概要

\(N\) 個の研究室それぞれが持つ研究テーマの集合から、共通のテーマが \(K\) 個以上ある研究室のペアの数を求める問題です。

考察

この問題では、すべての研究室のペア（ \(i < j\) ）について、共通の研究テーマの数を調べ、それが \(K\) 以上かどうかを判定する必要があります。

素朴な方法として、各ペアに対して、一方の研究室のテーマをもう一方のテーマと一つひとつ比較する方法が考えられますが、これは効率が悪く、最悪の場合 \(O(M^2)\) の比較が必要になります（ \(M\) はテーマ数）。また、テーマの一致を効率よく判定するために、リストではなく集合（set）を使うことが重要です。

集合を使うことで、共通要素の抽出（積集合）を高速に行え、さらに重複を気にする必要もなくなります。Python では set 型が非常に便利で、集合演算子 & を使って2つのセットの共通部分を簡単に求められます。

したがって、各研究室のテーマを set として保持しておき、すべてのペア \((i, j)\) （ \(i < j\) ）に対して積集合のサイズを調べ、それが \(K\) 以上であればカウントを増やす、という方針が有効です。

アルゴリズム

1. 各研究室の研究テーマを set として読み込み、リストに保存します。
2. 研究室のペア \((i, j)\) （ \(i < j\) ）を全探索します。
3. 各ペアに対して、2つの研究室のテーマ集合の積集合を求め、その要素数が \(K\) 以上であればカウンタを増やします。
4. 最終的なカウンタの値を出力します。

例えば、以下の入力があったとします：

3 2
2
ai ml
2
ml dl
2
ai dl

このとき、

• 研究室1: {“ai”, “ml”}
• 研究室2: {“ml”, “dl”}
• 研究室3: {“ai”, “dl”}

ペア (1,2): 共通テーマは {“ml”} → 1個（×） ペア (1,3): 共通テーマは {“ai”} → 1個（×） ペア (2,3): 共通テーマは {“dl”} → 1個（×）

よって答えは 0 です。

計算量

• 時間計算量: \(O(N^2 \cdot (M_{\max}))\)
  （ \(M_{\max}\) は1研究室あたりの最大テーマ数。setの積集合計算にかかる時間）
• 空間計算量: \(O(N \cdot M_{\max})\)

実装のポイント

• 各研究室のテーマは set で管理することで、効率的に共通要素の計算が可能です。
• ペアの走査は \(i < j\) の範囲で行い、重複を避ける必要があります。
• Pythonの input().split() はスペース区切りの文字列をリストに変換してくれるので、そのまま set() に入れると便利です。

ソースコード

N, K = map(int, input().split())

research_labs = []

for _ in range(N):
    M = int(input())
    themes = set(input().split())
    research_labs.append(themes)

count = 0

for i in range(N):
    for j in range(i + 1, N):
        common_themes = research_labs[i] & research_labs[j]
        if len(common_themes) >= K:
            count += 1

print(count)

---

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