概要

左から順に部屋を処理し、「倒せるなら必ず倒す・倒せないならスキップ」というルールに従って進んだとき、スキップ回数に応じた罰金の合計を求める問題です。

考察

この問題のポイントは、選択の余地がないことです。各部屋で高橋君が取れる行動は次のどちらかしかありません。

• 現在の体力 \(stamina\) が \(H_i\) 以上なら、必ず倒す（体力は \(stamina \leftarrow stamina - H_i + P_i\) に更新）
• \(H_i\) 未満なら、倒せないので必ずスキップ（体力は変わらず、罰金対象のスキップ数が増える）

つまり、「どの部屋を倒す／スキップするかを最適化する」タイプではなく、シミュレーションするだけで結果が一意に決まる問題です。

素朴に見えても、やるべきことは各部屋について条件判定と体力更新を行うだけなので、\(N \le 2\times 10^5\) でも十分間に合います。逆に、無駄にDPや探索を考えると実装が複雑になるだけでなく、不要な計算で遅くなる可能性があります。

具体例：

• \(S=10\)
• 1部屋目 \((H_1,P_1)=(7,3)\)：\(10\ge 7\) なので倒す → 体力 \(10-7+3=6\)
• 2部屋目 \((H_2,P_2)=(8,0)\)：\(6<8\) なのでスキップ → スキップ数 \(+1\) 最終的にスキップ数 \(\times C\) が答えになります。

アルゴリズム

1. 体力 \(stamina \leftarrow S\)、スキップ数 \(skips \leftarrow 0\) で初期化する。
2. \(i=1\) から \(N\) まで順に部屋を処理する。
   • もし \(stamina \ge H_i\) なら倒し、\(stamina \leftarrow stamina - H_i + P_i\) と更新する。
   • そうでなければスキップし、\(skips \leftarrow skips + 1\) とする。
3. 最後に \(skips \times C\) を出力する。

計算量

• 時間計算量: \(O(N)\)（各部屋を1回ずつ処理）
• 空間計算量: \(O(1)\)（入力の保持を除けば、使用する変数は定数個）

実装のポイント

• \(N\) が大きいので、Pythonでは sys.stdin.buffer.read() でまとめて読み込み、整数列として処理すると高速です。
• 罰金は「スキップ回数 × \(C\)」なので、スキップしたタイミングで都度加算してもよいですが、最後にまとめて掛け算する方が分かりやすいです。
• 体力や罰金額は最大で \(10^9\) オーダーですが、Pythonの整数はオーバーフローしないので安心して扱えます。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, S, C = data[0], data[1], data[2]
    stamina = S
    skips = 0
    idx = 3
    for _ in range(N):
        H = data[idx]
        P = data[idx + 1]
        idx += 2
        if stamina >= H:
            stamina = stamina - H + P
        else:
            skips += 1
    print(skips * C)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。