SRM 568 div1 easy: BallsSeparating

問題

TopCoder Statistics - Problem Statement

解法

box i に色を残しておけない際に, ボールが逃げる場所を作っておかなければなりません。

各色が逃げる場所を r, g, b とした時, ボールを動かす回数は,

• i==r の時は, green, blue を動かす回数
• i==g の時は, red, blue を動かす回数
• i==b の時は, red, green を動かす回数
• それ以外では, red, blue, green のうち, 一番個数の多いボールを残して他の色のボールを取り除くのが明らかに最適

というアルゴリズムから求めることが出来ます。

class BallsSeparating {
public:
    int minOperations(vector <int> red, vector <int> green, vector <int> blue) {
        const int INF = 1e9;
        int n = red.size();
        int ret = INF;
        for (int r = 0; r < n; r++) for (int g = 0; g < n; g++) for (int b = 0; b < n; b++) {
            if (r==g || g==b || b==r) continue;
            int tmp = 0;
            for (int i = 0; i < n; i++) {
                if (i==r) tmp += green[i]+blue[i];
                else if (i==g) tmp += blue[i]+red[i];
                else if (i==b) tmp += red[i]+green[i];
                else tmp += red[i]+blue[i]+green[i]-max({red[i], blue[i], green[i]});
            }
            ret = min(ret, tmp);
        }
        if (ret == INF) ret = -1;
        return ret;
    }
};