概要

\(N\) 個の部屋を順番に訪れ、現在の体力がモンスターの強さ以上なら「戦う」、足りなければ「スキップして罰金を払う」というルールに従ってシミュレーションを行い、最終的な罰金の合計額を求める問題です。

考察

この問題で最も重要な点は、「倒せるモンスターは必ず倒し、倒せない場合のみスキップする」 というルールが固定されていることです。高橋君が「あえて倒せるモンスターをスキップする」といった選択の余地がないため、左端の部屋から順番に条件分岐（if文）を用いてシミュレーションを行うだけで正解を導き出すことができます。

注意すべき点は以下の通りです： - 数値の大きさ: 体力 \(S\) や罰金 \(C\)、モンスターの強さ \(H_i\) などは最大 \(10^9\) と非常に大きな値になります。罰金の合計額は \(N \times C\) となり、最大で \(2 \times 10^{14}\) 程度に達する可能性があります。Pythonは標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。 - 計算量: 部屋の数 \(N\) が最大 \(2 \times 10^5\) であるため、各部屋の処理を \(O(1)\) で行い、全体で \(O(N)\) の計算量に収める必要があります。

アルゴリズム

単純なシミュレーション（逐次処理）を用います。

1. 現在の体力を \(current\_stamina = S\)、罰金の合計を \(total\_penalty = 0\) と初期化します。
2. 部屋 \(i = 1, 2, \dots, N\) について、以下の処理を順番に行います。
   • もし \(current\_stamina \geq H_i\) ならば（モンスターを倒せる場合）：
     • 体力を消費し、その後に回復する： \(current\_stamina = current\_stamina - H_i + P_i\)
   • そうでなければ（モンスターを倒せない場合）：
     • 罰金を加算する： \(total\_penalty = total\_penalty + C\)
     • 体力は変化しません。
3. すべての部屋を処理し終えた後、 \(total\_penalty\) を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の部屋を一度ずつ走査し、各部屋で定数時間の比較と加減算を行うため、部屋の数に比例した時間で終了します。
• 空間計算量: \(O(N)\)
  • 入力値をすべてリストとして読み込む場合、 \(N\) に比例したメモリを使用します。

実装のポイント

• 高速な入出力: Pythonで \(N=2 \times 10^5\) 程度の入力を扱う場合、input() を繰り返すと実行時間が長くなることがあります。sys.stdin.read().split() を使って一括で読み込み、イテレータ（iter()）で処理することで、効率的にデータを取得できます。
• シミュレーションの忠実な再現: 問題文にある「\(H_i\) を引いた後 \(P_i\) を加える」という手順をそのままコードに落とし込みます。途中で体力がマイナスになることは（条件分岐により）ありませんが、回復量 \(P_i\) によって体力が初期値 \(S\) を超える可能性がある点に注意してください（本問題では上限の指定がないため、そのまま計算して問題ありません）。

ソースコード

import sys

def solve():
    """
    ダンジョン探索の問題を解く関数です。
    各部屋のモンスターを順番に判定し、体力が足りれば倒し、
    足りなければスキップして罰金を加算します。
    """
    
    # 標準入力からすべての入力を読み込み、空白や改行で分割してトークンのリストを作成します。
    # 大量の入力を効率的に処理するために sys.stdin.read().split() を使用します。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は何もせず終了します。
    if not input_data:
        return
    
    # トークンを順番に取り出すためのイテレータを作成します。
    it = iter(input_data)
    
    # 最初の3つの値（部屋の数 N、初期体力 S、スキップの罰金 C）を取得します。
    try:
        n = int(next(it))
        s = int(next(it))
        c = int(next(it))
    except (StopIteration, ValueError):
        return
    
    # 現在の体力を初期体力 S で初期化します。
    current_stamina = s
    # 罰金の合計額を 0 で初期化します。
    total_penalty = 0
    
    # N 個の部屋を順番に処理します。
    for _ in range(n):
        try:
            # 各モンスターの強さ H と倒した後の回復量 P を取得します。
            h = int(next(it))
            p = int(next(it))
        except (StopIteration, ValueError):
            break
            
        # 現在の体力がモンスターの強さ H 以上であれば倒すことができます。
        if current_stamina >= h:
            # モンスターを倒すと体力が H 減り、その後 P 回復します。
            current_stamina = current_stamina - h + p
        else:
            # 体力が足りない場合は部屋をスキップし、罰金 C を支払います。
            # このとき体力は変化しません。
            total_penalty += c
            
    # 全ての部屋を処理した後の罰金の合計額を出力します。
    print(total_penalty)

if __name__ == "__main__":
    # プログラムの実行を開始します。
    solve()

この解説は gemini-3-flash-thinking によって生成されました。