概要

\(N\) 種類の商品と \(M\) 件の購入記録が与えられたとき、会員割引（\(1\) 個あたり \(K\) 円引き、最低 \(0\) 円）を考慮して、すべての売上の合計金額を求める問題です。

考察

この問題で重要な点は、「会員かどうかに応じて \(1\) 個あたりの価格を正しく計算すること」と「大量のデータを効率よく処理すること」の 2 点です。

1. 価格の計算

会員が商品 \(i\)（定価 \(A_i\)）を購入する場合、価格は \(A_i - K\) 円となります。ただし、問題文に「定価以上の割引にはならず、価格は \(0\) 円未満にはなりません」とあるため、もし \(A_i - K\) がマイナスになる場合は \(0\) 円として扱う必要があります。 これは数式で表すと \(\max(A_i - K, 0)\) となります。

2. 効率的な処理

制約を見ると、商品の種類数 \(N\) は最大 \(2 \times 10^5\)、記録の件数 \(M\) は最大 \(10^5\) と非常に大きいです。 各購入記録に対して、以下の手順を繰り返すことで答えが得られます。 1. 商品番号 \(P_j\) から定価 \(A_{P_j}\) を特定する（配列を使って \(O(1)\) で取得可能）。 2. 会員フラグ \(S_j\) を見て、単価を決定する。 3. 「単価 \(\times\) 個数 \(D_j\)」を合計金額に加算する。

この処理は 1 回あたり定数時間で終わるため、全体で \(O(N + M)\) の計算量となり、制限時間内に十分間に合います。

アルゴリズム

1. 商品の定価 \(A_1, A_2, \ldots, A_N\) を配列（Python ではリスト）に格納します。このとき、商品番号 \(1 \sim N\) を配列のインデックス \(0 \sim N-1\) に対応させると管理しやすくなります。
2. 合計金額を保持する変数 total_sales を \(0\) で初期化します。
3. \(M\) 件の購入記録を 1 つずつ読み込みます。
   • 会員 (\(S_j = 1\)) の場合：単価 \(v = \max(A_{P_j} - K, 0)\)
   • 非会員 (\(S_j = 0\)) の場合：単価 \(v = A_{P_j}\)
   • total_sales に \(v \times D_j\) を加算します。
4. 最終的な total_sales を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 定価の読み込みに \(O(N)\)、購入記録の処理に \(O(M)\) かかります。各記録の処理は定数時間で行えます。
• 空間計算量: \(O(N)\)
  • 商品の定価を保存するために長さ \(N\) の配列が必要です。

実装のポイント

• 高速な入出力: \(N\) や \(M\) が大きいため、Python では input() を繰り返すよりも sys.stdin.read().split() などを使って一括で入力を取得するほうが実行時間を短縮できます。

• 大きな数値の扱い: 答えは最大で \(10^{15}\) に達しますが、Python は標準で多倍長整数（いくらでも大きな整数）を扱えるため、オーバーフローを気にせずそのまま計算できます。

• インデックスの調整: 問題文の商品番号は \(1\) から始まりますが、プログラミング言語の配列は通常 \(0\) から始まります。A[p - 1] のようにインデックスを \(1\) 減らしてアクセスする必要があります。

  ソースコード

import sys

def solve():
    # 入力をすべて一括で読み込み、スペースや改行で分割してリストにします。
    # 大量の入力を効率的に処理するために sys.stdin.read().split() を使用します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用して各値を順番に取得します。
    it = iter(input_data)
    
    # N: 商品の種類数, M: 購入記録の件数, K: 会員の割引額
    N = int(next(it))
    M = int(next(it))
    K = int(next(it))
    
    # A: 各商品の定価リスト (商品番号 i は A[i-1] に対応)
    A = [int(next(it)) for _ in range(N)]
    
    total_sales = 0
    
    # M 件の購入記録を順番に処理します。
    for _ in range(M):
        s = int(next(it)) # 会員かどうか (1: 会員, 0: 非会員)
        p = int(next(it)) # 購入した商品の番号 (1-indexed)
        d = int(next(it)) # 購入した個数
        
        # 定価を取得
        price = A[p - 1]
        
        if s == 1:
            # 会員の場合、1個あたりの価格は max(定価 - K, 0)
            member_price = price - K
            if member_price < 0:
                member_price = 0
            total_sales += member_price * d
        else:
            # 非会員の場合、1個あたりの価格は定価どおり
            total_sales += price * d
            
    # すべての購入記録の合計金額を出力します。
    # Pythonは標準で多倍長整数をサポートしているため、10^15のような大きな値も扱えます。
    print(total_sales)

if __name__ == '__main__':
    solve()

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