概要

この問題は、\(N\) 個の「時間帯」と \(M\) 人の「アルバイト候補者」を、与えられた条件（勤務可能かどうか）に基づいてペアにする問題です。各時間帯には最大 1 人、各候補者も最大 1 つの時間帯にしか割り当てられないという制約の下で、最大で何組のペアを作れるかを求めます。

これはグラフ理論における「二部マッチング（Maximum Bipartite Matching）」の最大値を求める問題として解くことができます。

考察

1. 二部グラフとしての整理

この問題を整理すると、以下の 2 つのグループに分けられます。 - グループ A：時間帯 \(1, 2, \ldots, N\) - グループ B：候補者 \(1, 2, \ldots, M\)

「時間帯 \(i\) に候補者 \(j\) が勤務可能である」という条件を、グループ A のノード \(i\) とグループ B のノード \(j\) を結ぶ「辺」とみなすと、このグラフは異なるグループ間のみに辺が存在する二部グラフになります。

2. なぜ単純な「早い者勝ち」ではダメなのか？

例えば、以下のようなケースを考えます。 - 時間帯 1：候補者 A、候補者 B が勤務可能 - 時間帯 2：候補者 A のみ勤務可能

もし時間帯 1 に「早い者勝ち」で候補者 A を割り当ててしまうと、時間帯 2 には誰も割り当てられなくなり、合計 1 組になります。しかし、時間帯 1 に候補者 B、時間帯 2 に候補者 A を割り当てれば、合計 2 組に増やすことができます。

このように、ある時間帯の選択が他の時間帯の選択肢を奪ってしまうため、最適な組み合わせを見つけるには「後から割り当てを調整する」仕組みが必要です。

アルゴリズム

最大二部マッチングを解くために、増加路（Augmenting Path）を探すアルゴリズム（DFS を用いた手法）を使用します。

1. 初期化: すべての時間帯と候補者を未割り当ての状態にします。
2. マッチングの試行: 各時間帯 \(i = 1 \ldots N\) について、以下の手順で割り当てを試みます。
3. DFS（深層優先探索）による探索:
   • 時間帯 \(i\) が勤務可能な候補者 \(v\) を一人ずつ確認します。
   • もし候補者 \(v\) がまだ誰にも割り当てられていなければ、即座に \(i\) と \(v\) をペアにします。
   • もし候補者 \(v\) が既に別の時間帯 \(i'\) に割り当てられている場合、「時間帯 \(i'\) が \(v\) 以外の別の候補者へ移動できるか」を再帰的に探索します。
   • 移動ができれば、空いた候補者 \(v\) を時間帯 \(i\) に割り当てます。これを「増加路が見つかった」と言います。
4. カウント: 増加路が見つかるたびに、マッチング数を 1 増やします。

このアルゴリズムは、一度決めたペアを必要に応じて解消し、別のペアに組み替えることで、全体のペア数を最大化します。

計算量

• 時間計算量: \(O(N \times (N + E))\)
  • ここで \(E\) は「勤務可能」という情報の総数（辺の数）です。
  • 各時間帯（\(N\) 個）から DFS を開始し、各 DFS では最大ですべての辺を走査するため、この計算量になります。今回の制約（\(N, M \leq 100\)）では十分に高速に動作します。
• 空間計算量: \(O(N + M + E)\)
  • グラフの隣接リストと、マッチング状況を保持する配列のメモリが必要です。

実装のポイント

• match 配列: match[v] = u とすることで、候補者 v が現在どの時間帯 u に割り当てられているかを管理します。

• visited 配列: 1 つの時間帯から始まる DFS の中で、同じ候補者を何度も調べないようにするために使用します。これにより無限ループを防ぎます。

• 再帰の深さ: \(N\) が大きくなる場合は sys.setrecursionlimit が必要になることがありますが、今回は \(N=100\) なので標準設定でも問題ありません。

  ソースコード

import sys

# 再帰上限を増やす（念のため）
sys.setrecursionlimit(2000)

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    m = int(input_data[1])
    
    adj = []
    current = 2
    for _ in range(n):
        k = int(input_data[current])
        candidates = []
        for j in range(k):
            candidates.append(int(input_data[current + 1 + j]))
        adj.append(candidates)
        current += (k + 1)

    # 二部マッチングのための変数
    # match[v] は候補者 v がどの時間帯に割り当てられているかを保持する
    match = [-1] * (m + 1)
    
    def dfs(u, visited):
        """
        時間帯 u から始まる増加路を探す
        """
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                # 候補者 v がまだ誰にも割り当てられていないか、
                # 既に割り当てられている時間帯 match[v] に対して別の候補者を割り当て直せる場合
                if match[v] < 0 or dfs(match[v], visited):
                    match[v] = u
                    return True
        return False

    ans = 0
    for i in range(n):
        # 各時間帯についてマッチングを試みる
        visited = [False] * (m + 1)
        if dfs(i, visited):
            ans += 1
            
    print(ans)

if __name__ == "__main__":
    solve()

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