kmjp's blog

競技プログラミング参加記です

TopCoder SRM 622 Div2 Medium BoxesDiv2

コーナーケースを見落とした…。
http://community.topcoder.com/stat?c=problem_statement&pm=13192

問題

各種類の飴がそれぞれcandyCounts[i]個ある。

ここに飴のサイズに対し2の累乗倍のサイズの箱が無限にある。
まず、同じ種類の飴をそれぞれ1個の箱に入れる。

次に、これらの飴の入った箱が、さらに大きい箱に2つまで詰め込むことができる。
最終的に全部の飴と箱を1つの箱にしまいたい。
そのような箱の最小サイズを答えよ。

解法

candyCountsの中身が箱2個以上ある間は、大きさでソートし小さい分2つを大きな箱にしまう、という処理を繰り返せばよい。
適宜箱のサイズが2の累乗となるようにする。

class BoxesDiv2 {
	public:
	int findSize(vector <int> candyCounts) {
		while(candyCounts.size()>1) {
			sort(candyCounts.begin(),candyCounts.end());
			int x=1;
			while(x<candyCounts[1]) x*=2;
			candyCounts.erase(candyCounts.begin());
			candyCounts.erase(candyCounts.begin());
			candyCounts.push_back(x*2);
		}
		int x=1;
		while(x<candyCounts[0]) x*=2;
		return x;
	}
}

まとめ

飴の種類が1個のコーナーケースで、サイズを2の累乗にするのを忘れて1ミスした…。