概要

\(N\) 種類の商品があるフリーマーケットにおいて、\(M\) 回の取引が行われた後の最終的な所持金を求める問題です。各取引ごとに売上の半分（小数点以下切り捨て）が手数料として差し引かれるため、取引ごとに正確に計算を行う必要があります。

考察

この問題を解くためのポイントは以下の3点です。

1. 取引ごとの計算: 手数料は「売上の合計」に対してではなく、「取引ごと」に発生します。例えば、5円の売上が2回あった場合、各取引で \(\lfloor 5/2 \rfloor = 2\) 円の手数料がかかり、手元に残るのは \((5-2) + (5-2) = 6\) 円です。これを合計売上10円に対して一度に計算すると \(\lfloor 10/2 \rfloor = 5\) 円の手数料となり、結果が変わってしまいます。問題文の「その場で支払う」「順番に処理される」という指示通りにシミュレーションする必要があります。

2. 制約と計算量: 商品の種類数 \(N\) とお客さんの数 \(M\) は最大 \(10^5\) です。1回の取引は定数時間 \(O(1)\) で計算できるため、全体で \(O(M)\) の計算量となります。これは実行時間制限内に十分間に合う計算量です。

3. 入力の高速化: Pythonでは input() を \(M\) 回呼び出すと、入力行数が多い場合に実行時間が長くなることがあります。sys.stdin.read().split() を使って一括で読み込むことで、高速に処理を行うことができます。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 初期の所持金 \(S\) を変数（例：current_cash）に格納します。
2. 各商品の価格 \(P_1, P_2, \ldots, P_N\) を配列（リスト）に格納します。このとき、商品番号は1から始まりますが、プログラミング言語の配列は0から始まることが多いため、インデックスの扱いに注意します（商品 \(T_j\) の価格は P[T_j - 1]）。
3. 各取引 \((T_j, Q_j)\) について、以下の計算を \(M\) 回繰り返します。
   • その取引の売上 \(X = P_{T_j} \times Q_j\) を計算する。
   • 手数料 \(F = \lfloor X / 2 \rfloor\) を計算する。
   • 所持金に \((X - F)\) を加算する。
4. 最終的な所持金を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 商品価格の読み込みに \(O(N)\)、取引の処理に \(O(M)\) かかります。
• 空間計算量: \(O(N + M)\)
  • 商品価格を保持する配列に \(O(N)\)、入力を一括で保持する場合に \(O(N + M)\) のメモリを使用します。

実装のポイント

• 整数除算: Pythonでは // 演算子を使うことで、小数点以下を切り捨てた整数除算（床関数 \(\lfloor \cdot \rfloor\)）を簡単に行えます。

• 1-indexedと0-indexed: 問題文の「\(T_j\) 番目の商品」を配列のインデックスとして使う際は、1を引いて P[T_j - 1] とする必要があります。

• 大きな数値: 最終的な所持金は \(10^9 + (10^5 \times 10^4 \times 10^4) = 10^{13}\) 程度になる可能性がありますが、Pythonは標準で多倍長整数をサポートしているため、オーバーフローを気にする必要はありません。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストに格納します
    # この方法は大量の入力を高速に処理するのに適しています
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 1行目のデータ（N: 商品の種類数, M: お客さんの人数, S: 初期の所持金）をパースします
    N = int(input_data[0])
    M = int(input_data[1])
    S = int(input_data[2])
    
    # 2行目のデータ（各商品の価格 P_1, P_2, ..., P_N）をパースします
    # 商品番号は1から始まりますが、リストの添字として扱うために0-indexedで管理します
    P = list(map(int, input_data[3:3+N]))
    
    # 現在の所持金を管理する変数（初期値は S 円）
    current_cash = S
    
    # 3行目以降の購入情報（T_j: 購入した商品の種類, Q_j: 購入個数）を順番に処理します
    # 購入情報は input_data の 3+N 番目の要素から始まります
    idx = 3 + N
    for _ in range(M):
        # 商品の種類 T_j と個数 Q_j を取得
        t_j = int(input_data[idx])
        q_j = int(input_data[idx+1])
        idx += 2
        
        # その取引での売上金額 X を計算します
        # T_j は1から始まるため、リスト P の添字は t_j - 1 となります
        sales = P[t_j - 1] * q_j
        
        # 手数料は売上の半分（小数点以下切り捨て）です
        # 最終的な手元の増加分は「売上 - 手数料」となります
        # Pythonの // 演算子は小数点以下切り捨ての整数除算を行います
        fee = sales // 2
        current_cash += (sales - fee)
        
    # すべての取引完了後の所持金を出力します
    print(current_cash)

if __name__ == '__main__':
    main()

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