ABC023 D - 射撃王 - ツバサの備忘録

解法

最大値の最小値を求めよ、といえば！二分探索です、ということで二分探索をしていきます。
$X$ 点を達成できるかどうか、を二分探索で調べていきます。
ここでの達成できるか、はぴったりではなく、 $X$ 点以上を達成できるかどうか、になります。最終的に最小値を二分探索で求めていくため、ぴったりの値が最後に残ることになるので、 $X$ 点以上かどうか調べるだけでよいです。
ということで、 $X$ 点以上かどうかを調べる方法が以下になります。
まず、 $h_{i} \gt X$ となる $i$ が存在したら不可能です。
あとは、 $X$ を超えないような、 $i$ 番目の得点の最大値になるような秒数 $t_{i}$ を求めます。
$\frac{(X - h_{i} ) }{s_{i}}$ を計算すると、その秒数が求まります。
あとは、この値を昇順でソートしたときに、
$t_{i} \lt i$ となるような $i$ が存在したら不可能、存在しなければ可能になります( $i$ は0-indexedです)。
あとはこれをもとにして二分探索を行うことで、答えを求めることができます。

感想

夏休みぐらいのときに、先輩から「最大値の最小や最小の最大値を求める問題では二分探索がしたくなる」と教わったので、実際にその通りに実行してみたら、サクっと解けました。
加えて、最近の練習会で、半開区間を利用した二分探索の実装方法を教わったので、二分探索に関してはバグなく通すことができました( $h_{i} \gt X$ となるパターンを考慮しきれていなかったのでWA自体は出したのですが…)。
この手の問題をサクサク解けるようになると楽しいです！