概要

各日に複数の来場者が希望する教室があり、定員を超えるとその教室の講演は中止される。延べ何人が講演に参加できたかを求める。

考察

この問題では、各日ごとに来場者が希望する教室の人数を集計し、その教室の定員と比較することで、その日のその教室での参加者数が決まります。

例えば、ある日、教室Aが定員10人で、希望者が8人いるなら、全員参加できます。しかし、希望者が12人いる場合、安全上講演が中止され、誰も参加できません。

素朴な方法として、毎回来場者のリストをそのまま処理し、各教室ごとに人数を数える方法がありますが、最悪の場合、1日あたり \(K_i\) が大きいと非効率です。しかし、各日において必要なのは「どの教室に何人が希望しているか」だけなので、事前にカウントすることで効率的に処理できます。

また、入力を高速に読み込む必要があるため、sys.stdin.read を使って一度に全ての入力を読み込み、分割して処理するのが有効です。

アルゴリズム

1. 全ての入力を一度に読み込み、トークンに分割する。
2. 各日について以下を行う：
   • 当日の来場者数 \(K_i\) を取得。
   • 各来場者の希望教室を読み込み、0-indexed に変換。
   • Counter を使い、各教室への希望者数を集計。
   • 各教室について、希望者数が定員以下ならばその人数を答えに加算。超えていれば誰も参加できないので無視。
3. 全日程分の合計を出力。

計算量

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

※ \(\sum K_i \leq 2 \times 10^5\) なので、十分高速。

実装のポイント

• 教室番号は1-indexedで入力されるため、内部で扱う際は0-indexedに変換する（-1する）。
• Counterを使うことで、各教室への希望者数を効率的に集計できる。
• 入力が非常に多いので、sys.stdin.readを使って高速に入力を読み込む必要がある。

## ソースコード

```python
import sys
from collections import Counter

input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    C = [int(data[idx + j]) for j in range(M)]
    idx += M
    
    total = 0
    
    for _ in range(N):
        K = int(data[idx])
        idx += 1
        P = [int(data[idx + k]) - 1 for k in range(K)]
        idx += K
        
        count = Counter(P)
        
        for room, cnt in count.items():
            if cnt <= C[room]:
                total += cnt
                
    print(total)

if __name__ == "__main__":
    main()

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