概要

各備品について「実際の価格 - 古い価格表の価格」の差額を事前計算しておき、各部署の購入申請に対して該当する備品の差額を合計する問題です。

考察

問題の本質を理解する

各部署について求めたい値は以下の式です： $\(\sum_{k=1}^{K_j} (P_{C_{j,k}} - Q_{C_{j,k}})\)$

これは「購入希望の各備品について、実際の価格と古い価格表の価格の差を全て足し合わせる」ということです。

重要な気づき

\(P_{C_{j,k}} - Q_{C_{j,k}}\) の部分は、備品の番号 \(C_{j,k}\) だけで決まる値です。つまり、備品 \(i\) に対する差額 \(D_i = P_i - Q_i\) を一度計算しておけば、何度でも再利用できます。

素朴なアプローチの問題点

もし毎回 \(P_i\) と \(Q_i\) を別々に参照して引き算を行っても計算量は変わりませんが、差額 \(D_i\) を事前計算しておくことで： - コードがシンプルになる - 配列アクセスの回数が減る（2回→1回）

という利点があります。

入力サイズの確認

• \(N, M \leq 10^5\)
• \(\sum_{j=1}^{M} K_j \leq 2 \times 10^5\)（全部署の購入希望数の合計）

全ての購入希望を愚直に処理しても、合計で \(2 \times 10^5\) 回程度の処理なので十分高速です。

アルゴリズム

1. 入力を読み込む：備品の実際の価格 \(P_i\) と古い価格表の価格 \(Q_i\) を読み込む

2. 差額の事前計算：各備品 \(i\) について、差額 \(D_i = P_i - Q_i\) を計算して配列に保存する

3. 各部署の申請を処理：

   • \(j\) 番目の部署について、購入希望の備品番号 \(C_{j,1}, C_{j,2}, \ldots, C_{j,K_j}\) を読み込む
   • 対応する差額 \(D_{C_{j,1}}, D_{C_{j,2}}, \ldots, D_{C_{j,K_j}}\) を合計する
   • 結果を出力用リストに追加

4. 結果を出力：全ての部署の結果をまとめて出力する

具体例

入力例：\(N=3\), \(P = [100, 200, 300]\), \(Q = [90, 220, 300]\) の場合

差額配列：\(D = [10, -20, 0]\)

部署が備品 \(1, 2\) を購入希望なら、答えは \(D_1 + D_2 = 10 + (-20) = -10\)

計算量

• 時間計算量: \(O(N + \sum_{j=1}^{M} K_j)\)

  • 差額配列の事前計算に \(O(N)\)
  • 全部署の購入申請処理に \(O(\sum_{j=1}^{M} K_j)\)
  • 制約より、全体で \(O(N + 2 \times 10^5) = O(N + M)\) 程度

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

  • 価格配列 \(P, Q\) と差額配列 \(D\) に \(O(N)\)
  • 結果を格納する配列に \(O(M)\)

実装のポイント

1. 1-indexed の配列：備品番号が \(1\) から \(N\) なので、配列サイズを \(N+1\) にして 1-indexed でアクセスすると分かりやすい

2. 高速な入力：sys.stdin.read() で一括読み込みし、split() で分割することで、大量の入力を高速に処理できる

3. 出力のまとめ出力：結果をリストに貯めておき、最後に '\n'.join() でまとめて出力することで、出力の高速化が図れる

4. 負の値に注意：\(P_i < Q_i\) の場合、差額は負になる。問題文にも「負になることもあります」と明記されている

   ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    
    N = int(input_data[idx])
    M = int(input_data[idx + 1])
    idx += 2
    
    P = [0] * (N + 1)
    Q = [0] * (N + 1)
    
    for i in range(1, N + 1):
        P[i] = int(input_data[idx])
        idx += 1
    
    for i in range(1, N + 1):
        Q[i] = int(input_data[idx])
        idx += 1
    
    # 差額を事前計算: D[i] = P[i] - Q[i]
    D = [0] * (N + 1)
    for i in range(1, N + 1):
        D[i] = P[i] - Q[i]
    
    results = []
    for _ in range(M):
        K = int(input_data[idx])
        idx += 1
        
        diff_sum = 0
        for _ in range(K):
            c = int(input_data[idx])
            idx += 1
            diff_sum += D[c]
        
        results.append(diff_sum)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

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