Educational Codeforces Round 61 D. Stressful Training

Problem - D - Codeforces

問題概要

コンテスト参加者が使う $n$ 台のPCがある。 $i$ 番目のPCの初期電池残量は $a_{i}$ で、消費速度は毎ステップ $b_{i}$ である。

初めに充電器の充電速度として非負整数 $c$ を決め、以下の処理を $k-1$ ステップ行う。

各ステップごとに、どのPCを充電するかを1台選ぶ。
充電対象として選んだPCは、電池残量が $b_{i} - c$ 減る。それ以外のPCはそれぞれ $b_{i}$ 減る。電池残量に上限はない。

全てのステップにおいて全てのPCの電池残量が負にならなければコンテストは成功である。コンテストを成功させることが可能な非負整数 $c$ の最小値を求めよ。（ $c$ の値に関わらず不可能な場合は -1 を出力せよ。）

※ステップ数が $k-1$ なのが謎ですが、サンプルがそう言っているのでそうなんだと思います。

制約

$1 \le n \le 2 \times 10^{5}$
$1 \le k \le 2 \times 10^{5}$
$1 \le a_{i} \le 10^{12}$
$1 \le b_{i} \le 10^{7}$

解法

二分探索をします。 $c$ を固定した時にコンテストを成功させることが可能かどうかを判定することを考えます。

最初のステップを0ステップ目として各ステップに番号を付けます。 $c$ を固定することで、各PCについて「 $t$ 回目の充電は遅くとも何ステップ目までに行わなければいけないか？」を求めることが出来ます。例えば $i$ 番目のPCでは、電池残量が $a_{i}$ からスタートして1ステップごとに $b_{i}$ 減っていくので、1回目の充電は遅くとも $\lfloor\frac{a_{i}}{b_{i}}\rfloor$ ステップ目終了時点までに行う必要があります。2回目の充電は $\lfloor\frac{a_{i} + c}{b_{i}}\rfloor$ ステップ目終了時点までに、3回目の充電は $\lfloor\frac{a_{i} + 2c}{b_{i}}\rfloor$ ステップ目終了時点までに…とそれ以降も計算できます。

これを、計算結果が最終ステップである $k-2$ ステップ目を超えるまで計算します。ただし合計充電回数が $k-1$ 回を超えてしまった場合は絶対に成功させられないので、その時点で強制的に処理を終わらせて「不可能」と判定してしまいましょう。このように処理すると全PCについての処理を $O(\max(n, k))$ 時間で終わらせることが出来ます。

これを全てのPCについて計算することで、各ステップについて「 $t$ ステップ目終了時点までに、全体で累積何回の充電が必要か？」を求めることが出来ます。対して $t$ ステップ目終了時点までに行える累積充電回数は（0-indexedとしているので） $t+1$ 回です。全てのステップそれぞれの終了時点においてこの累積充電回数が足りていることが、コンテストを成功させられる必要十分条件となります。これで判定ができます。