概要

この問題は、初期残高S円から始まる活動資金に対して、入会金の入金と飲料水の購入という2種類のイベントを順番に処理した理論値と実際の残高Rの差額を求める問題です。

考察

問題の本質は非常にシンプルで、与えられたイベントを順番に処理して最終的な理論値を計算し、実際の残高Rとの差を求めるだけです。イベントの数Mが最大200,000回と多いですが、各イベントの処理は単純な加算・減算のみであるため、単純にシミュレーションするだけで十分高速に計算できます。

制約条件として「理論値 ≥ R」が保証されているため、計算結果が負になる心配はありません。また、各イベント処理後の残高が負にならないことも保証されているため、オーバーフローなどのエラーを気にする必要もありません。

アルゴリズム

1. 初期残高Sを理論値の初期値として設定
2. 各イベントを順番に処理：
   • 入会イベント（\(e_i = 1\)）の場合：理論値に \(v_i\) を加算
   • 購入イベント（\(e_i = 2\)）の場合：理論値から \(v_i \times P\) を減算
3. すべてのイベントを処理した後の理論値から実際の残高Rを引き、差額を出力

計算量

• 時間計算量: \(O(M)\)（M回のイベントをそれぞれ定数時間で処理するため）
• 空間計算量: \(O(M)\)（イベント情報を保存するためのメモリ使用量）

実装のポイント

• 標準入力からデータを一括で読み込み、効率的に処理する

• イベントの種類（\(e_i\)）に応じて適切な計算を行う

• 各イベント処理は単純な加算・減算のみで、複雑なデータ構造は不要

• 理論値と実際の残高Rの差を正しく計算する

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    S = int(data[0])
    P = int(data[1])
    R = int(data[2])
    M = int(data[3])
    
    index = 4
    events = []
    for i in range(M):
        e = int(data[index])
        v = int(data[index+1])
        index += 2
        events.append((e, v))
        
    total = S
    for e, v in events:
        if e == 1:
            total += v
        else:
            total -= v * P
            
    result = total - R
    print(result)

if __name__ == "__main__":
    main()

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