概要

モンスターを左から順に訪れ、攻撃力が足りないモンスターはスタックに後回しにし、倒せるモンスターを倒すたびにスタックの一番上から連鎖的に倒せるか確認する、シミュレーション問題です。

考察

問題の構造を理解する

高橋君は攻撃力 \(h = 0\) から始めて、モンスターを左から順に訪れます。各モンスターに対して：

• 倒せない場合（\(D_i > h\)）：スタックの一番上に積む（後回し）
• 倒せる場合（\(D_i \leq h\)）：倒して \(h \leftarrow h + D_i\)、ゴールド \(+V_i\)。その後、スタックの一番上が倒せるなら連鎖的に倒し続ける

ポイントは、スタックはLIFO（後入れ先出し）なので、最近後回しにしたモンスターが先に再挑戦の対象になることです。スタックの途中を飛ばすことはできません。

計算量について

一見すると、各モンスターを倒すたびに while ループでスタックを確認するため、二重ループで \(O(N^2)\) になりそうに見えます。

しかし、各モンスターはスタックに追加されるのは高々1回、スタックから取り出されるのも高々1回です。つまり、while ループの中での pop 操作は全体を通して合計 \(N\) 回以下しか発生しません。これは「償却計算量（amortized analysis）」と呼ばれる考え方で、全体として \(O(N)\) に収まります。

具体例

例えば、\(N = 4\) で以下のモンスターがいるとします：

モンスター	\(D_i\)	\(V_i\)
1	0	10
2	5	20
3	3	15
4	0	5

• モンスター1：\(D_1 = 0 \leq h = 0\) → 倒す。\(h = 0, \text{gold} = 10\)。スタック空なので解消処理なし。
• モンスター2：\(D_2 = 5 > h = 0\) → 後回し。スタック: \([(5, 20)]\)
• モンスター3：\(D_3 = 3 > h = 0\) → 後回し。スタック: \([(5, 20), (3, 15)]\)
• モンスター4：\(D_4 = 0 \leq h = 0\) → 倒す。\(h = 0, \text{gold} = 15\)。スタック一番上は \((3, 15)\)、\(3 > 0\) なので解消終了。
• 最後の解消処理：スタック一番上 \((3, 15)\)、\(3 > 0\) → 倒せず終了。

最終結果：ゴールド \(15\)、スタックに2体残る。

アルゴリズム

1. \(h = 0\)（攻撃力）、\(\text{gold} = 0\)（所持ゴールド）、空のスタックを用意する。
2. \(i = 1, 2, \ldots, N\) の順に各モンスターを処理する：
   • \(D_i > h\) ならスタックに \((D_i, V_i)\) を積む。
   • \(D_i \leq h\) なら倒し、\(h += D_i\)、\(\text{gold} += V_i\)。その後、スタックの一番上が倒せる限り連鎖的に倒す。
3. 全モンスター訪問後、最後にもう一度スタックの一番上から連鎖的に倒せるか処理する。
4. \(\text{gold}\) を出力する。

計算量

• 時間計算量: \(O(N)\)（各モンスターのスタックへの push/pop が合計高々 \(N\) 回ずつ）
• 空間計算量: \(O(N)\)（スタックに最大 \(N\) 体のモンスターが入る可能性がある）

実装のポイント

• Pythonのリストを使い、append で push、pop() で一番上を取り出すことで、スタックを簡単に実装できます。

• sys.stdin.buffer.read() で入力を一括読み込みすることで、Pythonでも高速に入力処理できます。

• 攻撃力 \(h\) は最大 \(N \times 10^9 \approx 2 \times 10^{14}\) になり得ますが、Pythonでは整数のオーバーフローを気にする必要はありません（C++等では long long が必要です）。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    h = 0
    gold = 0
    stack = []  # list of (D, V), top is end
    
    for i in range(N):
        D = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        
        if D > h:
            stack.append((D, V))
        else:
            gold += V
            h += D
            # 後回し解消処理
            while stack and stack[-1][0] <= h:
                d, v = stack.pop()
                gold += v
                h += d
    
    # 最後にもう一度後回し解消処理
    while stack and stack[-1][0] <= h:
        d, v = stack.pop()
        gold += v
        h += d
    
    print(gold)

main()

---

この解説は claude4.6opus-thinking によって生成されました。