概要

各備品について「実際価格 \(P_i\) − 古い表の価格 \(Q_i\)」を前計算し、各部署の申請リストに含まれる分だけ足し合わせて差額合計を求める問題です。

考察

求めたい値は部署 \(j\) ごとに $\(\sum_{k=1}^{K_j} (P_{C_{j,k}} - Q_{C_{j,k}})\)\( です。ここで重要なのは、部署ごとに毎回 \)P\( と \)Q$ を引き算する必要はない、という点です。

• まず各備品 \(i\) について差分 \(D_i = P_i - Q_i\) を作っておけば、 部署 \(j\) の答えは単に $\(\sum_{k=1}^{K_j} D_{C_{j,k}}\)$ になります。
• これにより、各申請に含まれる備品番号を見て差分配列を足すだけで済みます。

素朴に見える方法（部署ごとにその都度 \((P_i - Q_i)\) を計算して足す）でも計算量自体は同じですが、実装上は「引き算を何度も書く」より「差分配列を作って足す」方が単純で高速です。

また、制約として \(\sum K_j \le 2\times 10^5\) が与えられているため、各部署のリストを合計回数ぶんだけ走査する方針が最適です。逆に、例えば「各部署について \(1..N\) を走査して含まれるか判定する」ような実装をすると \(O(MN)\) となり確実にTLEになります。

具体例： - 備品1の差分が \(D_1=100\)、備品3が \(D_3=-50\) のとき、部署が \(\{1,3\}\) を買うなら答えは \(100+(-50)=50\) です。

アルゴリズム

1. 入力で \(P, Q\) を受け取り、各備品について差分配列 \(D\) を作る：\(D_i = P_i - Q_i\)。
2. 各部署について
   • \(K_j\) と備品番号列 \(C_{j,1..K_j}\) を読む
   • \(s=0\) から始め、各 \(c\) について \(s \mathrel{+}= D_{c}\)（添字は \(0\)-indexed に注意して \(c-1\)）
   • \(s\) を出力する

計算量

• 時間計算量: \(O(N + \sum_{j=1}^{M} K_j)\)
  （差分作成に \(O(N)\)、各申請の処理が合計で \(\sum K_j\) 回）
• 空間計算量: \(O(N)\)
  （差分配列 \(D\) を保持）

実装のポイント

• 備品番号 \(C_{j,k}\) は \(1\)-indexed なので、Pythonの配列に使うときは \(c-1\) にする。

• \(\sum K_j\) が最大 \(2\times 10^5\)、\(N,M\) も最大 \(10^5\) なので、sys.stdin.buffer.read() でまとめて読み、イテレータで順に取り出すと高速です。

• 差額は負になり得るので、符号付き整数としてそのまま扱います（Pythonなら問題なし）。

  ソースコード

import sys

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

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

    P = [next(it) for _ in range(N)]
    Q = [next(it) for _ in range(N)]
    D = [p - q for p, q in zip(P, Q)]

    out = []
    for _ in range(M):
        k = next(it)
        s = 0
        for _ in range(k):
            c = next(it) - 1
            s += D[c]
        out.append(str(s))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

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