概要

与えられたルール通りに「倒せるなら倒す／倒せないならスタックに積む」を順番に実行し、最後にスタックから倒せる分だけ倒したときの合計報酬を求める問題です。

考察

この問題のポイントは、行動の選択肢がなく、手順が完全に決まっていることです。したがって「最適化」ではなく、ルール通りに正確にシミュレーションすれば答えが出ます。

ただし注意点があります。

• モンスターを1体倒すたびに「後回し解消処理」が走り、スタック上のモンスターを連鎖的に倒せることがあります。
• これを素朴に実装して、例えば「スタック内の倒せるモンスターを全部探す」ようなことをすると、スタックの中身を何度も走査してしまい、最悪 \(O(N^2)\) で TLE になり得ます。

しかし本問の「後回し解消処理」は、 - スタックの一番上しか見ない - 倒せたら pop して攻撃力が増え、さらに次の一番上を確認する

という LIFO（最後に積んだものから試す） の挙動そのものです。よって、スタック（配列の末尾）を使って

• 倒せないなら push
• 倒せるなら倒して、while で「一番上が倒せる限り pop」

と書くだけで、ルール通りの処理をそのまま再現できます。

具体例： - \(h=3\) のとき、後回しスタック上から順に強さが [10, 4, 2]（右端が一番上）だとします。 - 一番上 2 は倒せる → 倒して \(h=5\) - 次の一番上 4 も倒せる → 倒して \(h=9\) - 次の一番上 10 は倒せない → ここで停止
この「上から順にしか見ない」挙動が重要です。

アルゴリズム

次の変数を管理します。

• 現在の攻撃力 \(h\)（初期 \(0\)）
• 合計ゴールド gold（初期 \(0\)）
• 後回しスタック stack（要素は (D, V)）

処理は次の通りです。

1. \(i=1..N\) を順に見る。
2. もし \(D_i > h\) なら倒せないので stack.append((D_i, V_i))。
3. もし \(D_i \le h\) なら倒す：
   • gold += V_i
   • h += D_i
   • 直後に後回し解消処理：
     • while stack が空でなく、stack[-1].D <= h の間

          - `pop` して倒す（`gold` と `h` を更新）
       

4. 全モンスター訪問後、最後にもう一度同じ while を回して、倒せる分だけスタックから倒す。
5. 残ったスタックは倒せない扱いなので無視し、gold を出力する。

この方法は、問題文の手順をそのままコードに落とした形になっています。

計算量

• 時間計算量: \(O(N)\)
  各モンスターは高々1回 push され、高々1回 pop されます。while が入っていても、総 pop 回数は最大 \(N\) なので全体で線形時間です（償却計算量）。
• 空間計算量: \(O(N)\)
  最悪の場合すべて後回しになり、スタックに \(N\) 個積まれます。

実装のポイント

• Python では list の append / pop を使うとスタックを高速に扱えます（末尾操作は \(O(1)\)）。

• 「後回し解消処理」は必ず while stack and stack[-1][0] <= h: の形で、一番上だけを見て連鎖的に処理します。

• 入力が最大 \(2\times 10^5\) なので、sys.stdin.buffer.read() のような高速入力にしておくと安全です。

• \(D_i=0\) の場合でも「倒せるなら倒す」で問題ありません（攻撃力は増えませんが、報酬は加算されます）。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    idx = 1

    h = 0
    gold = 0
    stack = []  # (D, V)

    for _ in range(n):
        d = int(data[idx]); v = int(data[idx + 1]); idx += 2
        if d > h:
            stack.append((d, v))
        else:
            gold += v
            h += d
            while stack and stack[-1][0] <= h:
                d2, v2 = stack.pop()
                gold += v2
                h += d2

    while stack and stack[-1][0] <= h:
        d2, v2 = stack.pop()
        gold += v2
        h += d2

    sys.stdout.write(str(gold))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。