概要

初期残高から始まり、お金が増減する \(M\) 回のイベントを順番にシミュレーションして理論上の最終残高を求め、実際の残高との差額を計算する問題です。

考察

この問題は、問題文の指示通りにイベントを1つずつ順番に処理していくシミュレーションを行うことで解くことができます。

イベントの回数 \(M\) は最大で \(2 \times 10^5\) 回です。1回のイベント処理は足し算や掛け算といった単純な計算のみで行えるため、\(O(1)\) の時間で処理できます。したがって、全体を順番に処理しても \(O(M)\) の計算量となり、実行時間制限に余裕で間に合います。

気を付けるべきポイントは金額の大きさ（オーバーフロー）です。 初期残高 \(S\) は最大 \(10^9\)、入会金 \(v_i\) も最大 \(10^9\) です。仮に \(2 \times 10^5\) 回のイベントがすべて入会金 \(10^9\) 円のイベントだった場合、最終残高は \(10^9 + (2 \times 10^5) \times 10^9 \approx 2 \times 10^{14}\) 円に達します。 Pythonでは自動的に桁数の大きい整数が扱えるため問題ありませんが、C++やJavaなどの言語を使用する場合は、32ビット整数型（int）の上限（約 \(2 \times 10^9\)）を超えてしまうため、64ビット整数型（long long など）を使う必要があります。

アルゴリズム

1. 現在の残高を表す変数（例: current_balance）を用意し、初期残高 \(S\) を代入します。
2. \(M\) 回のイベントについて、順番に以下の処理を行います。
   • \(e_i = 1\)（入会イベント）のとき：current_balance に \(v_i\) を足します。
   • \(e_i = 2\)（購入イベント）のとき：current_balance から \(v_i \times P\) を引きます。
3. すべてのイベントを処理し終えたあとの current_balance の値が「理論値」となります。
4. 最後に current_balance - R を計算し、出力します。

計算量

• 時間計算量: \(O(M)\)
  • \(M\) 回のイベントに対してそれぞれ \(O(1)\) で四則演算を行うため、全体の処理時間は \(O(M)\) となります。
• 空間計算量: \(O(M)\)
  • 正解コードのように sys.stdin.read().split() を用いて入力全体を一度にメモリ上に読み込む場合、\(O(M)\) の空間を消費します。（言語や実装方法によっては逐次読み込みを行うことで \(O(1)\) に抑えることも可能です）

実装のポイント

• 高速な入出力の利用: 入力される数値の個数が \(2 \times 10^5\) 個以上と多いため、Pythonの場合は input() をループの中で何度も呼び出すと実行時間が遅くなる可能性があります。正解コードのように sys.stdin.read().split() を使って入力を一括で読み込むと、高速に処理できます。

• データ型の選択: 考察で述べた通り、他言語で実装する際は残高を管理する変数に64ビット整数型（long long など）を使用してください。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    S = int(input_data[0])
    P = int(input_data[1])
    R = int(input_data[2])
    M = int(input_data[3])
    
    current_balance = S
    idx = 4
    for _ in range(M):
        e = int(input_data[idx])
        v = int(input_data[idx+1])
        idx += 2
        
        if e == 1:
            current_balance += v
        elif e == 2:
            current_balance -= v * P
            
    print(current_balance - R)

if __name__ == '__main__':
    solve()

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