概要

各購入記録について「1個あたりの実際の価格」を求め、それに購入個数を掛けて合計していく問題です。
商品ごとの定価 \(A_i\) と、会員なら \(K\) 円引き（ただし \(0\) 円未満にはしない）という条件を、そのまま素直に計算すれば解けます。

考察

この問題で必要なのは、各購入記録ごとに購入金額を正しく計算することです。

購入記録 \((S_j, P_j, D_j)\) に対して、

• 商品番号は \(P_j\)
• 定価は \(A_{P_j}\)
• 非会員（\(S_j = 0\)）なら 1 個あたり \(A_{P_j}\) 円
• 会員（\(S_j = 1\)）なら 1 個あたり \(\max(A_{P_j} - K, 0)\) 円

なので、その記録の購入金額は

• 非会員なら \(A_{P_j} \times D_j\)
• 会員なら \(\max(A_{P_j} - K, 0) \times D_j\)

です。これを全記録について足し合わせれば答えになります。

重要な観察

購入個数 \(D_j\) は最大 \(10^5\) ですが、1個ずつシミュレーションする必要はありません。
1 個あたりの価格が分かっているので、まとめて

\[ \text{価格} \times D_j \]

と計算すれば十分です。

素朴すぎる方法がまずい理由

たとえば「\(D_j\) 個買ったなら、1 個ずつループして合計する」という実装をすると、購入個数の総和が非常に大きくなる可能性があり、無駄に遅くなります。
この問題では各記録を 1 回ずつ見るだけでよいので、記録単位で計算するのが重要です。

具体例

たとえば、

• \(A_3 = 100\)
• \(K = 30\)
• 記録が \((S, P, D) = (1, 3, 4)\)

なら、会員なので 1 個あたりの価格は

\[ \max(100 - 30, 0) = 70 \]

よって購入金額は

\[ 70 \times 4 = 280 \]

です。

また、もし \(A_3 = 20\) なら

\[ \max(20 - 30, 0) = 0 \]

となり、購入金額は \(0 \times 4 = 0\) 円です。
この「\(0\) 円未満にならない」という条件を忘れないようにしましょう。

アルゴリズム

1. 商品の定価配列 \(A\) を読み込む。
2. 合計金額 total を \(0\) で初期化する。
3. 各購入記録について次を行う。
   • \(S, P, D\) を読む
   • \(S = 0\) なら 1 個あたりの価格は \(A_P\)
   • \(S = 1\) なら 1 個あたりの価格は \(\max(A_P - K, 0)\)
   • price * D を total に加える
4. 最後に total を出力する。

この方法なら、すべての記録を 1 回ずつ処理するだけで済みます。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 商品番号は \(1\) から \(N\) なので、実装では A を長さ N + 1 の配列にして 1-indexed で持つと扱いやすいです。
• 会員価格は必ず

$\( \max(A[P] - K, 0) \)$

として、負の値にならないようにします。 - 合計金額は大きくなるので、整数型の扱いに注意します。Python なら自動で大きな整数を扱えるため安心です。 - 提出コードでは sys.stdin.buffer.read() を使ってまとめて入力を読み、高速に処理しています。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)
    K = next(it)

    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = next(it)

    total = 0
    for _ in range(M):
        S = next(it)
        P = next(it)
        D = next(it)
        price = A[P] if S == 0 else max(A[P] - K, 0)
        total += price * D

    print(total)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。