JOI情報オリンピック 公式テキスト問題『射撃王』を完全解説!

このページでは情報オリンピック 公式テキスト問題『射撃王』を完全解説します。

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)

模範解答の完全解説です。

よく読んで完全に理解してください。

このプログラムは2分探索の手法(アルゴリズム)を使っています。

なぜ、2分探索で、風船の高度の最小値を求められるのか?それを理解してください。

テキストの解説は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  注1)
上限値を考えられる限りの大きな数、兆にしました。

ng = -1  注2)

二分探索のための上限値okと下限値ngを設定します。

while ok - ng > 1:
m = (ok + ng) // 2

二分探索を利用するので中央値mを計算します。

★mは各風船が全部割れるまでの最小高度を格納するための変数です。

◆ではtとは何か?

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は最初はかなり大きな数です。例えば500mとかになります。

そこで、最初に1つ目の風船の高度とmを比べ、1つ目の初期高度h[0]が600mなら、これは全部の風船を割れる最小高度mを上回っているのだから、全部の風船は割れないですね。
でもmが10000mなら割れますね。

では10000mまで風船が達するのに何秒かかる?1秒でs[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より左にあって小さいか?それとも右側にあって大きいか?左にありますよね。

そこで、右端=OKをmの値にして、求める範囲を左端の0からまでにするのです。

次にこの範囲の中間値を求めて、風船が全部割れるか調べます。

割れたらまた右端=OKをmにします。

割れなかったら、求める最小値はmより右にあるので左端=ngをmにするのです。

こうすれば最小高度にmの値はどんどん近づいて行きます。

右端と左端が同じ値か逆転したら、それ以上調べるのを終了して良いですね。

★繰り返し処理の条件はこうです。

while ok - ng > 1:

mに最小高度が入っていますね。

★mを2分探索の値とするのは、飛び飛びの大きな値=中央値を試して試す回数を減らすためです。ここが右端と左端を更新している部分です。

if is_ok == 1:
ok = m
else:
ng = m

★ok = mは上限値をmに、ng = mは下限値左端をmにして探索範囲を絞り込んでいって
いるのです。

(注1)

ok = 10 ** 14 の 10 ** 14 の意味は何ですか?

10 ** 14は、Pythonの演算子**を使用して10の14乗を計算する表現です。つまり、10を14回掛けることを意味します。

その結果は、1の後に14個の0が続く非常に大きな数、すなわち1兆(日本の数の単位)になります。

このプログラムでは、ok = 10 ** 14は二分探索の上限値を設定しています。つまり、探索する時間の範囲の最大値を非常に大きな値(1兆)に設定しています。
これは、探索範囲を十分に大きくすることで、全ての可能性をカバーするためです。
この値は、問題の制約に基づいて選ばれます。この場合、風船が割れるまでの時間が非常に長くなる可能性があるため、大きな値が選ばれました。

(注2)

ng = -1は、二分探索の下限値を設定しています。つまり、探索する時間の範囲の最小値を-1に設定しています。

二分探索では、探索範囲の上限値と下限値を設定し、その範囲を狭めていきます。このプログラムでは、okが上限値、ngが下限値となります。

ngの初期値を-1に設定する理由は、探索範囲を0以上の全ての整数に設定するためです。
なぜなら、この問題では求めるべき答え(風船が全て割れる最小の時間)は0以上の整数だからです。

したがって、ng = -1と設定することで、0以上の全ての整数を探索範囲とすることができます。

そして、二分探索を進めることで、この範囲を狭め、最終的に求めるべき答えを見つけることができます。

このように、二分探索は効率的に答えを見つけるための強力な手法となります。このプログラムでは、その手法を活用して、風船が全て割れる最小の時間を求めています