ABC 023 D 射撃王【Python】

問題はこちら。

得点 X が可能かどうかを判定する関数を作って二分探索する。

初期高度が H, 上昇速度が S の風船を高度 X 以下で割るためには開始から (X - H) / S 秒以内に割らなければいけないということに着目する。

// 得点のMAXを超える適当な値を設定
INF = 2*10**14

// 得点 X が可能かどうかを判定する関数
def check(X):
   data = [0]*N
   for i in range(N):
       H, S = HS[i]
       j = (X - H) // S
       if j < 0:
           return False
       data[min(j, N - 1)] += 1
   if data[0] >= 2:
       return False
   for i in range(1, N):
       data[i] += data[i - 1]
       if data[i] >= i + 2:
           return False
   return True
   
// 入力
N = int(input())
HS = [tuple(map(int, input().split())) for _ in range(N)]

// 二分探索
l, u = 0, INF
while l < u:
   m = (l + u) // 2
   if check(m):
       u = m
   else:
       l = m + 1
ans = l

// 出力
print(ans)