概要

高橋君がフリーマーケットで商品を販売し、各取引ごとに売上の半分（小数点以下切り捨て）を手数料として支払う場合、最終的な所持金を求める問題です。

考察

この問題は、各取引を順番に処理していくだけで解くことができます。重要な点は、各取引ごとに以下の手順を正確に行うことです： 1. 商品の価格と購入個数から売上総額を計算 2. 売上総額を現在の所持金に加算 3. 売上総額の半分（小数点以下切り捨て）を手数料として支払う（所持金から減算）

制約条件から、商品数Nと取引数Mが最大10^5まで大きくなる可能性がありますが、各取引を単純に処理するだけなので、O(M)の計算量で十分高速に処理できます。

アルゴリズム

1. 入力データを読み込む（商品数N、取引数M、初期所持金S、各商品の価格リスト、各取引情報）
2. 初期所持金Sをcurrent変数に設定
3. 各取引についてループ処理：
   • 取引情報から商品番号Tと購入個数Qを取得
   • 商品番号から価格Pを取得
   • 売上総額 = P × Q を計算
   • currentに売上総額を加算
   • 手数料 = 売上総額 ÷ 2（小数点以下切り捨て）を計算
   • currentから手数料を減算
4. 最終的なcurrentの値を出力

計算量

• 時間計算量: \(O(M)\)
  • M回の取引をそれぞれ定数時間で処理するため
• 空間計算量: \(O(N + M)\)
  • 商品価格のリスト（サイズN）と取引情報のリスト（サイズM）を保持するため

実装のポイント

• 商品番号は1-indexedで与えられるため、配列アクセス時にt-1でインデックス調整が必要

• 手数料の計算では小数点以下を切り捨てるため、整数除算//を使用

• 大規模な入力に対応するため、sys.stdin.read()で一括読み込みを行う

• 各取引を順番に処理するだけでよく、特別なデータ構造やアルゴリズムは不要

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    S = int(data[2])
    prices = list(map(int, data[3:3+n]))
    transactions = []
    index = 3 + n
    for i in range(m):
        t = int(data[index])
        q = int(data[index+1])
        index += 2
        transactions.append((t, q))
    
    current = S
    for t, q in transactions:
        price = prices[t-1]
        total_sale = price * q
        current += total_sale
        fee = total_sale // 2
        current -= fee
        
    print(current)

if __name__ == "__main__":
    main()

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