概要

各日において、各教室の参加希望者数がその教室の定員以下であれば全員が参加でき、超えるとその教室の全員が参加できなくなるという条件下で、N日間の参加者延べ人数を求める問題です。

考察

問題の条件から、各日において各教室の参加希望者数を集計し、その数が教室の定員以下かどうかを判定する必要があります。素朴なアプローチとして、各日ごとにすべての来場者情報を処理し、各教室への希望者数をカウントして定員と比較する方法が考えられます。

重要な点は、1日あたりの来場者数 \(K_i\) の合計が最大20万程度であることです。このため、各日ごとに希望教室の出現回数をカウントする処理は十分効率的です。ただし、教室数 \(M\) が最大10万あるため、毎日すべての教室をチェックするのは非効率ですが、実際にはその日に希望のあった教室だけを処理すればよいことに気づきます。

アルゴリズム

1. 各教室の定員 \(C_j\) を読み込む
2. 各日について以下の処理を行う:
   • その日の来場者数 \(K_i\) と希望教室リストを読み込む
   • 辞書（またはハッシュマップ）を使用して、各希望教室への希望者数をカウントする
   • 各希望教室について、希望者数が定員 \(C_j\) 以下であれば、その人数を参加者数に加算する
3. すべての日についての参加者数を合計して出力する

各日では、実際に希望のあった教室のみを処理するため、効率的な計算が可能です。

計算量

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

実装のポイント

• 入力データを一度に読み込むことで効率化

• 各日ごとに辞書を使用して希望教室の出現回数をカウント

• 教室番号は1-indexedなので、配列のインデックスに注意

• その日に実際に希望のあった教室のみを処理するため、無駄なループが発生しない

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
    
    it = iter(data)
    N = int(next(it)); M = int(next(it))
    C = [0] * (M + 1)
    for j in range(1, M + 1):
        C[j] = int(next(it))
    
    total_attended = 0
    for i in range(N):
        K_i = int(next(it))
        day_requests = []
        for k in range(K_i):
            p = int(next(it))
            day_requests.append(p)
        
        count_per_room = {}
        for room in day_requests:
            count_per_room[room] = count_per_room.get(room, 0) + 1
        
        day_attended = 0
        for room, count in count_per_room.items():
            if count <= C[room]:
                day_attended += count
        
        total_attended += day_attended
    
    print(total_attended)

if __name__ == "__main__":
    main()

---

この解説は deepseekv3 によって生成されました。