概要

モンスターを順番に訪問し、攻撃力が足りれば倒して報酬を得る。足りなければスタックにためて後で処理する。最終的に得られる報酬の合計を求める。

考察

この問題では、モンスターを左から順に訪問していく中で、攻撃力が足りない場合は一旦スタック（LIFO）に保存し、攻撃力が上がった後に倒せるかどうかを判定する必要があります。

重要な観察点は、「後回し解消処理」において、スタックの一番上から順に倒せるモンスターを探す必要があるということです。つまり、スタックはLIFO構造なので、新しい順に処理する必要があり、かつ何度も処理が発生する可能性があるため、効率的なデータ構造を使う必要があります。

素朴な方法として、毎回スタック全体を見て処理しようとするのは非効率で、最悪の場合 \(O(N^2)\) かかり、制約 \(N \leq 2 \times 10^5\) に対してはTLEになります。

これを解決するために、スタックの末尾（一番上）だけを見ればよいという性質を利用し、Pythonの collections.deque を使ってスタックを実現すると、高速な追加・削除が可能です。

さらに、モンスターを訪問するたびに「後回し解消処理」を行うことで、処理漏れを防ぎ、最後にも再度後回し処理を行うことで、スタックに残ったモンスターをできる限り倒すことができます。

アルゴリズム

1. 各モンスターを左から順に処理する。
2. 現在の攻撃力 \(h\) がモンスターの強さ \(D_i\) 以上であれば、その場で倒し、報酬 \(V_i\) を得て攻撃力を更新する。
3. 倒した直後、「後回し解消処理」を行う：
   • スタックの一番上のモンスターが現在の攻撃力で倒せるなら、それを取り出して倒す（これを繰り返す）。
4. 攻撃力が足りない場合は、そのモンスターをスタックに積む。
5. 全モンスターを処理した後、もう一度「後回し解消処理」を行う。
6. 最終的に得られた報酬の合計を出力する。

計算量

• 時間計算量: \(O(N)\)
  各モンスターは高々1回スタックに追加され、1回取り出されるため、全体で \(O(N)\)。
• 空間計算量: \(O(N)\)
  スタックに最大 \(N\) 個のモンスターが格納される。

実装のポイント

• スタックには (D, V) のタプルを保持し、攻撃力との比較と同時に報酬も取得できるようにする。

• 後回し解消処理はループで実装し、スタックが空 or 一番上のモンスターが倒せない場合に終了する。

• 最後の処理忘れに注意（全モンスター訪問後に再度後回し解消を行う）。

  ソースコード

import sys
from collections import deque

input = sys.stdin.read
data = input().split()

N = int(data[0])
monsters = [(int(data[2*i+1]), int(data[2*i+2])) for i in range(N)]

h = 0
total_gold = 0
stack = deque()  # (D, V) のタプルを保持するスタック

for D, V in monsters:
    if D <= h:
        # 倒せる場合
        total_gold += V
        h += D
        
        # 後回し解消処理
        while stack and stack[-1][0] <= h:
            d, v = stack.pop()
            total_gold += v
            h += d
    else:
        # 倒せない場合はスタックに追加
        stack.append((D, V))

# 最後の後回し解消処理
while stack and stack[-1][0] <= h:
    d, v = stack.pop()
    total_gold += v
    h += d

print(total_gold)

この解説は qwen3-coder-480b によって生成されました。