概要

各日ごとに、各教室への希望者数を数え、定員以下なら全員参加、定員を超えたら全員不参加として、N日間の参加者の延べ人数を求める問題です。

考察

重要な気づき

この問題のポイントは、定員を超えた場合の扱いです。定員を超えると「一部の人が入れない」のではなく、講演自体が中止になり全員が参加できないという点に注意が必要です。

例えば、教室の定員が 3 人のとき： - 希望者が 3 人 → 3 人全員が参加できる（✅ 定員以下） - 希望者が 5 人 → 0 人が参加できる（❌ 定員超過で中止）

各日は独立

日をまたいでの累積などは考える必要がありません。毎日リセットされ、その日の希望者数だけで判定します。

素朴なアプローチで十分か？

各日ごとに来場者の希望教室を集計し、教室ごとに定員と比較すればよいです。来場者の総数 \(\sum K_i \leq 2 \times 10^5\) という制約があるため、全来場者を1人ずつ処理しても十分高速です。特別なアルゴリズムは不要で、集計（カウント）を正しく行うことが本質です。

アルゴリズム

1. 教室の定員 \(C_1, C_2, \ldots, C_M\) を読み込む。
2. 各日 \(i = 1, 2, \ldots, N\) について：
   • その日の \(K_i\) 人の希望教室を読み込む。
   • 教室ごとに希望者数をカウントする（Counter やハッシュマップを使用）。
   • 各教室について、希望者数 \(\leq\) 定員ならその人数を答えに加算する。
3. \(N\) 日間の合計を出力する。

具体例

教室が 2 つで定員が \(C_1 = 3, C_2 = 2\) のとき：

• 1日目: 希望が [1, 1, 2, 1] → 教室1に3人（\(3 \leq 3\) ✅）、教室2に1人（\(1 \leq 2\) ✅） → +4人
• 2日目: 希望が [2, 2, 2] → 教室2に3人（\(3 > 2\) ❌、中止） → +0人

合計: 4人

計算量

• 時間計算量: \(O(N + \sum_{i=1}^{N} K_i + M)\)
  • 各来場者を1回ずつ処理し、各日の教室ごとの集計を行うため、来場者総数に比例します。\(M\) は定員の読み込みにかかります。
• 空間計算量: \(O(M + \max_i K_i)\)
  • 定員配列のサイズ \(M\) と、各日ごとのカウンタ（最大で \(K_i\) 種類）の分です。

実装のポイント

• 高速な入力: sys.stdin.buffer.read() で入力を一括読み込みし、split() で分割することで、Python でも高速に処理できます。1行ずつ input() を呼ぶと遅くなる場合があります。

• Counter の活用: Python の collections.Counter を使うと、教室ごとの希望者数を簡潔にカウントできます。

• 教室番号のインデックス: 教室番号は 1-indexed なので、定員配列 C をサイズ \(M+1\) で確保し、C[j]（\(j = 1, \ldots, M\)）でアクセスできるようにしています。

  ソースコード

import sys
from collections import Counter

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    C = [0] * (M + 1)
    for j in range(1, M + 1):
        C[j] = int(input_data[idx]); idx += 1
    
    total = 0
    for i in range(N):
        K = int(input_data[idx]); idx += 1
        cnt = Counter()
        for k in range(K):
            p = int(input_data[idx]); idx += 1
            cnt[p] += 1
        for room, count in cnt.items():
            if count <= C[room]:
                total += count
    
    print(total)

main()

---

この解説は claude4.6opus-thinking によって生成されました。