abc 023 d '射撃王' (python)
二分探索の問題。二分探索はここのサイトがとても参考になった。
めぐる式二分探索 コピペで使えるPython実装 - 学習する天然ニューラルネット
答えを arg と仮定した場合にそれが条件をみたすなら、arg+1についてもまた調べる、満たさないなら、arg//2 について調べるといったアルゴリズムを作って条件を満たす最大値を求める
条件は、n個の的についてそれぞれ何秒までに割れば その的を合計 arg秒以内に割れるかを求めて、その求めた秒数の list を小さい順にみていったときに
0 <= i <= n-1 で list[ i ] > i を満たしていることである。
numpy を導入するとリスト全体を一括で計算できるので早くて楽。
(導入前:4784ms 導入後:536ms )
numpy なしの提出
Submission #12297759 - AtCoder Beginner Contest 023
import numpy as np import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline n = int(readline()) x = np.array(read().split(),np.int64) h = x[::2] s = x[1::2] if n == 1: print(a[0]) exit() def is_ok(arg): limit = (arg-h)//s limit.sort() return (limit >= p).all() 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 p = np.arange(n) ans = 10**14 print(meguru_bisect(0, ans+1))