概要

ダンジョンの部屋を左から順に訪れ、体力が足りればモンスターを倒し、足りなければスキップする単純なシミュレーション問題です。スキップした部屋の数に罰金単価 \(C\) を掛けた値を出力します。

考察

この問題のポイントは、高橋君の行動に選択の余地がないことです。

• 部屋は左から順に処理する（順番は固定）
• 倒せるモンスターは必ず倒す（倒すかどうかの判断は不要）
• 倒せないモンスターがいる部屋は必ずスキップする

つまり、貪欲法や動的計画法のような高度なアルゴリズムは不要で、問題文に書かれたルール通りに左から順番にシミュレーションするだけで正解が得られます。

具体例で確認

例えば \(N = 3, S = 10, C = 5\) で、各部屋が \((H, P) = (8, 3), (7, 2), (4, 1)\) の場合：

スキップ数は \(1\) なので、罰金は \(1 \times 5 = 5\) となります。

アルゴリズム

1. 現在の体力 hp を初期体力 \(S\) に設定し、スキップ回数 skip_count を \(0\) に設定する。
2. 部屋 \(i = 1, 2, \ldots, N\) を順に処理する：
   • hp \(\geq H_i\) なら、モンスターを倒す：hp \(\leftarrow\) hp \(- H_i + P_i\)
   • hp \(< H_i\) なら、スキップ：skip_count \(\leftarrow\) skip_count \(+ 1\)
3. 最終的な罰金 skip_count \(\times C\) を出力する。

計算量

• 時間計算量: \(O(N)\) — 各部屋を \(1\) 回ずつ処理するだけ
• 空間計算量: \(O(1)\) — 体力とスキップ回数の変数のみ（入力の読み込みを除く）

実装のポイント

• 体力の値が非常に大きくなる可能性：\(S\) は最大 \(10^9\)、\(P_i\) も最大 \(10^9\) で \(N\) は最大 \(2 \times 10^5\) なので、体力は最大で \(10^9 + 2 \times 10^5 \times 10^9 \approx 2 \times 10^{14}\) 程度になり得ます。Python では整数のオーバーフローは起きませんが、C++ などでは long long を使う必要があります。
• 高速な入力：\(N\) が最大 \(2 \times 10^5\) のため、Python では sys.stdin.buffer.read() でまとめて読み込むことで入力の高速化を図っています。
• 罰金の計算：スキップ数を数えてから最後にまとめて \(C\) を掛ける方が、毎回加算するよりシンプルです。

ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    S = int(input_data[idx]); idx += 1
    C = int(input_data[idx]); idx += 1
    
    skip_count = 0
    hp = S
    
    for i in range(N):
        H = int(input_data[idx]); idx += 1
        P = int(input_data[idx]); idx += 1
        
        if hp >= H:
            hp = hp - H + P
        else:
            skip_count += 1
    
    print(skip_count * C)

main()

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