概要

各研究室が持つ研究テーマの集合について、共通テーマ数が \(K\) 個以上となる研究室ペア \((i<j)\) の数を数えます。

考察

重要なのは「2つの集合の共通要素数（積集合のサイズ）」を高速に数えることです。

• 素朴にやると、各ペア \((i,j)\) について「テーマ文字列が一致するか」を全探索しがちです。
  例えば、研究室 \(i\) の全テーマ \(M_i\) と研究室 \(j\) の全テーマ \(M_j\) を二重ループで照合すると \(O(M_i M_j)\) かかります。これを全ペアで行うと最大で \( O\left(\sum_{i<j} M_i M_j\right) \approx O(N^2 \cdot 50^2)\) となり、Pythonだと定数も大きくなりやすく、ギリギリ〜TLEのリスクが出ます（文字列比較も重い）。

• 解決方針は次の2点です。

  1. テーマ文字列を整数IDに変換して比較を軽くする（辞書で圧縮）。
  2. 各研究室のテーマIDをソートし、2本ポインタで共通数を数える。
     これなら1ペアあたり \(O(M_i + M_j)\) で数えられます。

さらに、共通数が \(K\) に到達した時点で打ち切ったり、「残り全部一致しても \(K\) に届かない」場合に早期終了することで、無駄な走査を減らします。

アルゴリズム

1. テーマの座標圧縮（ID化）

   • すべてのテーマ文字列に対して、初めて見た文字列には新しい整数IDを割り当てます。
   • 各研究室は「テーマIDのリスト」を持つようにします。
   • 研究室ごとにそのIDリストをソートします。

2. 全ペアを調べ、2本ポインタで共通数を数える

   • 研究室 \(i\) と \(j\) のソート済みID配列を \(a, b\) とする。
   • ポインタ \(p, q\) を先頭から進めていきます。
     • \(a[p] == b[q]\) なら共通テーマなのでカウントを増やし、両方進める
     • 小さい方のポインタを進める（集合のマージと同じ要領）
   • カウントが \(K\) に達したら、そのペアは「共同研究可能」なので答えに加算して打ち切り。
   • また、途中で \(\text{cnt} + \min(\text{残り}a,\ \text{残り}b) < K\) となったら、これ以上進めても \(K\) に届かないので打ち切り。

3. 小さすぎる研究室は最初から除外

   • そもそも \(M_i < K\) の研究室は、誰と組んでも共通が \(K\) に届かないのでスキップします。
   • ペア側でも \(\min(M_i, M_j) < K\) ならスキップします。

（例）

• \(K=2\)、研究室A: {a,b,c}、研究室B: {b,c,d}
  ID化してソート済み配列を突き合わせると、b,c が一致してすぐ \(2\) 個到達 → 共同研究可能。

計算量

• 時間計算量:
  
  • ID化とソート：\(\displaystyle O\left(\sum_i M_i \log M_i\right)\)（各 \(M_i \le 50\) なので軽い）
    
  • ペア判定：最悪 \(\displaystyle O\left(\sum_{i<j} (M_i+M_j)\right) = O(N^2 \cdot 50)\)
    よって全体として概ね \(O(N^2 \cdot 50)\) 程度（早期終了でさらに減ることが多い）
• 空間計算量:
  
  • 研究室のID配列と辞書：\(\displaystyle O\left(\sum_i M_i\right)\)

実装のポイント

• 入力は sys.stdin.buffer.read().split() でまとめて読み、速度を確保しています（テーマは bytes のまま辞書キーにして高速化）。

• テーマを整数IDに変換してから処理すると、比較が軽くなります。

• 2本ポインタ中の早期終了条件
  cnt + min(la-p, lb-q) < K
  は「残り全部一致しても届かない」ことを意味し、無駄な走査を防げます。

• 共通数が \(K\) に到達した瞬間にペアを確定して break することで、平均的に高速になります。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    K = int(next(it))

    theme_id = {}
    nxt_id = 0
    labs = []

    for _ in range(N):
        Mi = int(next(it))
        ids = []
        for _ in range(Mi):
            w = next(it)  # bytes
            if w in theme_id:
                ids.append(theme_id[w])
            else:
                theme_id[w] = nxt_id
                ids.append(nxt_id)
                nxt_id += 1
        ids.sort()
        labs.append(ids)

    ans = 0
    for i in range(N):
        a = labs[i]
        la = len(a)
        if la < K:
            continue
        for j in range(i + 1, N):
            b = labs[j]
            lb = len(b)
            if lb < K or (la if la < lb else lb) < K:
                continue

            p = q = cnt = 0
            while p < la and q < lb:
                # early stop if even taking all remaining can't reach K
                if cnt + (la - p if la - p < lb - q else lb - q) < K:
                    break
                ap = a[p]
                bq = b[q]
                if ap == bq:
                    cnt += 1
                    if cnt == K:
                        ans += 1
                        break
                    p += 1
                    q += 1
                elif ap < bq:
                    p += 1
                else:
                    q += 1

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

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