概要

\(N\) 人のメンバーがそれぞれ候補曲リストの中から好きな曲を選んだとき、全員が共通して選んだ曲が何曲あるかを求める問題です。

考察

「全員が共通して選んだ曲」とは、言い換えると「選んだ人数がちょうど \(N\) 人である曲」のことです。

各メンバーがどの曲を選んだかという情報は、曲の番号（\(1\) から \(M\)）として与えられます。したがって、各曲の番号について「何人に選ばれたか」をカウントし、最後にそのカウントが \(N\) になっているものの個数を数えれば、答えを求めることができます。

効率的なカウント方法

もし、曲ごとに「誰が選んだか」を \(N\) 人全員分チェックしようとすると、計算量が多くなりすぎてしまう可能性があります。しかし、この問題では「各メンバーが選んだ曲の総数（\(\sum K_i\)）」が \(2 \times 10^5\) 以下と比較的少ないため、「選ばれた曲の番号をその都度カウントする」というアプローチをとることで、非常に効率よく解くことができます。

アルゴリズム

1. 長さ \(M+1\) の配列 counts を用意し、すべて \(0\) で初期化します。（曲番号が \(1\) から \(M\) なので、インデックスを合わせるため \(M+1\) とします）
2. 各メンバーについて、選んだ曲の番号 \(C_{i,j}\) を読み込み、counts[C_{i,j}] の値を \(1\) 増やします。
3. すべてのメンバーの入力を処理した後、counts 配列を順番に確認します。
4. counts[i] の値が \(N\) と等しい曲の個数をカウントし、それを出力します。

計算量

• 時間計算量: \(O(M + \sum K_i)\)
  • 各メンバーが選んだ曲を走査するのに \(O(\sum K_i)\)、最後に曲のリストを確認するのに \(O(M)\) かかります。制約より \(\sum K_i \leq 2 \times 10^5, M \leq 10^5\) であるため、十分高速に動作します。
• 空間計算量: \(O(M)\)
  • 曲ごとのカウントを記録する配列 counts のサイズが \(M+1\) となります。

実装のポイント

• 高速な入出力: 入力の数が多い（最大で \(\sum K_i\) 個の数値がある）ため、Python では sys.stdin.read().split() などを使って一括で入力を取得すると実行時間を短縮できます。

• 配列のサイズ: 曲の番号は \(1\) から \(M\) までなので、配列のサイズを \(M+1\) にしておくと、曲番号をそのままインデックスとして使えて分かりやすくなります。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: メンバーの人数, M: 曲の総数
    n = int(input_data[0])
    m = int(input_data[1])
    
    # 各曲が何人に選ばれたかを記録する配列
    # 曲番号は 1 から M なので、サイズ M+1 の配列を用意します
    counts = [0] * (m + 1)
    
    # input_data の読み込み位置を管理するポインタ
    ptr = 2
    for _ in range(n):
        # 各メンバーが選んだ曲数 K
        k = int(input_data[ptr])
        ptr += 1
        for _ in range(k):
            # 選んだ曲の番号
            song_id = int(input_data[ptr])
            counts[song_id] += 1
            ptr += 1
            
    # 全員（N人）が選んだ曲の数をカウントします
    ans = 0
    for i in range(1, m + 1):
        if counts[i] == n:
            ans += 1
            
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

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