概要

各メンバーが選んだ曲の情報から、\(N\) 人全員が共通して選んだ曲（全員のリストに含まれる曲）の個数を数えます。

考察

「全員が共通して選んだ曲」とは、ある曲番号 \(x\) について \(N\) 人全員の選択リストに \(x\) が含まれることを意味します。
そこで、各曲が「何人に選ばれたか」を数え、最後にその数が \(N\) の曲を数えればよいと分かります。

例えば \(N=3\) のとき、曲 5 が 3 人全員に選ばれていればカウントすべきで、2 人までなら共通ではありません。

素朴に「曲ごとに、全員のリストを探す」をすると、曲数 \(M\) が最大 \(10^5\)、人数 \(N\) も最大 \(10^5\) なので、最悪だと \(O(NM)\) になり到底間に合いません。
本問題では \(\sum K_i \le 2\times 10^5\) と「選ばれた曲の総数」が抑えられているため、入力として現れる曲番号だけを数える方法にすると高速に処理できます。

アルゴリズム

1. 長さ \(M\) の配列 cnt を用意し、cnt[x] を「曲 \(x\) を選んだ人数」とする（初期値 0）。
2. 各メンバーの入力について、選んだ曲番号 \(c\) ごとに cnt[c] += 1 として人数カウントを増やす。
3. 最後に cnt[1..M] のうち cnt[x] == N を満たす曲の個数を数えて出力する。

この方法なら、各曲番号は入力に登場した回数だけ処理すればよく、重い探索が不要です。

計算量

• 時間計算量: \(O\!\left(\sum_{i=1}^{N} K_i + M\right)\)
  （カウント更新が \(\sum K_i\) 回、最後の集計が \(M\) 回）
• 空間計算量: \(O(M)\)
  （曲ごとのカウント配列）

実装のポイント

• 入力が最大 \(2\times 10^5\) 個以上の整数になるため、sys.stdin.buffer.read() でまとめて読み込むと高速です。

• cnt は 1-indexed で扱うと分かりやすく、cnt = [0]*(M+1) として cnt[1:] を走査します。

• cnt[x] == N の曲だけを数えるのが「全員共通」の条件です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    cnt = [0] * (M + 1)
    for _ in range(N):
        k = next(it)
        for _ in range(k):
            c = next(it)
            cnt[c] += 1

    ans = sum(1 for x in cnt[1:] if x == N)
    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。