TCO15 Round 2D med:BallsInBoxes

うーむ, もうちょっと時間があれば…

問題

TopCoder Statistics - Problem Statement

解法

まず N が 3*K-1 以下の場合を考えます。この場合, ボールが入っている区間の左端がどこかを特定すれば良いですが,左端の候補は N-K+1 個あり, これはたかだか 2*K なので二分探索で求めることが出来ます。 1 回二分探索をすると区間は (N+1)/2 に狭まるので区間の長さが 1 になるところを探しましょう。

N が 3*K 以上の場合はそのまま二分探索することは出来ないのでまず 1 回ずつの調査で調べるべき区間を K ずつ減らしていきます。

これらの試行回数の和が答えです。

class BallsInBoxes {
public:
    long long maxTurns(long long N, long long K) {
        ll step = N/K;
        ll ans = 0;
        if (step >= 3) {
            ans += step-2;
            N -= K*ans;
        }
        N = N-K+1;
        while (N>1) {
            ans++;
            N = (N+1)/2;
        }
        return ans;
    }
};