AtCoder ABC 023 D「射撃王」
問題概要
- \(N\) 個の風船があり、風船 \(i\) は初期高度 \(H_i\)、1秒ごとに \(S_i\) 上昇する。
- 競技開始時に1個、その後1秒ごとに1個の風船を割れる（合計 \(N\) 個のタイミング 0,1,…,N-1 で割る）。
- 風船を割ったときの高度がその風船のペナルティ。最終的なペナルティは、割ったすべての風船のペナルティの最大値。
- 割る順番は自由に選べるとき、最終ペナルティの最小値を求めよ。
解法の着想
「最大値の最小化」は二分探索が有効です。
単調性
もしペナルティを \(x\) 以下にできるなら、\(x+1\) 以下にも当然できます。
逆に \(x\) でできないなら、\(x-1\) でもできません。
よって「ある値 \(x\) に対して、最終ペナルティを \(x\) 以下にできるか？」という判定問題を解き、可能な最小の \(x\) を二分探索で求めます。
判定問題 (penalty ≤ x にできるか？)
各風船の制限時刻
風船 \(i\) を時刻 \(t\) に割ると高度は \(H_i + S_i \cdot t\)。これが \(x\) 以下である条件は
[ H_i + S_i \cdot t \le x \quad\Longleftrightarrow\quad t \le \frac{x - H_i}{S_i} ]
したがって、その風船を 割らなければならない最終時刻 は
[ T_i = \left\lfloor \frac{x - H_i}{S_i} \right\rfloor ]
です（\(x < H_i\) の場合は最初から無理 → 判定は No）。割る順序の最適戦略
最終時刻が早い（\(T_i\) が小さい）風船ほど、差し迫っている ので先に割るべきです。
時刻 \(0,1,\dots,N-1\) のスロットに、\(T_i\) の小さい順に風船を割り当てます。
つまり \(T\) を昇順ソートしたものを \(T'_0 \le T'_1 \le \dots \le T'*{N-1}\) とすると、
\(i\) 番目（0-indexed）に割る風船は時刻 \(i\) に割ることになります。割り切れる条件
時刻 \(i\) に割る風船は、その最終時刻 \(T'_i\) が \(i\) 以上 でなければなりません。
もし \(T'_i < i\) なら、その風船は時刻 \(i\) より前に割る必要があるのに、それ以前のスロットはすでに埋まっているため不可能です。
よって、すべての \(i\) で \(T'_i \ge i\) が成り立てば Yes、一つでも \(T'_i < i\) なら No です。
これで判定問題が \(O(N \log N)\)（ソートがボトルネック）で解けます。
二分探索の実装
不変条件 (invariant)
left: 常に 達成できない ペナルティ値right: 常に 達成できる ペナルティ値
初期値：
left = 0（正の高度なのでペナルティ0は絶対に無理）right = max_i (H_i + S_i \cdot (N-1)) + 1（すべての風船を最後の時刻 \(N-1\) に割った場合の最大ペナルティより少し大きな値。これなら必ず達成できる）
ループ：
while right - left > 1:
mid = (left + right) // 2
if can(mid):
right = mid # mid は達成できる → 右端を狭める
else:
left = mid # mid は達成できない → 左端を狭める
while right - left > 1:
mid = (left + right) // 2
if can(mid):
right = mid # mid は達成できる → 右端を狭める
else:
left = mid # mid は達成できない → 左端を狭める
ループ終了後、right が「達成できる最小のペナルティ」 → 答えとして出力。
計算量
- 二分探索の反復回数: \(O(\log M)\)（\(M = \max(H_i + S_i \cdot (N-1))\)）
- 各判定でソート: \(O(N \log N)\)
- 全体: \(O(N \log N \log M)\)
Pythonコード（最終版）
from typing import List
class Solution:
def min_max_penalty(self, H: List[int], S: List[int]) -> int:
N = len(H)
# 判定関数: 最大ペナルティを x 以下にできるか？
def can(x: int) -> bool:
limits = []
for i in range(N):
if x < H[i]:
return False
# この風船を割らなければならない最終時刻（整数切り捨て）
limits.append((x - H[i]) // S[i])
limits.sort()
for i, t in enumerate(limits):
if t < i: # 時刻 i に割ろうとするが、その風船の限界は i 未満
return False
return True
# 上限: 全風船を最後の時刻 N-1 に割った場合の最大ペナルティ
right = max(H[i] + S[i] * (N - 1) for i in range(N)) + 1
left = 0
while right - left > 1:
mid = (left + right) // 2
if can(mid):
right = mid
else:
left = mid
return right
# 使用例（AtCoderの入力形式）
if __name__ == "__main__":
import sys
input = sys.stdin.readline
N = int(input())
H = []
S = []
for _ in range(N):
h, s = map(int, input().split())
H.append(h)
S.append(s)
sol = Solution()
print(sol.min_max_penalty(H, S))
from typing import List
class Solution:
def min_max_penalty(self, H: List[int], S: List[int]) -> int:
N = len(H)
# 判定関数: 最大ペナルティを x 以下にできるか？
def can(x: int) -> bool:
limits = []
for i in range(N):
if x < H[i]:
return False
# この風船を割らなければならない最終時刻（整数切り捨て）
limits.append((x - H[i]) // S[i])
limits.sort()
for i, t in enumerate(limits):
if t < i: # 時刻 i に割ろうとするが、その風船の限界は i 未満
return False
return True
# 上限: 全風船を最後の時刻 N-1 に割った場合の最大ペナルティ
right = max(H[i] + S[i] * (N - 1) for i in range(N)) + 1
left = 0
while right - left > 1:
mid = (left + right) // 2
if can(mid):
right = mid
else:
left = mid
return right
# 使用例（AtCoderの入力形式）
if __name__ == "__main__":
import sys
input = sys.stdin.readline
N = int(input())
H = []
S = []
for _ in range(N):
h, s = map(int, input().split())
H.append(h)
S.append(s)
sol = Solution()
print(sol.min_max_penalty(H, S))
まとめ
- 「最大値の最小化」 → 二分探索＋判定問題。
- 判定では各風船の「割る最終時刻」を計算し、ソートして貪欲に割り当てる。
- 不変条件を明確にすることで、
return rightで直感的に答えが得られる。