概要

各時間帯（左側）と候補者（右側）からなる二部グラフを作り、「同じ候補者は1回しか使えない」という制約のもとで割り当て数を最大化する問題であり、最大二部マッチングを求めれば解けます。

考察

重要な気づき

• 時間帯 \(i\) に候補者 \(c\) を割り当て可能、という情報は「辺 \(i \to c\) がある」と見なせます。
• 「各時間帯に高々1人」「各候補者は高々1枠」という制約は、二部グラフでの マッチング（端点を共有しない辺集合）そのものです。
• したがって、求めたいのは「選べる辺の本数の最大」＝ 最大マッチングのサイズです。

素朴な方法がうまくいかない理由

• 貪欲法（各時間帯で空いている候補者を適当に埋める）は失敗します。
  例：
  
  • 時間帯1: 候補者 {1,2}
    
  • 時間帯2: 候補者 {1}
    時間帯1で候補者1を取ってしまうと、時間帯2が埋められず合計1枠しか埋まりません。しかし時間帯1→2、時間帯2→1とすれば2枠埋まります。
• 全探索（割当の組合せを試す）は最悪で指数時間になります。

解決方針

「いまの割当を少し組み替えて、割当数を1増やす」ことを繰り返す 増加路（augmenting path） の考え方を使います。
この増加路探索を高速に行う代表的手法が Hopcroft–Karp法です。

アルゴリズム

二部グラフの作成

• 左側頂点：時間帯 \(0 \ldots N-1\)
• 右側頂点：候補者 \(0 \ldots M-1\)
• 入力の「時間帯 \(i\) が候補者 \(c\) を選べる」ごとに辺 \(i \to c\) を張ります（コードでは adj[i] に候補者番号を追加）。

Hopcroft–Karp法（最大二部マッチング）

マッチングを増やす「増加路」をまとめて見つけることで高速化します。

• pair_u[u]：左頂点 \(u\) がマッチしている右頂点（いなければ -1）
• pair_v[v]：右頂点 \(v\) がマッチしている左頂点（いなければ -1）

手順は以下です。

1. BFS（層構造の構築）

   • まだマッチしていない左頂点（未割当の時間帯）を始点として幅優先探索し、
   • 「マッチ辺→非マッチ辺→マッチ辺→…」と辿る形で到達可能性を調べ、距離 dist を作ります。
   • どこかで未マッチの右頂点に到達できるなら、「増加路が存在する」ので次へ。

2. DFS（層に沿った増加路探索）

   • BFSで作った層（dist が 1 ずつ増える関係）を壊さない範囲でDFSし、実際に増加路を見つけます。
   • 増加路が見つかるたびに、その経路上の「マッチ/非マッチ」を反転させ、マッチング数が1増えます。

3. BFSで増加路が見つからなくなるまで 1〜2 を繰り返し、最終的なマッチング数を答えとして出力します。

この問題では「埋められる時間帯数」＝「マッチした左頂点数」＝「マッチングのサイズ」なので、そのまま最大マッチングを出せばOKです。

計算量

• 時間計算量: \(O(E\sqrt{V})\)
  ここで \(V = N + M\)、\(E = \sum_{i=1}^{N} K_i\)（張られる辺の総数）です。
• 空間計算量: \(O(V + E)\)（隣接リストとマッチング配列など）

実装のポイント

• 0-index化：入力の候補者番号は \(1 \ldots M\) なので、コードでは -1 して \(0 \ldots M-1\) にしています。

• 隣接リスト adj：adj[i] に「時間帯 i が選べる候補者（右頂点）」を列挙します。

• BFSで増加路の存在判定：Hopcroft–Karpでは、BFSで「未マッチ右頂点に到達できるか（found）」を判定し、到達できる層があるときだけDFSを回すのが肝です。

• DFSで失敗した頂点の距離をINFに：dist[u] = INF とすることで、同じ探索を何度も繰り返して無駄に時間を使うのを防ぎます。

  ソースコード

import sys
from collections import deque

def hopcroft_karp(adj, n_left, n_right):
    INF = 10**9
    pair_u = [-1] * n_left
    pair_v = [-1] * n_right
    dist = [0] * n_left

    def bfs():
        q = deque()
        for u in range(n_left):
            if pair_u[u] == -1:
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = INF

        found = False
        while q:
            u = q.popleft()
            for v in adj[u]:
                pu = pair_v[v]
                if pu != -1 and dist[pu] == INF:
                    dist[pu] = dist[u] + 1
                    q.append(pu)
                elif pu == -1:
                    found = True
        return found

    def dfs(u):
        for v in adj[u]:
            pu = pair_v[v]
            if pu == -1 or (dist[pu] == dist[u] + 1 and dfs(pu)):
                pair_u[u] = v
                pair_v[v] = u
                return True
        dist[u] = INF
        return False

    matching = 0
    while bfs():
        for u in range(n_left):
            if pair_u[u] == -1 and dfs(u):
                matching += 1
    return matching

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    adj = [[] for _ in range(N)]
    for i in range(N):
        Ki = next(it)
        for _ in range(Ki):
            c = next(it) - 1
            if 0 <= c < M:
                adj[i].append(c)

    ans = hopcroft_karp(adj, N, M)
    print(ans)

if __name__ == "__main__":
    main()

---

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