概要

各注文で指定されたおかず番号に対応する価格を、順番に足し合わせて合計を出力する問題です。
価格配列をそのまま参照すれば、全注文を高速に処理できます。

考察

重要な点は、「各注文はおかず番号のリストとして与えられる」ことです。
したがって、注文ごとにやるべきことはシンプルで、列挙された番号 \(a\) に対して価格 \(W_a\) を足すだけです。

例えば価格が
\(W_1=300, W_2=500, W_3=200\) のとき、注文が \((2, 1, 3)\) なら合計は \(300+200=500\) です。

素朴に「毎回どのおかずの価格かを探索する」ような実装（例: リストを線形探索）をすると、1回の参照が遅くなり、全体で間に合わなくなる可能性があります。
この問題ではおかず番号は \(1\) から \(N\) までなので、配列で直接アクセスすれば \(O(1)\) で価格を取得できます。

また、制約で
\(\sum_{j=1}^{M} K_j \le 10^6\)
が保証されているため、全ての選択おかずを1回ずつ処理する実装なら十分高速です。

アルゴリズム

1. \(N, M\) を読む。
2. 価格配列 \(W\) を読む。実装では W = [0] + ... として 1-indexed にすると、番号 \(a\) に対して W[a] をそのまま使えて便利。
3. 各注文について:
   • 行の先頭を \(K_j\) として受け取る。
   • 続く \(K_j\) 個のおかず番号 \(A_{j,k}\) それぞれに対し、s += W[A_{j,k}]。
   • 合計 s を出力用配列に追加。
4. 最後に改行区切りでまとめて出力する。

計算量

• 時間計算量: \(O\!\left(N + \sum_{j=1}^{M} K_j\right)\)
  （入力読み込みと、各選択おかずを1回ずつ足す処理）
• 空間計算量: \(O(N + M)\)
  （価格配列と出力文字列の保存。入力1行分の一時配列は最大 \(O(N)\) 程度）

実装のポイント

• sys.stdin.readline を使って高速入力にする。

• 価格配列を 1-indexed にして、添字ずれバグを防ぐ。

• 出力は print を毎回呼ぶより、配列にためて "\n".join(out) でまとめて書くと高速。

  ソースコード

import sys

def main():
    input = sys.stdin.readline

    N, M = map(int, input().split())
    W = [0] + list(map(int, input().split()))  # 1-indexed

    out = []
    for _ in range(M):
        data = list(map(int, input().split()))
        k = data[0]
        s = 0
        for a in data[1:1 + k]:
            s += W[a]
        out.append(str(s))

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

if __name__ == "__main__":
    main()

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