概要

\(N\) 個の研究室のうち、共通する研究テーマが \(K\) 個以上あるペアの数を数える問題です。

考察

問題の理解

各研究室は複数の研究テーマ（文字列）を持っており、2つの研究室の研究テーマの共通部分が \(K\) 個以上あれば「共同研究可能」なペアとしてカウントします。

具体例で考える

例えば、以下のような場合を考えます：

• 研究室1: {ai, ml, nlp}
• 研究室2: {ai, ml, cv}
• 研究室3: {biology, chemistry}

\(K = 2\) のとき：

• 研究室1と2の共通テーマ: {ai, ml} → 2個 ≥ 2 → 共同研究可能
• 研究室1と3の共通テーマ: {} → 0個 < 2 → 共同研究不可
• 研究室2と3の共通テーマ: {} → 0個 < 2 → 共同研究不可

答えは 1 となります。

アプローチの検討

• 全ペア探索: \(N\) 個の研究室から2つを選ぶ組み合わせは \(\frac{N(N-1)}{2}\) 通り
• \(N \leq 500\) なので、最大でも約 \(125,000\) ペア
• 各ペアの共通テーマ数を調べる必要がある

制約が小さいため、全ペアを愚直に調べても十分間に合います。

共通部分の効率的な計算

2つの集合の共通部分を求めるには、集合（set）のデータ構造を使うと効率的です。Pythonでは set 型を使い、& 演算子（積集合）で共通要素を取得できます。

アルゴリズム

1. 入力の読み込み: 各研究室の研究テーマを set（集合）として保存する
2. 全ペアの探索: 2重ループで全ての研究室ペア \((i, j)\)（\(i < j\)）を列挙
3. 共通テーマ数の計算: labs[i] & labs[j] で積集合を求め、その要素数を取得
4. 条件判定: 共通テーマ数が \(K\) 以上ならカウンタを増やす
5. 結果の出力: 最終的なカウンタの値を出力

計算量

• 時間計算量: \(O(N^2 \times M)\)

  • \(N^2\) ペアそれぞれについて、集合の積集合を計算
  • 各積集合の計算は最大 \(O(M)\)（\(M\) は各研究室の最大テーマ数、最大50）
  • \(500^2 \times 50 = 12,500,000\) 程度で十分高速

• 空間計算量: \(O(N \times M)\)

  • 各研究室のテーマを集合として保存

実装のポイント

1. 集合（set）を使う: リストで共通要素を探すより、set の & 演算子を使う方が高速かつ簡潔に書けます。

2. ペアの重複を避ける: for j in range(i + 1, N) とすることで、\((i, j)\) と \((j, i)\) を重複して数えることを防ぎます。

3. 入力の読み込み: 各研究室について2行ずつ（テーマ数と実際のテーマ）読み込むことに注意が必要です。

# 集合の積集合（共通部分）の例
set1 = {"ai", "ml", "nlp"}
set2 = {"ai", "ml", "cv"}
common = set1 & set2  # {"ai", "ml"}
print(len(common))    # 2

ソースコード

def main():
    import sys
    input = sys.stdin.read().split('\n')
    idx = 0
    
    first_line = input[idx].split()
    N = int(first_line[0])
    K = int(first_line[1])
    idx += 1
    
    labs = []
    for i in range(N):
        M = int(input[idx])
        idx += 1
        themes = set(input[idx].split())
        idx += 1
        labs.append(themes)
    
    count = 0
    for i in range(N):
        for j in range(i + 1, N):
            common = len(labs[i] & labs[j])
            if common >= K:
                count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

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