概要

料理コンテストで上位 \(K\) 人に残ったシェフたちが共通して使える食材の種類数を求めます。

考察

この問題では、まず上位 \(K\) 人のシェフを決定する必要があります。得点が同じ場合はシェフ番号が小さい方が上位となることに注意が必要です。

次に、これらのシェフがそれぞれ得意とする食材の集合から、共通部分（インターセクション）を求めることになります。

素朴な方法としては、すべての食材について、その食材を上位 \(K\) 人全員が持っているかどうかを確認する方法がありますが、これは最大で \(M \times K\) 回の比較が必要になり、制約が大きい場合（例えば \(M = 10^5\), \(K = 10^5\)）では間に合いません。

そこで、各シェフの得意とする食材を集合（set）で管理することで、効率的に共通部分を計算することが可能になります。Python の set 型には複数の集合の共通部分を求める機能（&= 演算子など）が備わっており、これを利用すれば高速に計算できます。

アルゴリズム

1. 全シェフの情報を読み込み、得点とシェフ番号に基づいて降順にソートします（得点が同じなら番号が小さい順）。
2. 上位 \(K\) 人のシェフを取り出し、それぞれの得意食材を set として保存します。
3. 最初の1人の食材集合を基準とし、残りの \(K - 1\) 人の集合との共通部分を順次求めます。
4. 最終的な共通集合の要素数を出力します。

具体例

入力例：

3 5 2
100 3 1 2 3
100 2 2 3
90 2 3 4

• シェフ1: 得点100、食材 {1, 2, 3}
• シェフ2: 得点100、食材 {2, 3}
• シェフ3: 得点90、食材 {3, 4}

得点が高い順かつ番号が小さい順に並べると、シェフ1 → シェフ2 → シェフ3。

上位 \(K = 2\) 人はシェフ1とシェフ2。

共通食材は {1, 2, 3} ∩ {2, 3} = {2, 3} → 答えは 2。

計算量

• 時間計算量: \(O(N \log N + \sum_{i=1}^{K} C_i) \)
  • ソートに \(O(N \log N)\)、集合演算に \(O(\sum C_i)\)
• 空間計算量: \(O(\sum_{i=1}^{N} C_i) \)

実装のポイント

• 各シェフの食材リストは重複がないので set を使うことで効率よく共通部分を計算できます。

• 得点が同じときの順序を正しく処理するために、ソートキーを (-得点, 番号) のように設定します。

• 高速な入力処理のために sys.stdin.read() を使用しています。

  ソースコード

import sys
from collections import defaultdict

input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    
    chefs = []
    
    for i in range(N):
        V = int(data[idx])
        idx += 1
        C = int(data[idx])
        idx += 1
        ingredients = []
        for _ in range(C):
            ingredients.append(int(data[idx]))
            idx += 1
        chefs.append((V, i+1, set(ingredients)))
    
    # 得点が高い順、シェフ番号が小さい順にソート
    chefs.sort(key=lambda x: (-x[0], x[1]))
    
    # 上位K人の食材の集合を取得
    top_k_sets = [chef[2] for chef in chefs[:K]]
    
    # 全ての集合の共通部分を求める
    common = top_k_sets[0]
    for s in top_k_sets[1:]:
        common &= s
    
    print(len(common))

if __name__ == "__main__":
    main()

---

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