概要

フリーマーケットで商品を売り、各取引ごとに売上の半分（切り捨て）を手数料として支払った後の最終的な所持金を求める問題です。

考察

この問題で重要なポイントは以下の通りです。

各取引の流れを正確に理解する

\(j\) 番目のお客さんが商品 \(T_j\) を \(Q_j\) 個買ったとき、売上金額は \(X = P_{T_j} \times Q_j\) 円です。このとき：

1. まず \(X\) 円を受け取る
2. その直後に \(\lfloor X / 2 \rfloor\) 円を手数料として支払う

つまり、1回の取引で手元に残る金額は \(X - \lfloor X / 2 \rfloor\) 円です。

具体例： 価格 \(300\) 円の商品を \(3\) 個購入された場合、\(X = 900\) 円です。手数料は \(\lfloor 900 / 2 \rfloor = 450\) 円なので、手元に残るのは \(900 - 450 = 450\) 円です。

もし \(X = 7\) 円（奇数）の場合は、手数料が \(\lfloor 7 / 2 \rfloor = 3\) 円なので、手元に残るのは \(7 - 3 = 4\) 円です。切り捨てにより、奇数のときは売上の半分より \(1\) 円多く手元に残ります。

素朴なアプローチで十分

この問題は \(M\) 回の取引を順番にシミュレーションするだけで解けます。\(M \leq 10^5\) なので、各取引を \(O(1)\) で処理すれば十分間に合います。特別なアルゴリズムは不要です。

注意：取引ごとに手数料を計算する必要がある

「全取引の合計売上をまとめてから手数料を引く」のではなく、取引ごとに \(\lfloor X / 2 \rfloor\) の切り捨てが発生します。切り捨ての回数が異なるため、まとめて計算すると答えが変わる可能性があります。

アルゴリズム

1. 初期所持金 \(S\) を変数 cash に設定する。
2. \(M\) 人のお客さんについて順番に以下を行う：
   • 売上金額 \(X = P_{T_j - 1} \times Q_j\) を計算する（商品番号は 1-indexed なので配列アクセス時に \(-1\) する）。
   • cash に \(X - \lfloor X / 2 \rfloor\) を加算する。
3. 最終的な cash を出力する。

計算量

• 時間計算量: \(O(N + M)\)（商品価格の読み込みに \(O(N)\)、取引の処理に \(O(M)\)）
• 空間計算量: \(O(N)\)（商品価格を保持する配列）

実装のポイント

• 商品番号 \(T_j\) は 1-indexed（1 から始まる）なので、配列アクセス時に P[t - 1] とする必要があります。

• 手数料の計算では 整数除算（切り捨て） を使います。Python では // 演算子が非負整数に対して切り捨て除算を行うため、x // 2 でそのまま正しく計算できます。

• 売上金額 \(X\) の最大値は \(P_i \times Q_j \leq 10^4 \times 10^4 = 10^8\) であり、所持金の最大値も \(10^9 + 10^5 \times 10^8\) 程度ですが、Python では整数のオーバーフローがないため特に気にする必要はありません（C++ 等では long long を使う必要があります）。

  ソースコード

N, M, S = map(int, input().split())
P = list(map(int, input().split()))
cash = S
for _ in range(M):
    t, q = map(int, input().split())
    x = P[t - 1] * q
    cash += x - x // 2
print(cash)

---

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