概要

ダンジョンの部屋を順番に訪れ、モンスターを倒せるかどうかを現在の体力に基づいて判定し、スキップした部屋の数に応じた罰金を計算する問題です。

考察

問題のルールはシンプルで、各部屋で現在の体力がモンスターの強さ \(H_i\) 以上なら倒して体力を更新し、そうでなければスキップして罰金 \(C\) を加算します。重要な点は、モンスターを倒した後の体力の更新が \(現在の体力 - H_i + P_i\) となることです。この問題は、各ステップで単純に条件判定と状態更新を行うだけで解くことができます。制約条件が \(N \leq 2 \times 10^5\) と大きいですが、各ステップの処理が定数時間で実行できるため、線形時間のアルゴリズムで十分です。

アルゴリズム

1. 初期体力 \(S\) と罰金 \(0\) で開始します。
2. 各部屋 \(i\) について順番に処理します：
   • 現在の体力が \(H_i\) 以上なら、体力を \(現在の体力 - H_i + P_i\) に更新します。
   • そうでなければ、罰金に \(C\) を加算します（スキップ）。
3. すべての部屋を処理した後の罰金の合計を出力します。

このアルゴリズムは、問題で指定された通りの処理を愚直にシミュレートするものです。各ステップで体力が更新されるため、次の部屋の判定は更新後の体力に基づいて行われます。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の部屋を1回ずつ処理するため。
• 空間計算量: \(O(N)\)
  • \(H\) と \(P\) の配列を保持するため。

実装のポイント

• 入力の読み込みでは、一度にすべてのデータを読み込んでから処理することで効率化しています。
• 現在の体力を保持する変数を更新しながら、各ルームで条件分岐を行うだけのシンプルな実装です。
• 整数のオーバーフローを心配する必要はありません（Pythonの整数は任意精度のため）。

ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    S = int(data[1])
    C = int(data[2])
    H = []
    P = []
    index = 3
    for i in range(n):
        H.append(int(data[index]))
        P.append(int(data[index+1]))
        index += 2
        
    current_health = S
    penalty = 0
    
    for i in range(n):
        if current_health >= H[i]:
            current_health = current_health - H[i] + P[i]
        else:
            penalty += C
            
    print(penalty)

if __name__ == "__main__":
    main()

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