概要

\(N\) 人のメンバー全員が共通して選んだ曲の数を求める問題です。各曲が何人に選ばれたかをカウントし、\(N\) 人全員に選ばれた曲の数を数えます。

考察

重要な気づき

「全員が共通して選んだ曲」とは、\(N\) 人全員がその曲を選んでいるということです。つまり、ある曲が選ばれた回数がちょうど \(N\) 回であれば、その曲は全員に選ばれています。

具体例で理解する

例えば、\(N = 3\) 人のメンバーがいて、以下のように曲を選んだとします： - メンバー1: 曲1, 曲2, 曲3 - メンバー2: 曲2, 曲3 - メンバー3: 曲1, 曲2, 曲4

各曲が選ばれた回数をカウントすると： - 曲1: 2回（メンバー1, 3） - 曲2: 3回（メンバー1, 2, 3）← 全員が選んだ！ - 曲3: 2回（メンバー1, 2） - 曲4: 1回（メンバー3）

よって、全員が共通して選んだ曲は「曲2」の1曲です。

素朴なアプローチとの比較

もし各曲について「全員が選んでいるか」を愚直に確認すると、\(M\) 曲 × \(N\) 人 = \(O(NM)\) の計算量になり、最大 \(10^{10}\) 回の操作が必要で TLE になる可能性があります。

しかし、実際に選ばれた曲の総数は \(\sum K_i \leq 2 \times 10^5\) に制限されているため、選ばれた曲だけをカウントすれば十分高速に解けます。

アルゴリズム

1. カウンター（連想配列）を用意する: 各曲が何回選ばれたかを記録するための Counter を使います。

2. 全メンバーの選択を処理する: 各メンバーが選んだ曲を読み込み、その曲のカウントを1増やします。

3. 全員が選んだ曲を数える: カウンターの値が \(N\) に等しい曲の数を数えます。これが答えです。

count[曲番号] = その曲を選んだ人数

最後に count[曲番号] == N となる曲番号の個数が答えになります。

計算量

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

  • 全メンバーが選んだ曲の総数分だけカウント処理を行います
  • 制約より \(\sum K_i \leq 2 \times 10^5\) なので十分高速です

• 空間計算量: \(O(M)\)

  • 最大で \(M\) 種類の曲のカウントを保持する可能性があります
  • ただし実際には選ばれた曲の種類数だけで済みます

実装のポイント

1. 入力形式に注意: 各行の最初の数字 \(K_i\) は曲の数であり、曲番号ではありません。line[1:] で曲番号のリストを取得します。

2. Counter の活用: Python の collections.Counter を使うと、要素の出現回数を簡単にカウントできます。

3. 最終カウント: count.values() で各曲の選ばれた回数を取得し、その値が \(N\) と等しいものを数えます。条件 c == N を満たす曲が「全員が選んだ曲」です。

   ソースコード

from collections import Counter

N, M = map(int, input().split())
count = Counter()

for _ in range(N):
    line = list(map(int, input().split()))
    K = line[0]
    songs = line[1:K+1]
    for song in songs:
        count[song] += 1

# N人全員が選んだ曲の数をカウント
result = sum(1 for c in count.values() if c == N)
print(result)

---

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