概要

モンスターを左から順に訪れ、現在の攻撃力で倒せるかどうかでスタックに積むか倒すかを判断し、スタックに積まれたモンスターは後で解消処理を行うことで、最終的に得られる報酬の合計を求める問題です。

考察

問題の重要なポイントは、モンスターを訪れる順序と後回しスタックのLIFO（後入れ先出し）の性質です。モンスターは左から順に訪れますが、後回しにしたモンスターはスタックに積まれ、後で解消処理が行われます。この解消処理では、スタックの一番上（最後に積まれたモンスター）から順に確認し、現在の攻撃力で倒せるなら倒して攻撃力を増加させます。素朴に全てのモンスターを毎回チェックすると、最悪ケースで \(O(N^2)\) の時間がかかり、制約 \(N \leq 2 \times 10^5\) では間に合いません。そこで、スタックを活用して効率的に処理する必要があります。

アルゴリズム

1. 現在の攻撃力 \(h\) と報酬の合計 \(total\_gold\) を0で初期化し、空のスタックを準備します。
2. 各モンスター \(i\) を左から順に処理します：
   • \(D_i > h\) の場合：モンスターをスタックに追加します。
   • \(D_i \leq h\) の場合：モンスターを倒し、報酬 \(V_i\) を加算し、攻撃力 \(h\) を \(D_i\) だけ増加させます。その後、スタックが空でなく、かつスタックの一番上のモンスターの強さが \(h\) 以下である限り、スタックからモンスターを取り出して倒し、報酬と攻撃力を更新します。
3. 全てのモンスターを訪れた後、スタックに残っているモンスターに対して再度解消処理を行います（スタックの一番上から順に、攻撃力で倒せる限り取り出して処理）。
4. 最終的な報酬の合計 \(total\_gold\) を出力します。

このアルゴリズムでは、各モンスターはスタックに最大1回追加され、最大1回取り出されるため、効率的に処理できます。

計算量

• 時間計算量: \(O(N)\)
  • 各モンスターはスタックに1回追加され、1回取り出されるため、全体で線形時間で処理できます。
• 空間計算量: \(O(N)\)
  • 最悪の場合、スタックに \(N\) 個のモンスターが積まれるため、線形の空間が必要です。

実装のポイント

• スタックにはモンスターの強さ \(D_i\) と報酬 \(V_i\) の組を保存します。

• 後回し解消処理は、モンスターを倒した直後と、全てのモンスターを訪れた後の2回行います。

• スタックの操作では、while stack: ループを使って、スタックの一番上を確認し、条件を満たす限り取り出し続けます。

• 入力の読み取りでは、一度に全てのデータを読み込んで処理することで効率化しています。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    D = []
    V = []
    index = 1
    for i in range(n):
        D.append(int(data[index]))
        V.append(int(data[index+1]))
        index += 2
        
    h = 0
    total_gold = 0
    stack = []
    
    for i in range(n):
        if D[i] > h:
            stack.append((D[i], V[i]))
        else:
            total_gold += V[i]
            h += D[i]
            while stack:
                top_d, top_v = stack[-1]
                if top_d <= h:
                    total_gold += top_v
                    h += top_d
                    stack.pop()
                else:
                    break
                    
    while stack:
        top_d, top_v = stack[-1]
        if top_d <= h:
            total_gold += top_v
            h += top_d
            stack.pop()
        else:
            break
            
    print(total_gold)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。