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 にできるか？)

  1. 各風船の制限時刻
    風船 (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）。

  2. 割る順序の最適戦略
    最終時刻が早い（(Ti) が小さい）風船ほど、差し迫っている ので先に割るべきです。
    時刻 (0,1,\dots,N-1) のスロットに、(T_i) の小さい順に風船を割り当てます。
    つまり (T) を昇順ソートしたものを (T'_0 \le T'_1 \le \dots \le T'    {N-1}) とすると、
    (i) 番目（0-indexed）に割る風船は時刻 (i) に割ることになります。

  3. 割り切れる条件
    時刻 (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 は達成できない → 左端を狭める

ループ終了後、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))

まとめ

  • 「最大値の最小化」 → 二分探索＋判定問題。
  • 判定では各風船の「割る最終時刻」を計算し、ソートして貪欲に割り当てる。
  • 不変条件を明確にすることで、return right で直感的に答えが得られる。