概要

町内会の活動資金について、初期残高にすべてのイベント（入会金の加算・飲料水購入の減算）を順番に反映させた理論上の最終残高を求め、実際の残高 \(R\) との差額を計算する問題です。

考察

この問題で求めるべきものは次の2ステップに分かれます。

1. 理論値の計算: 初期残高 \(S\) に対して \(M\) 回のイベントを順に処理し、最終的な残高を求める。
2. 差額の計算: 理論値から実際の残高 \(R\) を引く。

各イベントは以下のように処理します：

• 入会イベント (\(e_i = 1\)): 入会金 \(v_i\) 円がそのまま加算される。
• 購入イベント (\(e_i = 2\)): 飲料水 \(v_i\) 本を購入するので、\(v_i \times P\) 円が減算される。

例えば、\(S = 10000\), \(P = 150\), \(R = 9000\) で、以下のイベントがあったとします：

理論値は \(13500\) 円、差額は \(13500 - 9000 = 4500\) 円となります。

特別なアルゴリズムは不要で、問題文の指示どおりにシミュレーションすれば正解が得られます。ただし、値の範囲に注意が必要です。

アルゴリズム

1. 変数 balance を初期残高 \(S\) で初期化する。
2. \(M\) 回のイベントを順に読み込み、それぞれ以下のように処理する：
   • \(e_i = 1\) なら balance += v_i（入会金の加算）
   • \(e_i = 2\) なら balance -= v_i * P（飲料水の購入費の減算）
3. 最終的な balance が理論値なので、balance - R を出力する。

計算量

• 時間計算量: \(O(M)\) — 各イベントを1回ずつ処理するだけです。
• 空間計算量: \(O(1)\) — 残高を保持する変数のみで、イベント情報を保存する必要はありません。

実装のポイント

• オーバーフローに注意: \(S\) は最大 \(10^9\)、入会金も最大 \(10^9\) で \(M\) は最大 \(2 \times 10^5\) 回あるため、理論値は最大で約 \(10^9 + 2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) 程度になり得ます。また \(R\) は最大 \(10^{18}\) です。C++ などでは long long 型を使う必要がありますが、Python では整数のオーバーフローがないため、そのまま計算できます。

• 購入イベントの計算: 購入本数 \(v_i\) に単価 \(P\) を掛ける必要があります。\(v_i\) がそのまま金額ではない点を見落とさないようにしましょう。

  ソースコード

S, P, R = map(int, input().split())
M = int(input())
balance = S
for _ in range(M):
    e, v = map(int, input().split())
    if e == 1:
        balance += v
    else:
        balance -= v * P
print(balance - R)

この解説は claude4.6opus-thinking によって生成されました。