このページでは情報オリンピック 公式テキスト問題『射撃王』を完全解説します。
JOI公式テキストp114に載っている模範解答プログラムです。
n = int(input())
h = [0] * n
s = [0] * n
for i in range(n):
h[i], s[i] = map(int, input().split())
ok = 10 ** 14
ng = -1
while ok - ng > 1:
m = (ok + ng) // 2
t = [0] * n
for i in range(n):
if m < h[i]:
t[i] = -1
else:
t[i] = (m - h[i]) // s[i]
t = sorted(t)
is_ok = 1
for i in range(n):
if t[i] < i:
is_ok = 0
if is_ok == 1:
ok = m
else:
ng = m
print(ok)
模範解答の完全解説です。
よく読んで完全に理解してください。
このプログラムは２分探索の手法（アルゴリズム）を使っています。
なぜ、２分探索で、風船の高度の最小値を求められるのか？それを理解してください。
テキストの解説は20行ほどと非常に簡素で完全な理解は難かしいです。
★解説
n = int(input())
まず、風船の数nを入力として受け取ります。
h = [0] * n
s = [0] * n
for i in range(n):
h[i], s[i] = map(int, input().split())
次に、各風船の初期高度h[i]と上昇速度s[i]を入力として受け取ります。
ok = 10 ** 14 注１）
上限値を考えられる限りの大きな数、兆にしました。
ng = -1 注２）
二分探索のための上限値okと下限値ngを設定します。
while ok - ng > 1:
m = (ok + ng) // 2
二分探索を利用するので中央値mを計算します。
★mは各風船が全部割れるまでの最小高度を格納するための変数です。
◆ではｔとは何か？
t = [0] * n
for i in range(n):
if m < h[i]:
t[i] = -1
else:
t[i] = (m - h[i]) // s[i]
このプログラムにおけるtは、各風船が全部割れるまでの秒数を格納するためのリストです。
★mは最初はかなり大きな数です。例えば500ｍとかになります。
そこで、最初に１つ目の風船の高度とmを比べ、１つ目の初期高度h[0]が600mなら、これは全部の風船を割れる最小高度mを上回っているのだから、全部の風船は割れないですね。
でもmが10000mなら割れますね。
では10000mまで風船が達するのに何秒かかる？1秒でｓ[0]=100m上がるなら
(10000-600)÷100 で94秒となる。これでt[0]が94となります。これを、風船の個数だけ繰り返します。
各風船が割れない時はt[0]などに-1と入れます。
もし、最初のt[0]が-1なら、割れない風船があるのだから、is_okを0に設定します。
t = sorted(t)
is_ok = 1
for i in range(n):
if t[i] < i:
is_ok = 0
これは割れないということですね。
これをもし、各風船が割れない時にt[0]などに0と入れると0秒で割れる意味になるので駄目ですね。
その後、tはソートされ、各風船が指定した時間内に割れるかどうかが確認されます。
全ての風船が指定した時間内に割れる場合、ok（探索範囲の上限）を更新します。そうでない場合、ng（探索範囲の下限）を更新します。
ここがポイントです！
求めるのは全部の風船が割れる最小高度です。
これを二分探索でどう求めるのでしょうか？全部の風船が割れるのは、最小高度より高い距離なら全部割れますよね。
だから、恐らく、最初に求まったmでも全部割れるでしょう。
では、さらに最小高度を求めるにはどうしたらよいか？
最小高度は1回目のmより左にあって小さいか？それとも右側にあって大きいか？左にありますよね。
そこで、右端＝ＯＫをmの値にして、求める範囲を左端の０からまでにするのです。
次にこの範囲の中間値を求めて、風船が全部割れるか調べます。
割れたらまた右端=OKをmにします。
割れなかったら、求める最小値はmより右にあるので左端＝ngをmにするのです。
こうすれば最小高度にmの値はどんどん近づいて行きます。
右端と左端が同じ値か逆転したら、それ以上調べるのを終了して良いですね。
★繰り返し処理の条件はこうです。
while ok - ng > 1:
mに最小高度が入っていますね。
★mを２分探索の値とするのは、飛び飛びの大きな値=中央値を試して試す回数を減らすためです。ここが右端と左端を更新している部分です。
if is_ok == 1:
ok = m
else:
ng = m
★ok = mは上限値をｍに、ng = mは下限値左端をmにして探索範囲を絞り込んでいって
いるのです。
（注１）
ok = 10 ** 14 の 10 ** 14 の意味は何ですか？
10 ** 14は、Pythonの演算子**を使用して10の14乗を計算する表現です。つまり、10を14回掛けることを意味します。
その結果は、1の後に14個の0が続く非常に大きな数、すなわち1兆（日本の数の単位）になります。
このプログラムでは、ok = 10 ** 14は二分探索の上限値を設定しています。つまり、探索する時間の範囲の最大値を非常に大きな値（1兆）に設定しています。
これは、探索範囲を十分に大きくすることで、全ての可能性をカバーするためです。
この値は、問題の制約に基づいて選ばれます。この場合、風船が割れるまでの時間が非常に長くなる可能性があるため、大きな値が選ばれました。
（注２）
ng = -1は、二分探索の下限値を設定しています。つまり、探索する時間の範囲の最小値を-1に設定しています。
二分探索では、探索範囲の上限値と下限値を設定し、その範囲を狭めていきます。このプログラムでは、okが上限値、ngが下限値となります。
ngの初期値を-1に設定する理由は、探索範囲を0以上の全ての整数に設定するためです。
なぜなら、この問題では求めるべき答え（風船が全て割れる最小の時間）は0以上の整数だからです。
したがって、ng = -1と設定することで、0以上の全ての整数を探索範囲とすることができます。
そして、二分探索を進めることで、この範囲を狭め、最終的に求めるべき答えを見つけることができます。
このように、二分探索は効率的に答えを見つけるための強力な手法となります。このプログラムでは、その手法を活用して、風船が全て割れる最小の時間を求めています
