概要

お店の会員割引制度を考慮しながら、\(M\) 件の購入記録それぞれの購入金額を計算し、その合計を求める問題です。

考察

この問題では、各購入記録ごとに以下を判定するだけでよいシンプルな問題です。

• 非会員（\(S_j = 0\)）の場合: 商品 \(P_j\) の定価 \(A_{P_j}\) をそのまま使う
• 会員（\(S_j = 1\)）の場合: 定価から \(K\) 円引いた価格を使うが、\(0\) 円未満にはならない

例えば、\(K = 30\) のとき： - 定価 \(100\) 円の商品 → 会員価格は \(\max(100 - 30, 0) = 70\) 円 - 定価 \(20\) 円の商品 → 会員価格は \(\max(20 - 30, 0) = 0\) 円（タダになる）

特別なアルゴリズムは不要で、\(M\) 件の記録を順番に処理して合計を求めれば十分です。素朴なアプローチでも制約（\(M \leq 10^5\)）の範囲内で余裕を持って間に合います。

アルゴリズム

1. \(N, M, K\) と商品の定価リスト \(A\) を読み込む。
2. 合計金額 total を \(0\) で初期化する。
3. \(M\) 件の購入記録を順に処理する：
   • 商品番号 \(P_j\) に対応する定価 \(A_{P_j}\) を取得する（配列は 0-indexed なので \(A[P_j - 1]\)）。
   • 会員（\(S_j = 1\)）なら、価格を \(\max(A_{P_j} - K,\ 0)\) に更新する。
   • 購入金額 \(= \text{price} \times D_j\) を total に加算する。
4. total を出力する。

具体例

入力例として \(N=3, M=2, K=30\)、定価が \([100, 50, 20]\) の場合を考えます。

合計: \(300 + 0 = 300\) 円

計算量

• 時間計算量: \(O(N + M)\)
  • 定価リストの読み込みに \(O(N)\)、\(M\) 件の購入記録の処理に \(O(M)\)
• 空間計算量: \(O(N)\)
  • 定価リスト \(A\) の保持に \(O(N)\)

実装のポイント

• 1-indexed と 0-indexed の変換: 商品番号は \(1\) から始まるが、Python のリストは \(0\) から始まるため、A[p - 1] とする必要があります。

• max 関数の利用: 会員割引で価格が負にならないよう max(price - K, 0) を使います。これを忘れると、定価が \(K\) より小さい商品で負の価格になり WA になります。

• 整数型の範囲: 答えは最大 \(10^{15}\) まであり得ますが、Python では整数のオーバーフローがないため特別な対策は不要です（C++ などでは long long が必要です）。

  ソースコード

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
total = 0
for _ in range(M):
    s, p, d = map(int, input().split())
    price = A[p - 1]
    if s == 1:
        price = max(price - K, 0)
    total += price * d
print(total)

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