概要

各日ごとに「教室ごとの希望者数」を数え、定員以下の教室の分だけ参加できた人数を加算していく問題です。

考察

重要なのは、講演が中止になるかどうかは「その日・その教室の希望者数」だけで決まるという点です。
つまり、ある日について教室 \(j\) の希望者数を \(x\) とすると、

• \(x \le C_j\) なら、その教室希望者 \(x\) 人は全員参加できる
• \(x > C_j\) なら、その教室希望者は 0 人（全員参加不可）

したがって、各日ごとに「教室番号 \(\rightarrow\) 希望者数」を集計できれば答えが出ます。

素朴に「各教室について希望者数を数える」を毎日 \(M\) 個の教室すべてに対してやると、最悪で \(O(NM)\) になり（\(10^5 \times 10^5\)）到底間に合いません。
しかしこの問題では \(\sum K_i \le 2 \times 10^5\) なので、実際に希望があった教室だけを数えるようにすれば、全体を高速に処理できます。

例：ある日に希望が [1,1,3,3,3,5] なら集計は {1:2, 3:3, 5:1} だけ作れば十分で、他の教室は「希望者 0」で結果に影響しません。

アルゴリズム

1. 教室の定員 \(C_1,\dots,C_M\) を配列に持つ（1-indexed にすると教室番号と対応しやすい）。
2. 各日について以下を行う：
   1. その日の希望教室列を読み取り、辞書（連想配列）cnt により cnt[教室] = 希望者数 を数える。
   2. cnt に入っている各教室 (room, v) について、
      • もし \(v \le C_{room}\) なら ans += v
      • そうでなければ何も足さない（中止なので 0 人）
3. 最終的な ans を出力する。

この方法だと、「希望者の数え上げ」は希望者の人数ぶんだけで済みます。

計算量

• 時間計算量: \(O\!\left(\sum_{i=1}^{N} K_i\right)\)
  （各希望を 1 回ずつ辞書で数え、数えた教室数ぶんだけ判定するため。教室数ぶんの判定も合計で \(\sum K_i\) を超えません）
• 空間計算量: \(O(M + U)\)
  ここで \(U\) は「その日の異なる教室数」で、最大でも \(K_i\)。定員配列に \(O(M)\)、日ごとの辞書に \(O(U)\) を使います。

実装のポイント

• 入力が大きいので、sys.stdin.buffer.read().split() のようにまとめて読み、整数化して高速化しています。

• 各日ごとの集計は dict（cnt[p] = cnt.get(p, 0) + 1）で行うと簡潔です。

• 定員配列を C[1..M] の 1-indexed にしておくと、入力の教室番号をそのまま使えてミスが減ります。

  ソースコード

import sys

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

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

    C = [0] * (M + 1)
    for j in range(1, M + 1):
        C[j] = next(it)

    ans = 0
    for _ in range(N):
        K = next(it)
        cnt = {}
        for _ in range(K):
            p = next(it)
            cnt[p] = cnt.get(p, 0) + 1
        for room, v in cnt.items():
            if v <= C[room]:
                ans += v

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

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