概要

得点順（同点なら番号が小さい順）で上位 \(K\) 人のシェフを選び、その \(K\) 人全員が共通して得意な食材の種類数（集合の共通部分の大きさ）を求めます。

考察

まず「決勝進出者」は、得点 \(V_i\) の降順、同点の場合はシェフ番号の昇順で並べたときの先頭 \(K\) 人で一意に決まります。よって最初にやるべきことは 上位 \(K\) 人の特定 です。

次に求めたいのは、決勝進出した \(K\) 人の集合 \(S_{i_1}, S_{i_2}, \dots, S_{i_K}\) の共通部分 [ |S_{i1} \cap S{i2} \cap \cdots \cap S{i_K}| ] です。

素朴に「各食材 \(t\) について、上位 \(K\) 人全員が持つかを調べる」と、各食材ごとに \(K\) 人を確認して \(O(MK)\) になり、最大で \(10^5 \times 10^5\) となって間に合いません。

ここで重要な観察は、入力全体の「得意食材の総数」が [ \sum C_i \le 2\times 10^5 ] と小さいことです。つまり、食材情報は疎（まばら）なので、「現れた食材だけを数える」方向にすると高速に処理できます。

具体的には、上位 \(K\) 人に含まれる各食材 \(t\) の出現回数を数え、回数がちょうど \(K\) なら「全員が持っている」と判断できます。

アルゴリズム

1. 各シェフ \(i\) について、得点 \(V_i\) と得意食材リスト \(S_i\) を読み込む。
2. シェフをキー (-V[i], i)（得点降順・番号昇順）でソートし、先頭 \(K\) 人を決勝進出者として取り出す。
3. 配列 cnt[t] を用意し、決勝進出者の各食材 \(t\) について cnt[t] += 1 として出現回数を数える。
4. \(t=1\) から \(M\) まで走査し、cnt[t] == K を満たす食材の個数を答えとして出力する。

（例） - 決勝進出者が \(K=3\) 人で、食材 1 が 3 回出現していれば、3 人全員が食材 1 を得意 ⇒ 使える食材にカウント。

計算量

• 時間計算量: ソートが \(O(N\log N)\)、カウントが \(O\!\left(\sum_{i\in\text{決勝}} C_i\right)\)、最後の走査が \(O(M)\) なので全体で
  [ O(N\log N + M + \sum_{i\in\text{決勝}} C_i) ]
• 空間計算量: 食材カウント配列が \(O(M)\)、入力保持が合計で \(O\!\left(\sum C_i\right)\) 程度なので
  [ O(M + \sum C_i) ]

実装のポイント

• 同点処理は「番号が小さい方が上位」なので、ソートキーを (-V[i], i) にすると安全です。

• cnt は食材番号が \(1 \sim M\) なので長さ M+1 の配列にすると扱いやすいです。

• \(\sum C_i\) が大きめなので、Python では sys.stdin.buffer.readline を使うと高速に読み込めます。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M, K = map(int, input().split())

    V = [0] * N
    ing = [None] * N

    for i in range(N):
        a = list(map(int, input().split()))
        V[i] = a[0]
        C = a[1]
        ing[i] = a[2:] if C else []

    order = list(range(N))
    order.sort(key=lambda i: (-V[i], i))
    finalists = order[:K]

    cnt = [0] * (M + 1)
    for i in finalists:
        for t in ing[i]:
            cnt[t] += 1

    ans = 0
    for t in range(1, M + 1):
        if cnt[t] == K:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。