競プロ初中級者100問

ABC023D 射撃王

この記事で使うアルゴリズム

二分探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc023/tasks/abc023_d

この問題は二分探索を用いて解くことができますが、標準ライブラリbisectを使うことはできません。なぜならbisectはリストに対する二分探索であり、この問題ではリスト化できない関数に対する二分探索が必要になるためです。

方針

  • 「ある時点での高度」や「速度」に対して貪欲に風船を割っても最適な割り方とはならない。
  • しかし、ある得点が与えられた時「その得点以下となるように風船を割ることができるか」を判定することはできる。
    • 各風船をいつまでに割れば良いかを考え、全ての風船に対して実行可能なスケジューリングがあるかを確認すれば良い
  • 判定を元にして二分探索を行えば良い

ポイント

  • 特典の最大値に注意する(1e+14)

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def is_ok(x):
    ls = []
    for i in range(N):
        ls.append((x-H[i])//S[i]) # いつまでに割れば良いか
    ls.sort() # 期限が近いものから先にわる
    for n in range(N):
        if (ls[n] < n): 
            return False # 時間ぎれ
    return True

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

N = int(input())
H = []
S = []
for i in range(N):
    h, s = map(int,input().split())
    H.append(h)
    S.append(s)
print (meguru_bisect(0,int(1e+14)))

二分探索を行う関数meguru_bisectはこちらの実装学習する天然ニューラルネットを利用させていただきました。記事の中で説明している通り、実装が簡潔でバグが入り難いと思います。

関連記事

記事情報

  • 投稿日：2020年4月12日
  • 最終更新日：2020年5月8日