SRM 561 div1 easy ICPCBalloons

問題文長すぎな。

問題

TopCoder Statistics - Problem Statement

N 種類のボールがある。これらは以下のような特徴がある。

• 大きさが決まっている(medium と large の 2 種類がある)
• 種類ごとにいくつあるか決まっている
• 種類ごとに色が異なることは保証されている

また, M 種類の箱がある。これらの箱にボールをいれたい。ただし,

• 同じ箱に入れるボールは色, 大きさが同じでなければならない。また, 別の箱に入れるボールではボールの色が異ならなければならない。
• M 種類の箱には, 入れたいボールの数が決まっている。

あなたは, ボールの色を変更することができる。なるべく少ない数のボールの色を変更して, M 個の箱に条件を満たすようにボールを入れたい。最小のボールの色の変更数を求めよ。

解法

とりあえずボールの大きさそれぞれで, ボールの数が多い順に並べておきます。

M が小さいので, ボールの二種類の大きさのどちらを入れるかで場合分けすると良さそうです。

箱に入れる必要のあるボールの数が多い順に考えます。必要のあるボールが多いものにはできるだけ多くの数のある種類のボールを対応させるのが最適なので, そのようにします。

class ICPCBalloons {
public:
    int minRepaintings(vector <int> balloonCount, string balloonSize, vector <int> maxAccepted) {
        const int INF = 1e9;
        int N = balloonSize.size(), M = maxAccepted.size();
        vector<int> large, small;
        int L = 0, S = 0;
        for (int i = 0; i < N; i++) {
            if (balloonSize[i] == 'L') {
                large.push_back(balloonCount[i]);
                L += balloonCount[i];
            } else {
                small.push_back(balloonCount[i]);
                S += balloonCount[i];
            }
        }
        for (int i = 0; i < 50; i++) {
            large.push_back(0);
            small.push_back(0);
        }
        sort(large.rbegin(), large.rend());
        sort(small.rbegin(), small.rend());
        int ans = INF;
        for (int s = 0; s < 1<<M; s++) {
            int lsum = 0, ssum = 0;
            for (int i = 0; i < M; i++) {
                if ((s>>i)&1) lsum += maxAccepted[i];
                else ssum += maxAccepted[i];
            }
            if (lsum > L || ssum > S) continue;
            vector<int> al, as;
            for (int i = 0; i < M; i++) {
                if ((s>>i)&1) al.push_back(maxAccepted[i]);
                else as.push_back(maxAccepted[i]);
            }
            sort(al.rbegin(), al.rend());
            sort(as.rbegin(), as.rend());
            int cnt = 0;
            for (int i = 0; i < al.size(); i++) {
                cnt += max(0, al[i] - large[i]);
            }
            for (int i = 0; i < as.size(); i++) {
                cnt += max(0, as[i]-small[i]);
            }
            ans = min(ans, cnt);
        }
        if (ans == INF) ans = -1;
        return ans;
    }
};