概要

\(N\) 人のシェフの中から、スコアの高い順（同点なら番号の小さい順）に上位 \(K\) 人を選出し、その \(K\) 人全員が得意としている食材が何種類あるかを求める問題です。

考察

この問題は、大きく分けて以下の2つのステップで解くことができます。

1. 決勝進出者（上位 \(K\) 人）を特定する 各シェフは「得点」と「シェフ番号」の情報を持っています。問題文の条件（得点が高い順、得点が同じなら番号が小さい順）に従ってシェフを並べ替え、先頭から \(K\) 人を選びます。

2. 共通する食材を数える 「全員が共通して得意とする」という条件を効率よく判定する必要があります。 すべての食材（\(1\) から \(M\)）について、「進出した \(K\) 人のうち、何人がその食材を得意としているか」をカウントします。もし、ある食材のカウントがちょうど \(K\) であれば、それは「全員が共通して得意とする食材」であると言えます。

アルゴリズム

1. データの読み込みと整理 各シェフの情報をリストに格納します。ソートを簡単にするために、(得点, -シェフ番号) というタプルを作成します。 ※Pythonの sort(reverse=True) を使う場合、第2要素にマイナスをつけたシェフ番号を入れることで、「得点は大きい順、番号は小さい順」という条件を一度に満たすことができます。

2. ソートと選出 作成したリストを降順にソートし、最初の \(K\) 人を抽出します。

3. 食材のカウント サイズ \(M+1\) の配列（バケット）を用意します。 選出された \(K\) 人のシェフについて、それぞれが得意とする食材 \(T_{i,j}\) を確認し、配列の該当するインデックスの値を \(+1\) していきます。

4. 集計 最後に、配列の中身を確認し、値が \(K\) になっている要素の個数を数えて出力します。

計算量

\(N\) をシェフの数、\(M\) を食材の種類数、\(C_{total}\) を全シェフの得意食材の総数（\(\sum C_i\)）とします。

• 時間計算量: \(O(N \log N + C_{total} + M)\)

  • シェフのソートに \(O(N \log N)\) かかります。
  • 食材のカウントには、進出したシェフの得意食材の数だけ処理を行うため、最大で \(O(C_{total})\) です。
  • 最後の集計で \(O(M)\) かかります。
  • 制約（\(N, M \le 10^5, C_{total} \le 2 \times 10^5\)）より、この計算量は十分実行時間制限内に収まります。

• 空間計算量: \(O(N + M + C_{total})\)

  • シェフの情報、食材のカウント配列、各シェフの食材リストを保持するために必要です。

実装のポイント

• 大量の入力の処理: \(N\) や \(M\) が \(10^5\) クラスと大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などを使って一括で読み込む方が高速です。

• タイブレークの処理: ソート条件が複数ある場合（得点と番号）、タプルをうまく使うことで簡潔に実装できます。

• 食材のカウント: 「共通の食材」を探す際、集合（set）の積集合をとる方法もありますが、今回のように「\(K\) 人全員」という条件で食材の種類数 \(M\) が決まっている場合は、配列（バケット）によるカウントが非常に高速でメモリ効率も良いです。

  ソースコード

import sys

def solve():
    # Read all input data at once for efficiency
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: number of chefs, M: number of ingredients, K: number of finalists
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    chef_scores = []
    chef_ingredients = [None] * N
    
    ptr = 3
    for i in range(N):
        # V_i: score of chef i, C_i: number of favorite ingredients
        v = int(input_data[ptr])
        c = int(input_data[ptr + 1])
        # chef_scores: (score, -chef_id, original_index)
        # Using -chef_id because we sort in reverse and want smaller chef_id first for ties.
        chef_scores.append((v, -(i + 1), i))
        # Store references to the ingredient strings as a slice
        chef_ingredients[i] = input_data[ptr + 2 : ptr + 2 + c]
        ptr += 2 + c
        
    # Sort chefs based on score (descending) and chef_id (ascending)
    # The tuple (v, -chef_id) sorted descending achieves this.
    chef_scores.sort(key=lambda x: (x[0], x[1]), reverse=True)
    
    # ingredient_counts[ing] will store how many finalists like ingredient 'ing'
    ingredient_counts = [0] * (M + 1)
    for i in range(K):
        # Get the original index of the finalist from the sorted list
        idx = chef_scores[i][2]
        for ing_str in chef_ingredients[idx]:
            ing = int(ing_str)
            # Increment count for this ingredient
            ingredient_counts[ing] += 1
            
    # Count how many ingredients were liked by all K finalists
    ans = 0
    for count in ingredient_counts:
        if count == K:
            ans += 1
    
    # Output the final count
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

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