概要

\(N\) 日間にわたり \(M\) 個の教室で講演が行われます。各教室には定員があり、ある日の希望者数が定員を超えると、その日のその教室の講演は中止となります。全日程を通して、実際に講演に参加できた人数の合計を求める問題です。

考察

この問題を解く上で重要なポイントは、「各日にどの教室に何人集まったか」を効率的に集計することです。

1. 素朴なアプローチ

毎日 \(M\) 個の教室すべてについて、「この教室を希望した人は何人いるか？」を確認すると、計算量は \(O(N \times M)\) となります。 本問題では \(N, M \le 10^5\) であるため、最悪の場合 \(10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

2. 効率的な解決策

実際には、毎日すべての教室に人が集まるわけではありません。\(i\) 日目の来場者数を \(K_i\) とすると、その日に希望者が現れる教室の数は最大でも \(K_i\) 個です。 制約を見ると \(\sum K_i \le 2 \times 10^5\) となっており、全日程の来場者数の総和は十分に小さいことがわかります。

したがって、各日において「実際に希望者がいた教室」のみを対象に集計・判定を行うことで、計算量を大幅に削減できます。

アルゴリズム

以下の手順で解を進めます。

1. 準備: 各教室の定員 \(C_j\) を配列などに格納します（教室番号が \(1\) から始まるため、1-indexed で管理すると実装がスムーズです）。
2. 各日の処理:
   • その日の来場者が希望した教室のリストを受け取ります。
   • ハッシュマップ（Pythonでは collections.Counter）などを用いて、教室ごとの希望者数をカウントします。
   • カウントされた各教室（room_id）について、以下の判定を行います：
     • 希望者数 <= C[room_id] ならば、その人数を合計に加算する。
     • そうでなければ（定員超過）、加算しない。
3. 出力: 全日程の加算結果を出力します。

計算量

入力の総数を \(S = \sum K_i\) とします。

• 時間計算量: \(O(M + S)\)
  • 教室の定員の読み込みに \(O(M)\) かかります。
  • 各日の集計と判定は、その日の来場者数 \(K_i\) に比例する時間で行えるため、全体で \(O(S)\) となります。
• 空間計算量: \(O(M + \max K_i)\)
  • 定員を保持する配列に \(O(M)\) 必要です。
  • 各日の集計用のハッシュマップに最大 \(O(K_i)\) の空間を使用します。

実装のポイント

• 高速な入出力: 入力される数値の総数が多いため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込む手法が有効です。

• 集計の効率化: collections.Counter を使うことで、リストから「どの要素が何個あるか」を \(O(K_i)\) で簡単に集計できます。

• 1-indexedの扱い: 教室番号 \(1 \sim M\) をそのまま配列のインデックスとして使うため、サイズ \(M+1\) の配列を用意しておくとミスを防げます。

  ソースコード

import sys
from collections import Counter

def solve():
    # 全ての入力を一度に読み込み、空白文字で分割してトークン化します。
    # これにより、行の区切りを気にせずにデータを取得できます。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # 全てのトークンを整数に変換します。
    data = list(map(int, input_data))
    
    # 読み込み位置を管理するポインタ
    ptr = 0
    
    # N: イベントの日数, M: 教室の個数
    if ptr + 1 >= len(data):
        return
    N = data[ptr]
    M = data[ptr+1]
    ptr += 2
    
    # 各教室の定員情報を取得（1-indexedにするためサイズ M+1 のリストを作成）
    # C[j] に教室 j の定員が入るようにします。
    C = [0] * (M + 1)
    for i in range(1, M + 1):
        if ptr < len(data):
            C[i] = data[ptr]
            ptr += 1
            
    total_participants = 0
    
    # N日間、各日の情報を処理します。
    for _ in range(N):
        if ptr >= len(data):
            break
        
        # その日の来場者数 K
        K = data[ptr]
        ptr += 1
        
        # その日の来場者が希望する教室のリストを取得
        # 連続した K 個の要素をスライスで取得します。
        day_rooms = data[ptr : ptr + K]
        ptr += K
        
        # 各教室を希望した人数をカウントします。
        # collections.Counter を使用することで、効率的に集計できます。
        day_counts = Counter(day_rooms)
        
        # 各教室ごとに、希望者数が定員以下かどうかを判定します。
        for room_id, count in day_counts.items():
            # room_id が有効な範囲内であり、かつ定員以下の場合のみ加算
            if room_id <= M and count <= C[room_id]:
                total_participants += count
            # 定員を超えた場合は、その教室の講演は中止（0人が参加）となります。
            
    # 全日程の合計人数を出力します。
    sys.stdout.write(str(total_participants) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。