ABC023 D – 射撃王

はじめに

競プロの精進のために学びがあった問題についてまとめています。
目標は AtCoder 水色！

今のレートは茶色です。

問題

ABC023 D – 射撃王を解きました。

難易度は青色。

考察

すべての風船を割ったときの得点の最大値が求める答えとなる。

常に現時点での最大高度の風船を貪欲的に割っていけばいいのではと思ったが、それだとSの値によっては正しい解に至らない。

そこで、この問題を「高度X(ペナルティ)以下の範囲ですべての風船を割ることができるか」という判定問題と置き換える。

この判定のためには、各風船が高度Xを超える最小の時間を調べ、それを貪欲的に撃ち落としたときに間に合うかどうかを調べればよい。

判定問題の解は2分探索になるため、トータルの計算量はO(logN * N)になる（はず）。

コード

N = int(input())
H = []
S = []
MAX = pow(10, 18)

for i in range(N):
    h,s = map(int,input().split())
    H.append(h)
    S.append(s)


def check(x):
    T = []
    for i in range(N):
        t = (x - H[i]) // S[i]
        T.append(t)

    T.sort()
    for i, t in enumerate(T):
        if t < i:
            return False

    return True

def search_x(left, right):
    while right - left > 1:
        mid = (right + left) // 2
        if check(mid):
            right = mid

        else:
            left = mid

    return right

print(search_x(1, MAX))

まとめ

「答えの範囲で2分探索」って1日100回唱えてる。