TOC13の1Cの2問目 (TheOlympiadInInformatics)

前回は数年ぶりの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とかあるんですね。初めて知りました。

まぁ制約条件を読飛ばしているとか話にならないので、次は気をつけようと思います。