概要

\(N\) 種類の備品について、実際の価格 \(P_i\) と古い価格表の価格 \(Q_i\) が与えられます。\(M\) 個の部署ごとに指定された備品リストを購入した際の「実際の合計金額」と「見積もり合計金額」の差額を求める問題です。

考察

各部署が求める値は、購入する備品の番号を \(C_1, C_2, \ldots, C_K\) とすると、以下の式で表されます。 $\(\sum_{k=1}^{K} (P_{C_k} - Q_{C_k})\)$

この式をよく見ると、各備品 \(i\) について、「実際の価格と見積もり価格の差」をあらかじめ計算しておくことで、計算を簡略化できることがわかります。

1. 差額の事前計算: 各備品 \(i\) について、 \(D_i = P_i - Q_i\) を計算しておきます。
2. クエリへの回答: 部署 \(j\) の差額の合計は、単に \(\sum_{k=1}^{K_j} D_{C_{j,k}}\) となります。

例えば、備品 1 の価格が \(P_1=100, Q_1=80\) なら \(D_1=20\) です。備品 2 が \(P_2=50, Q_2=60\) なら \(D_2=-10\) です。これら両方を購入する場合、合計の差額は \(20 + (-10) = 10\) となり、個別に引き算をしてから足すのと結果は変わりません。

制約と効率

• \(N, M\) は最大 \(10^5\)、さらに全部署の購入備品数の合計 \(\sum K_j\) は \(2 \times 10^5\) です。
• 部署ごとに毎回 \(P_i - Q_i\) を計算しても間に合いますが、あらかじめ \(D_i\) を配列に持っておくことで、各クエリでは配列の値を参照して足すだけの処理（\(O(K_j)\)）になり、非常に高速に動作します。
• 入出力のデータ量が多いため、Pythonでは標準の input() ではなく sys.stdin.read などを用いた高速な入出力処理が推奨されます。

アルゴリズム

1. 長さ \(N\) の配列 \(D\) を用意し、\(D_i = P_i - Q_i\) を計算して格納する。
2. \(M\) 個の部署について以下の処理を繰り返す：
   • 入力される \(K_j\) 個の備品番号 \(C_{j,k}\) を読み取る。
   • 各番号に対応する差額 \(D_{C_{j,k}}\) を合計する。
   • 合計値を出力する。

計算量

• 時間計算量: \(O(N + \sum K_j)\)
  • 差額の事前計算に \(O(N)\) かかります。
  • 全部署のクエリ処理には、合計で \(\sum K_j\) 回の加算を行うため \(O(\sum K_j)\) かかります。
  • 全体として入力サイズに対して線形時間で処理可能です。
• 空間計算量: \(O(N)\)
  • 価格や差額を保存するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 1-indexedへの対応: 問題文の備品番号は \(1\) から \(N\) ですが、プログラムの配列は通常 \(0\) から始まるため、D[i - 1] のようにインデックスを調整する必要があります。

• 高速な入出力: Pythonの場合、sys.stdin.read().split() で全ての入力を一度に取得し、イテレータ (iter()) を使うことで大量のデータを効率よく処理できます。また、結果をリストに蓄積して最後に '\n'.join() で一括出力するのも有効です。

  ソースコード

import sys
from itertools import islice

def main():
    # 入力を一括で読み込み、空白で分割してリスト化することで高速化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用して各要素を順番に取得します
    it = iter(input_data)
    
    # N: 備品の種類数, M: 部署の数
    N = int(next(it))
    M = int(next(it))
    
    # P: 実際の価格, Q: 古い価格表の価格
    # isliceとmapを使用して効率的に整数リストに変換します
    P = list(map(int, islice(it, N)))
    Q = list(map(int, islice(it, N)))
    
    # 各備品について、実際の価格と見積もり価格の差額 (P_i - Q_i) をあらかじめ計算します
    # 備品番号は1から始まるため、リストDのインデックスiは備品番号i+1に対応します
    D = [p - q for p, q in zip(P, Q)]
    
    results = []
    # 各部署の購入申請を処理します
    for _ in range(M):
        # K: 購入する備品の個数
        K = int(next(it))
        
        # 次のK個の要素（備品番号）を整数に変換し、その差額の合計を計算します
        # map(int, islice(it, K)) でK個の備品番号を効率的に取得します
        # 備品番号は1-indexedなので、D[i - 1]でアクセスします
        diff_sum = sum(D[i - 1] for i in map(int, islice(it, K)))
        
        # 結果を文字列としてリストに追加します
        results.append(str(diff_sum))
        
    # すべての結果を改行で連結して一括出力します
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    main()

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