SRM 568 Div1 Easy BallsSeparating

問題

箱がN個あり、i番目の箱には赤色のボールがred[i]個、緑色のボールがgreen[i]個、青色のボールがblue[i]個入っている。すべての箱に対して、それぞれの箱に入っているボールの色数が必ず１色以下になるようにボールを他の箱に移動したい。動かす最小のボール数を求めよ。

やりかた

貪欲。
ある箱に入っているボール中、一番多いボール以外の2種類の色のボールを他の箱に動かしていけば良い。しかしそうするとすべての箱で移動することになる色が出てくる可能性が有る（例えばすべての箱で青色のボールは他の箱に移した方が良いといった状況が起こりうる）。そのためとりあえず赤を残す箱、緑を残す箱、青を残す箱を決め、この3箱以外については上の貪欲法を、この3箱についてはその残す色以外を移動する。こうするとこの場合でのボールの移動数が出てくるので、この計算を3色残す箱をすべてのパターンで試し、その最小値を求めればよい。

以下ソース。

class BallsSeparating {
public:
  int minOperations(vector <int> red, vector <int> green, vector <int> blue) {
    int result = INF;
    int N = red.size();
    //赤を残す箱、緑を残す箱、青を残す箱を全パターン試す
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
	for(int k = 0; k < N; k++){
	  int tmp = 0;
	  if(i == j || j == k || k == i) continue;

          //赤を残す箱、緑を残す箱、青を残す箱以外について貪欲で移動数を計算
	  for(int l = 0; l < N; l++){
	    if(l == i || l == j || l == k) continue;
	    tmp += red[l] + green[l] + blue[l];
	    tmp -= max(red[l], max(green[l], blue[l]));
	  }
	  tmp += green[i] + blue[i];
	  tmp += red[j] + blue[j];
	  tmp += red[k] + green[k];
	  
	  result = min(result, tmp);  
	}
      }
    }
    return result == INF ? -1 : result;
  }
};