競技プログラミング用 知識集積所
ABC457D - Raise Minimum
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
愚直にやるなら、毎回最小値を探してそこに操作をすることになる。
しかし、回数Kが最大10^18と多く、最小値を探すのも長さNの数列を全部見ていては、全く時間が足りない。
そこで高速化を考える。
しかし、回数Kが最大10^18と多く、最小値を探すのも長さNの数列を全部見ていては、全く時間が足りない。
そこで高速化を考える。
問題は「最大値はいくつか？」だが、ひとまず「その値をXにできるか？」を考えてみる。
これは、各値ごとにX以上にするために必要な回数の総和を求めれば、O(N)で答えられる。
回数が非常に多いため、long long型でさえはみ出ることに注意。
K+1以上はどれだけ多くても意味がないので、大きくなり過ぎたらK+1に戻すとよい。
これは、各値ごとにX以上にするために必要な回数の総和を求めれば、O(N)で答えられる。
回数が非常に多いため、long long型でさえはみ出ることに注意。
K+1以上はどれだけ多くても意味がないので、大きくなり過ぎたらK+1に戻すとよい。
さて、「ある値の最大値（最小値）はいくつか？」という問題で、
- 「その値をXにできるか？」がO(N)で解ける
- その値をXにできるなら、X以下（以上）は絶対に全部できる
- その値をXにできないなら、X以上（以下）は絶対に全部できない
の3つが成り立つ場合、二分探索※でO(NlogW)（Wは解としてありえる範囲）で間に合わせることができる。
この問題は、「数列の全ての値を基準値以上にできる、の基準値の最大値はいくつか？」という問題。
よって、「数列の全ての値を基準値以上にできる、の基準値をXにできるか？」と考えることでこれを適用できる。
よって、「数列の全ての値を基準値以上にできる、の基準値をXにできるか？」と考えることでこれを適用できる。
