概要

料理コンテストで得点上位 \(K\) 人のシェフを選び、その全員が共通して得意とする食材の数を求める問題です。

考察

問題を整理する

この問題は大きく2つのステップに分けられます： 1. 得点の上位 \(K\) 人を選ぶ 2. 選ばれた \(K\) 人全員が共通して得意とする食材を求める

上位 \(K\) 人の選び方

得点が高い順に \(K\) 人を選びますが、同点の場合はシェフ番号が小さい方が上位になります。これはソートを使えば簡単に実現できます。

例えば、\(K = 2\) で以下のシェフがいるとします： - シェフ1: 得点100, 得意食材 {1, 2, 3} - シェフ2: 得点100, 得意食材 {2, 3, 4} - シェフ3: 得点80, 得意食材 {1, 2}

この場合、得点上位2人はシェフ1とシェフ2（同点なので番号順）となります。

共通食材の求め方

全員が共通して得意とする食材は、集合の積集合（intersection）で求められます。

上の例では： - シェフ1の得意食材: {1, 2, 3} - シェフ2の得意食材: {2, 3, 4} - 共通食材: {1, 2, 3} ∩ {2, 3, 4} = {2, 3}

よって答えは 2 となります。

計算量について

• シェフの数は最大 \(10^5\)
• 食材の総数は最大 \(2 \times 10^5\)

ソートに \(O(N \log N)\)、積集合の計算に \(O(\sum C_i)\) かかりますが、制約内で十分高速に動作します。

アルゴリズム

1. 入力を読み込む: 各シェフの得点 \(V_i\) と得意食材の集合 \(S_i\) を保存
2. ソートする: 得点の降順、同点ならシェフ番号の昇順でソート
3. 上位 \(K\) 人を取得: ソート後の先頭 \(K\) 人が決勝進出者
4. 積集合を計算: 最初のシェフの食材集合からスタートし、順番に他のシェフの集合と積集合を取る
5. 答えを出力: 最終的な積集合の要素数が答え

common = 1番目のシェフの得意食材
for i = 2 to K:
    common = common ∩ (i番目のシェフの得意食材)
return |common|

計算量

• 時間計算量: \(O(N \log N + \sum_{i=1}^{N} C_i)\)
  • ソートに \(O(N \log N)\)
  • 積集合の計算に \(O(\sum C_i)\)（各食材は最大1回ずつ処理される）
• 空間計算量: \(O(N + \sum_{i=1}^{N} C_i)\)
  • シェフの情報と食材集合を保存する領域

実装のポイント

1. ソートのキー: Pythonでは key=lambda x: (-x[0], x[1]) とすることで、得点の降順・シェフ番号の昇順を同時に実現できます。負号をつけて降順にするテクニックは頻出です。

2. 集合の積集合: Pythonでは & 演算子または intersection() メソッドで簡単に計算できます。

3. 効率的な入力処理: 大量のデータを読み込む場合、sys.stdin.read() で一括読み込みしてから処理すると高速です。

4. コピーの注意: common = top_k[0][2].copy() のように、元の集合を変更しないためにコピーを取ることが重要です（今回は &= で新しい集合が作られるため問題ありませんが、安全のため）。

   ソースコード

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    chefs = []
    for i in range(N):
        V = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        ingredients = set()
        for _ in range(C):
            t = int(input_data[idx]); idx += 1
            ingredients.add(t)
        chefs.append((V, i, ingredients))
    
    # Sort by score descending, then by chef number ascending
    chefs.sort(key=lambda x: (-x[0], x[1]))
    
    # Get top K chefs
    top_k = chefs[:K]
    
    # Find common ingredients among all K chefs
    if K == 0:
        print(0)
        return
    
    # Start with the first chef's ingredients and intersect with others
    common = top_k[0][2].copy()
    for i in range(1, K):
        common &= top_k[i][2]
    
    print(len(common))

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。