TCO15 Round 2D med:BallsInBoxes
うーむ, もうちょっと時間があれば…
解法
まず 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; } };