概要

各備品の実際の価格と古い価格表の価格の差を用いて、各部署の購入申請における差額を求める問題。

考察

この問題では、各備品 \(i\) について「実際の価格 \(P_i\)」と「古い価格表の価格 \(Q_i\)」が与えられ、各部署が希望する備品リストに対し、それらの差 \(P_i - Q_i\) の合計を求めます。

素朴な方法としては、各部署ごとに、その部署が希望する備品番号を一つずつ見ていき、その都度 \(P_i - Q_i\) を計算して足し合わせるという方法があります。しかし、この方法でも十分高速です。制約を見ると、\(\sum K_j \leq 2 \times 10^5\) であり、各部署の希望リストの長さの合計が非常に小さいため、全部署を通じて計算回数が多くても20万回程度に抑えられます。よって、特に工夫しなくても間に合うと考えられます。

ただし、入力を高速に読み込む必要があり、Python標準の input() 関数では遅いため、sys.stdin.read を使って一度に全ての入力を読み込んで処理するのが望ましいです。

さらに、各備品 \(i\) について事前に差 \(D_i = P_i - Q_i\) を計算しておくことで、各部署での合計計算が効率的になります。

アルゴリズム

1. 全ての入力を一度に読み込み、リストに格納します。
2. 各備品 \(i\) について、差 \(D_i = P_i - Q_i\) を前計算しておきます（コードでは直接使用時に計算していますが、別途配列に持ってもよい）。
3. 各部署について、希望する備品の番号を順に見て、対応する \(P_c - Q_c\) を合計します。
4. 結果を出力します。

計算量

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

実装のポイント

• 入力が非常に多いので、sys.stdin.read を使って高速に読み込む。

• 各部署の計算では、\(P_c - Q_c\) を都度計算してもよいが、メモ化するとさらに高速になる場合もある。

• 結果は最後にまとめて出力すると効率的（print('\n'.join(result)) のように）。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    P = [0] * (N + 1)
    Q = [0] * (N + 1)
    
    for i in range(1, N + 1):
        P[i] = int(data[idx])
        idx += 1
    for i in range(1, N + 1):
        Q[i] = int(data[idx])
        idx += 1
    
    result = []
    for _ in range(M):
        K = int(data[idx])
        idx += 1
        diff = 0
        for __ in range(K):
            c = int(data[idx])
            idx += 1
            diff += P[c] - Q[c]
        result.append(str(diff))
    
    print('\n'.join(result))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。