読者です 読者をやめる 読者になる 読者になる

SRM 568 Div2 Medium BallsSeparating

問題

各ボックスiにはred[i],blue[i],green[i]のボールがそれぞれ入っている. 一つのボックスには一つの色のボールのみが入っているようにあるボックスのボールを他のボックスへ移動したい. ボールの最少移動回数を求めよ.

解答

全探索する. redのみが入っているボックス,blueのみが入っているボックス,greeのみが入っているボックスそれぞれ 3つを決めれば,他のボックスは最大の色のボールを除いてこれら3つのボックスへ移動するのが最小となる. そのため,この基準となる3つのボックスの選び方を全探索して,最少の移動コストを計算すれば良い.

一見時間がかかりそうだが,n=50から3つのボックスの選び方は(nC3)*3!なのでそれほど大きくはない.

class BallsSeparating
{
public:
  int minOperations(vector <int> red, vector <int> green, vector <int> blue)
    {
      int n = red.size();
      if (n < 3) return -1;
      vector<int> flag(n, 0);
      flag[n-1] = 3;
      flag[n-2] = 2;
      flag[n-3] = 1;
      int i;
      int res = INT_MAX;
      do{
        int curv = 0;
        for (i = 0; i < n && curv < res; i++){
          int sum = red[i] + blue[i] + green[i];
          int tmax = 0;
          if (flag[i] == 0){
            tmax = red[i];
            int tmax2 = max(green[i], blue[i]);
            tmax = max(tmax, tmax2);
          }else if (flag[i] == 1){
            tmax = red[i];
          }else if (flag[i] == 2){
            tmax = green[i];
          }else if (flag[i] == 3){
            tmax = blue[i];
          }
          curv += sum - tmax;
        }
        res = min(res, curv);
      }while(next_permutation(flag.begin(), flag.end()));
      return res;

    }
};