SRM561 Div1 Easy - ICPCBalloons

問題文が長い!

問題

ICPCの問題正解者に渡すための風船があり、色はn通りある
色iのものはc[i]個あり、それら全てのサイズはs[i]である ('M'edium or 'L'arge)
問題はm問あり、j番目の問題は最大でa[i]チームにしか解かれることはない
それぞれの風船は金を払えば好きな色に変えることができる
(元々存在しない色に変えることも可能)
以下の条件を満たすように風船を配ることができるか判定し、できる場合はそのために色を変える風船の個数の最小値を求めよ
1) 各チームが同じ問題を解いたときに渡す風船は色もサイズも同じ
2) 2つの異なる問題を解いたときに渡す風船の色はそれぞれ異なる

1 <= n <= 50
1 <= c[i] <= 100
1 <= m <= 15
1 <= a[i] <= 100

解法

mが小さいから、各問題に割り当てる風船のサイズの組み合わせを全通り試せる
サイズを決めてしまえばあとはサイズごとに
「n'個のグループがあり、i番目のグループのサイズはc'[i]
これをm'個のグループに分け、i番目のグループのサイズはa'[i]以上にしたい
グループのサイズを増やすには他のグループからもらう必要があり、1個もらう度にコスト1かかる
コストの最小値は?」
という問題を解けばいい
Σc'[i] < Σa'[i] ならどうやっても無理
そうじゃない場合はデカイc'[i]にデカイa'[i]を貪欲に対応させればいい
それでa'[i]<c'[i]の各iでc'[i]-a'[i]を足し合わせたものが答え
(どこから引っ張ってくるかは考えなくていい)

class ICPCBalloons {
public:
	int f(vector<int> &c, vector<int> &a) {
		if (accumulate(all(c),0) < accumulate(all(a),0)) return 1<<20;
		int n = c.size(), m = a.size();
		sort(c.rbegin(), c.rend()), sort(a.rbegin(), a.rend());
		rep(i,m) if (i<n) a[i] -= min(c[i],a[i]);
		return accumulate(all(a),0);
	}

	int minRepaintings(vector<int> c, string s, vector<int> a) {
		int n = c.size(), m = a.size(), res = 1<<20;
		vector<int> cx, cy;
		rep(i,n) (s[i]=='M' ? cx : cy).push_back(c[i]);
		rep(b,1<<m) {
			vector<int> ax, ay;
			rep(i,m) (b>>i&1 ? ax : ay).push_back(a[i]);
			chmin(res, f(cx,ax) + f(cy,ay));
		}
		return (res==(1<<20) ? -1 : res);
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12314&rd=15183