Overview

Given \(N\) members who each select their favorite songs from a list of candidate songs, the problem asks us to find how many songs were chosen by all members in common.

Analysis

“Songs chosen by all members in common” can be rephrased as “songs that were chosen by exactly \(N\) people”.

The information about which songs each member chose is given as song numbers (from \(1\) to \(M\)). Therefore, we can count “how many people chose each song” for every song number, and then count how many songs have a count equal to \(N\) to obtain the answer.

Efficient Counting Method

If we tried to check all \(N\) members for each song to see “who chose it,” the computational cost could become too large. However, in this problem, the total number of songs chosen by all members (\(\sum K_i\)) is relatively small at most \(2 \times 10^5\), so by taking the approach of “incrementing the count for each song number as we encounter it,” we can solve this very efficiently.

Algorithm

1. Prepare an array counts of length \(M+1\), initialized entirely to \(0\). (Since song numbers range from \(1\) to \(M\), we use \(M+1\) to align the indices.)
2. For each member, read the chosen song numbers \(C_{i,j}\) and increment counts[C_{i,j}] by \(1\).
3. After processing the input for all members, iterate through the counts array.
4. Count the number of songs where counts[i] equals \(N\), and output that count.

Complexity

• Time Complexity: \(O(M + \sum K_i)\)
  • Scanning the songs chosen by each member takes \(O(\sum K_i)\), and checking the song list at the end takes \(O(M)\). Given the constraints \(\sum K_i \leq 2 \times 10^5, M \leq 10^5\), this runs sufficiently fast.
• Space Complexity: \(O(M)\)
  • The array counts for recording the count per song has size \(M+1\).

Implementation Notes

• Fast I/O: Since the amount of input can be large (up to \(\sum K_i\) numerical values), in Python using sys.stdin.read().split() to read all input at once can reduce execution time.

• Array Size: Since song numbers range from \(1\) to \(M\), setting the array size to \(M+1\) allows us to use the song number directly as an index, making the code clearer.

  Source Code

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()

This editorial was generated by gemini-3-flash-preview.