概要

時間帯とアルバイト候補者を対応させる問題で、二部グラフの最大マッチングを求める典型問題です。

考察

問題の言い換え

この問題は以下のように整理できます： - 左側に \(N\) 個の「時間帯」ノード - 右側に \(M\) 個の「候補者」ノード - 時間帯 \(i\) に候補者 \(j\) が勤務可能なら、辺 \((i, j)\) を張る

このグラフで、各ノードが高々1本の辺にしか接続しないようにできるだけ多くの辺を選ぶ問題になります。これはまさに二部グラフの最大マッチング問題です。

素朴なアプローチの問題点

全ての割り当てパターンを試す場合、最悪で \(O(M^N)\) 通りの組み合わせを調べる必要があり、\(N, M \leq 100\) では到底間に合いません。

解決方法

二部グラフの最大マッチングには効率的なアルゴリズムが存在します： - Hopcroft-Karp法: \(O(E\sqrt{V})\) で求められる - Hungarian法や単純な増加路探索も使えます

アルゴリズム

二部マッチングの基本的な考え方

増加路（augmenting path） を見つけて、マッチングを1つずつ増やしていきます。

増加路とは、「マッチングに含まれない辺」から始まり、「マッチングに含まれる辺」と「含まれない辺」を交互にたどって、「マッチングに含まれない辺」で終わるパスです。

Hopcroft-Karp法の流れ

1. BFSフェーズ: マッチングされていない左側ノードから始めて、最短の増加路の長さを見つける
2. DFSフェーズ: 見つかった最短長の増加路を全て同時に処理して、マッチングを更新
3. 増加路が見つからなくなるまで繰り返す

例: N=3, M=3
時間帯1 → 候補者1, 2
時間帯2 → 候補者1
時間帯3 → 候補者2, 3

最大マッチング:
時間帯1 ↔ 候補者2
時間帯2 ↔ 候補者1
時間帯3 ↔ 候補者3
→ 答えは 3

計算量

• 時間計算量: \(O(E\sqrt{V})\)

  • \(V = N + M\)（頂点数）、\(E = \sum K_i\)（辺数）
  • 最悪で \(E = NM\)、\(V = N + M\) なので \(O(NM\sqrt{N+M})\)
  • \(N, M \leq 100\) なら十分高速

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

  • 隣接リストの保存に \(O(E)\)
  • マッチング配列に \(O(N + M)\)

実装のポイント

1. 0-indexed への変換: 入力では候補者番号が \(1\) から始まるため、c - 1 として0-indexedに変換

2. 2つの配列でマッチングを管理:

   • match_left[i]: 時間帯 \(i\) に割り当てられた候補者（-1なら未割り当て）
   • match_right[j]: 候補者 \(j\) が割り当てられた時間帯（-1なら未割り当て）

3. BFSで距離を計算: マッチングされていない時間帯からの距離を計算し、DFSで効率的に増加路を探索

4. DFSでの枝刈り: dist[u] = inf として、同じノードを再訪問しないようにする

   ソースコード

def main():
    import sys
    from collections import deque
    
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    # Build bipartite graph
    # Left side: time slots (0 to N-1)
    # Right side: candidates (0 to M-1)
    
    # For each time slot, store list of candidates who can work
    adj = [[] for _ in range(N)]
    
    for i in range(N):
        K = int(input_data[idx]); idx += 1
        for _ in range(K):
            c = int(input_data[idx]) - 1; idx += 1  # 0-indexed
            adj[i].append(c)
    
    # Maximum bipartite matching using Hopcroft-Karp algorithm
    # match_left[i] = candidate matched to time slot i (-1 if unmatched)
    # match_right[j] = time slot matched to candidate j (-1 if unmatched)
    
    match_left = [-1] * N
    match_right = [-1] * M
    
    def bfs():
        dist = [float('inf')] * N
        queue = deque()
        for i in range(N):
            if match_left[i] == -1:
                dist[i] = 0
                queue.append(i)
        
        found = False
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                next_u = match_right[v]
                if next_u == -1:
                    found = True
                elif dist[next_u] == float('inf'):
                    dist[next_u] = dist[u] + 1
                    queue.append(next_u)
        
        return found, dist
    
    def dfs(u, dist):
        for v in adj[u]:
            next_u = match_right[v]
            if next_u == -1 or (dist[next_u] == dist[u] + 1 and dfs(next_u, dist)):
                match_left[u] = v
                match_right[v] = u
                return True
        dist[u] = float('inf')
        return False
    
    matching = 0
    while True:
        found, dist = bfs()
        if not found:
            break
        for i in range(N):
            if match_left[i] == -1:
                if dfs(i, dist):
                    matching += 1
    
    print(matching)

if __name__ == "__main__":
    main()

---

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