前回は数年ぶりのTopCoderで、コンテスト中にエディタの設定に手間取ったりしたので、今回こそはと思って参加しました。2問解けてまぁ行けたかなと思ってたら、2問目がシステムテストで落ちてて、またダメでした。生きるのが辛いです。
今回間違えた問題がこれです。
問題は人数不明のテスト受験者達が、人数がバラバラのグループに分けられていて、グループ毎の合計点数のみ与えられたときに、自分がK番以内の成績を取るには何点必要かというもの。
最初に書いてたコードが以下です。単純に0点から順に順位を計算して行っています。
int find(vector <int> sums, int k) { int max_score = 0; for (int i = 0; i < sums.size(); i++) { max_score = max(max_score, sums[i]); } int score = 0; for (; score < max_score; score++) { int possible = 0; bool found = true; for (int j = 0; j < sums.size(); j++) { int value = sums[j]; possible += (value / (score + 1)); if (possible > k) { found = false; break; } } if (found) { break; } } return score; }
後でシステムテストを走らせてみると、Time Exceededになってました。それで問題文を見るとKの範囲が0〜10億で、あーそれはダメだという事で、他の人のもチラチラ見ながら二分探索で書き直したのが以下。
int find(vector<int> sums, int k) { int lo = 0; int hi = *max_element(sums.begin(), sums.end()); int mid; while (lo < hi) { mid = (lo + hi) / 2; int possible = 0; for (int i = 0; i < sums.size(); i++) { possible += (sums[i] / (mid + 1)); } if (possible <= k) { // 取り過ぎ hi = mid; } else { // 足りない lo = mid + 1; } } return lo; }
条件を満たしている際の、上限値の付け替えがmid – 1じゃ無くてmidなところが注意で、これはその時のmidが条件を満たす下限値になっている可能性があるからですね。
あとvectorから最大値取得するのにstd::max_elementとかあるんですね。初めて知りました。
まぁ制約条件を読飛ばしているとか話にならないので、次は気をつけようと思います。