概要

\(N\) 人のメンバーがそれぞれ複数の曲を選んでいるとき、全員が共通して選んでいる曲の数を求める問題。

考察

この問題では、各メンバーが選んだ曲のリストが与えられ、すべてのメンバーが選んでいる曲の集合の共通部分（積集合）を求めることになります。

素朴な方法として、例えばすべての曲に対して「その曲を何人が選んでいるか」をカウントする方法が考えられます。しかし、これには最大 \(M\) 個の曲について、それぞれ \(N\) 人を確認する必要があり、最悪ケースで \(O(N \cdot M)\) の計算量になってしまいます。制約より、これは最大で \(10^{10}\) となり、時間内に処理しきれません。

そこで効率的な方法として、「集合（set）」を使うことを考えます。最初のメンバーが選んだ曲の集合を基準とし、それに続く各メンバーの曲の集合との「共通部分（積集合）」を逐次更新していくことで、最終的に全員が選んでいる曲の集合を得ることができます。この方法では、各曲リストのサイズの合計が \(2 \times 10^5\) であることを利用して、効率的に処理できます。

アルゴリズム

1. 最初のメンバーの選んだ曲の集合 common_songs を作る。
2. 次のメンバー以降について、そのメンバーの選んだ曲の集合 songs を作り、common_songs との積集合を取って更新する。
3. 最終的な common_songs の要素数を出力する。

このように集合演算を使うことで、不要な比較を避けながら効率的に共通項を求めることができます。

計算量

• 時間計算量: \(O(\sum_{i=1}^{N} K_i)\)
  各メンバーの選んだ曲の数の合計だけ集合操作を行うため。
• 空間計算量: \(O(M)\)
  最大で \(M\) 個の曲を格納する可能性のある集合を保持するため。

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している。
• 集合の積集合演算 (&=) を使って、共通部分を効率的に更新している。
• 最初の集合を基準にすることで、後の処理がシンプルになる。

## ソースコード

```python
import sys
from collections import defaultdict

input = sys.stdin.read

data = input().split()
idx = 0

N = int(data[idx])
idx += 1
M = int(data[idx])
idx += 1

# 最初のメンバーの曲リストを取得
k = int(data[idx])
idx += 1
common_songs = set()
for _ in range(k):
    song = int(data[idx])
    idx += 1
    common_songs.add(song)

# 残りのメンバーの曲リストとの共通集合を取る
for i in range(1, N):
    k = int(data[idx])
    idx += 1
    songs = set()
    for _ in range(k):
        song = int(data[idx])
        idx += 1
        songs.add(song)
    common_songs &= songs

print(len(common_songs))

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