概要

\(N\) 個の研究室について、それぞれの研究テーマのリストが与えられます。2つの研究室を比較したとき、共通するテーマが \(K\) 個以上あるペアがいくつ存在するかを求める問題です。

考察

この問題を解くためには、すべての研究室の組み合わせ（ペア）を一つずつ確認し、共通するテーマの数を数える必要があります。

1. ペアの総数: 研究室の数 \(N\) は最大で \(500\) です。2つの研究室を選ぶペアの総数は \(\frac{N(N-1)}{2}\) で計算でき、\(N=500\) のとき \(\frac{500 \times 499}{2} = 124,750\) 通りとなります。この程度の数であれば、すべてのペアを全探索しても十分に間に合います。

2. 共通テーマの判定: 各ペアに対して「共通するテーマが何個あるか」を効率的に計算する必要があります。 素朴にリスト同士で比較すると時間がかかる場合がありますが、Pythonの集合（set）型を利用すると、積集合（共通部分）の計算を非常に高速に行うことができます。

3. 制約の確認: 研究テーマの数 \(M_i\) は最大 \(50\)、テーマ名の長さは最大 \(20\) です。全探索の過程で集合の比較を行っても、全体の計算量は実行時間制限内に収まると判断できます。

アルゴリズム

1. 各研究室が取り組んでいる研究テーマを読み込み、それぞれを set（集合）に格納してリスト labs に保持します。
2. 答えを格納する変数 ans を \(0\) で初期化します。
3. 二重ループを用いて、すべての研究室のペア \((i, j)\) （ただし \(0 \leq i < j < N\)）を順番に調べます。
4. 各ペアについて、集合の積演算（labs[i] & labs[j]）を行い、その結果の要素数（len）を取得します。
5. 要素数が \(K\) 以上であれば、ans を \(1\) 増やします。
6. 最終的な ans の値を出力します。

計算量

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

  • \(N\): 研究室の数（最大 \(500\)）
  • \(M\): 1研究室あたりの最大テーマ数（最大 \(50\)）
  • \(L\): テーマ名の最大長（最大 \(20\)）
  • ペアの探索に \(O(N^2)\)、集合の積計算に \(O(M)\)、文字列のハッシュ計算や比較に \(O(L)\) かかります。
  • \(500^2 \times 50 \times 20\) は最大でも \(2.5 \times 10^8\) 程度の定数倍がかかりますが、実際の積集合の計算は非常に効率化されているため、制限時間内に余裕を持って終了します。

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

  • すべての研究テーマを集合としてメモリに保持するための空間が必要です。

実装のポイント

• sys.stdin.read().split(): 入力データが複数行にわたる場合、このメソッドですべての単語をリストとして取得しておくと、インデックスを使って順番に処理できるため便利です。

• 集合（set）の活用: Pythonでは set_a & set_b と書くだけで、共通の要素を抽出した新しい集合を作成できます。その len() を取ることで、共通テーマの数を簡単に求められます。

  ソースコード

import sys

def main():
    # 全ての入力を読み込み、空白で分割してリストにする
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 研究室の数 N と閾値 K を取得
    N = int(data[0])
    K = int(data[1])
    
    # 各研究室の研究テーマを集合 (set) として格納するリスト
    labs = []
    idx = 2
    for _ in range(N):
        # 研究テーマの数 M_i を取得
        M_i = int(data[idx])
        idx += 1
        # M_i 個の研究テーマを読み込み、集合に変換
        themes = set(data[idx : idx + M_i])
        labs.append(themes)
        idx += M_i
        
    ans = 0
    # 全ての研究室のペア (i, j) について調査 (i < j)
    for i in range(N):
        for j in range(i + 1, N):
            # 2つの研究室の共通するテーマの数を計算
            # 集合の積演算 (&) を用いて共通要素を抽出し、その要素数を数える
            common_count = len(labs[i] & labs[j])
            
            # 共通するテーマが K 個以上あればカウントを増やす
            if common_count >= K:
                ans += 1
                
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    main()

この解説は gemini-3-flash-preview によって生成されました。