概要

この問題は、時間帯とアルバイト候補者の間に二部グラフを作り、最大マッチングを求めることで、.staffを最大何時間割り当てられるかを求める問題です。

考察

各時間帯には1人だけスタッフを配置でき、各スタッフも最大1つの時間帯にしか割り当てられません。これは典型的な「二部マッチング」の問題です。

例えば、時間帯1に候補者1,2が対応し、時間帯2に候補者2,3が対応している場合、候補者2をどちらの時間帯に割り当てるかによって結果が変わります。貪欲に割り当てると最適解にならないことがあるため、効率的なアルゴリズムが必要です。

このような問題では、全時間帯に対してスタッフをうまく割り当てる最大数を求めるために、「最大二部マッチング」アルゴリズム（特にHopcroft-KarpやDFSベースの増加路法）が有効です。

アルゴリズム

この問題は、時間帯を一方の頂点集合、アルバイト候補者をもう一方の頂点集合とした二部グラフの最大マッチング問題として解けます。

具体的には以下のように動作します： 1. 各時間帯から、その時間帯で働ける候補者へ辺を張った二部グラフを作る。 2. 各時間帯に対して、未使用の候補者がいればそれを割り当てる。 3. すでに使われている候補者の場合は、その候補者が割り当てられている時間帯から別の候補者を探して再帰的に割り当てを調整する（増加道を探す）。 4. 上記処理をすべての時間帯に行い、マッチングできた数をカウントする。

コード中では dfs 関数を使って、ある時間帯から始まる増加道があるか探索しています。

たとえば、時間帯 A → 候補者 X がすでにマッチしているとき、X が所属する時間帯 B から別の候補者 Y を探して割り当て直すことで、A に X を割り当てることができるようになります。

計算量

• 時間計算量: \(O(N \cdot M \cdot N) = O(N^2 M)\) （DFSによる増加道探索が最大 \(N\) 回、各辺を走査する）
• 空間計算量: \(O(N + M + \sum K_i)\) （グラフの隣接リストとマッチング情報を保存）

※実際にはHopcroft-Karpアルゴリズムなどを用いれば \(O(E \sqrt{V})\) まで改善可能ですが、制約が小さいのでDFSベースでも十分高速です。

実装のポイント

• グラフの構築時に、入力を1-indexedとして読み込んでいる点に注意。

• match_worker_to_slot および match_slot_to_worker の両方を持つことで双方向の確認が容易になる。

• DFS内で訪問済みフラグ visited を使い、無限ループを回避している。

• 入力のパース部分では高速化のために一度に全部読み込んで処理している。

  ソースコード

from collections import defaultdict

def max_bipartite_matching(N, M, candidates):
    # Build graph: time slot -> list of available workers
    graph = candidates
    
    # match[u] = v means worker u is assigned to time slot v (1-based)
    # -1 means unassigned
    match_worker_to_slot = [-1] * (M + 1)  # 1-based indexing for workers
    match_slot_to_worker = [-1] * (N + 1)   # 1-based indexing for slots
    
    def dfs(slot, visited):
        for worker in graph[slot]:
            if visited[worker]:
                continue
            visited[worker] = True
            
            # If the worker is free or we can find an alternative assignment
            if match_worker_to_slot[worker] == -1 or dfs(match_worker_to_slot[worker], visited):
                match_worker_to_slot[worker] = slot
                match_slot_to_worker[slot] = worker
                return True
        return False

    result = 0
    for slot in range(1, N + 1):
        visited = [False] * (M + 1)
        if dfs(slot, visited):
            result += 1
            
    return result

# Read input
import sys
input = sys.stdin.read
data = input().split()

idx = 0
N = int(data[idx])
idx += 1
M = int(data[idx])
idx += 1

candidates = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
    K = int(data[idx])
    idx += 1
    for _ in range(K):
        c = int(data[idx])
        idx += 1
        candidates[i].append(c)

print(max_bipartite_matching(N, M, candidates))

この解説は qwen3-coder-480b によって生成されました。