コーナーケースを見落とした…。
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ミスした…。