概要

高橋君が一列に並んだ \(N\) 個の部屋を左から順に探索し、体力が足りなければ部屋をスキップして罰金を支払います。すべての部屋を処理した後の罰金の合計を求めます。

考察

この問題では、高橋君が左から順に部屋を訪問し、それぞれのモンスターに対応する行動（倒す or スキップ）を決定していきます。各モンスターに対して：

• 現在の体力 \(current\_hp\) がモンスターの強さ \(H_i\) 以上であれば、そのモンスターを倒す。
  • 体力は \(current\_hp = current\_hp - H_i + P_i\) に更新される。
• そうでなければ、その部屋をスキップし、罰金 \(C\) を加算する。

重要なポイントは「順番に処理する」ことであり、過去に戻ったり選択肢があるわけではないため、単純なシミュレーションで解けます。

素朴なアプローチでも特に難しいことはなく、入力を順に読みながら処理すればよいですが、入力の受け取り方によってはTLEになることがあります。特にPythonでは、input() を使うと遅いため、高速な入力方法（例：sys.stdin.read）を使う必要があります。

アルゴリズム

1. 入力を一度に読み込み、\(N\), \(S\), \(C\), 各部屋の \(H_i\), \(P_i\) を取得します。
2. 初期体力 \(current\_hp = S\)、罰金合計 \(penalty = 0\) とします。
3. 左から順に各部屋について以下を実行：
   • 現在の体力が \(H_i\) 以上なら、
     • \(current\_hp \leftarrow current\_hp - H_i + P_i\)
   • そうでないなら、
     • \(penalty \leftarrow penalty + C\)
4. 最終的な \(penalty\) の値を出力します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• Pythonでは大量の入力を扱う場合、sys.stdin.read を用いて高速化する。
• 入力は文字列としてまとめて読み込まれるので、適切に分割・型変換を行う必要がある。
• 特に大きな値（例：\(10^9\)オーダー）を取り扱うので、int型の範囲に注意。

ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    S = int(data[1])
    C = int(data[2])
    
    H = [0] * N
    P = [0] * N
    
    for i in range(N):
        H[i] = int(data[3 + 2*i])
        P[i] = int(data[4 + 2*i])
    
    penalty = 0
    current_hp = S
    
    for i in range(N):
        if current_hp >= H[i]:
            current_hp -= H[i]
            current_hp += P[i]
        else:
            penalty += C
    
    print(penalty)

if __name__ == "__main__":
    main()

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