概要

参加者にプレゼントを配るとき、希望を満たす人数を最大化する問題。これは二部グラフにおける最大流問題としてモデル化できる。

考察

この問題は「誰に」「どのプレゼント」を配るかという組み合わせ最適化問題です。単純には、全組み合わせを試すことで解を求めることができますが、参加者数 \(N\) やプレゼントの種類数 \(M\) が最大500もあるため、全探索では計算量が爆発し、現実的ではありません。

重要な観察として、「各参加者は高々1つのプレゼントを受け取る」「各プレゼントは用意された数までしか配れない」という制約があります。また、参加者が満足するのは「自分が希望するプレゼントのうちどれか一つを受け取ること」です。

このような「マッチング」を最適に行うには、二部グラフの最大流問題として定式化することが有効です。

具体的には以下のようなグラフを作ります：

• 左側の頂点：参加者（\(1\) から \(N\)）
• 右側の頂点：プレゼントの種類（\(1\) から \(M\)）
• ソース \(S\) から各参加者へ容量1の辺を張る（各人は1つだけ受け取る）
• 各参加者から、その人が希望するプレゼントへ容量1の辺を張る（希望したものの中から選ぶ）
• 各プレゼントからシンク \(T\) へ、そのプレゼントの個数 \(B_i\) を容量とする辺を張る（個数制限）

このようにして作ったグラフ上で最大流を求めると、それが「満足する参加者の最大人数」となります。

アルゴリズム

この問題は 最大流問題（Max Flow Problem） として解くことができます。具体的には Dinic 法 を使用して解いています。

手順：

1. グラフ構築

   • 頂点集合：ソース \(S\)、参加者 \(1..N\)、プレゼント \(1..M\)、シンク \(T\)
   • 辺：
     • \(S \rightarrow\) 各参加者：容量1
     • 各参加者 \(\rightarrow\) 希望するプレゼント：容量1
     • 各プレゼント \(\rightarrow T\)：容量 \(B_i\)

2. 最大流を求める

   • Dinic法などのアルゴリズムを使用して、ソースからシンクへの最大流を計算する。

3. 答えの出力

   • 得られた最大流の値が、満足する参加者の最大人数となる。

計算量

• 時間計算量: \(O(N \cdot M^2)\) （Dinic法による最大流の計算量。正確には \(O(E \cdot V^2)\) だが、今回のグラフサイズで抑えられる）
• 空間計算量: \(O(N + M + E)\) （グラフの隣接リスト表現に必要なメモリ）

実装のポイント

• グラフの頂点番号に注意すること（参加者は1〜N、プレゼントはN+1〜N+Mなど）

• 辺の追加時に逆辺も同時に設定する（最大流アルゴリズムの性質上必須）

• Dinic法の実装では bfs でレベルグラフを構築し、dfs で増加分を探索する流れになる

• Pythonの再帰回数制限に注意（特にDFS深さが大きい場合）

  ソースコード

from collections import deque

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    
    B = [0] * (M + 1)
    for i in range(1, M + 1):
        B[i] = int(data[idx]); idx += 1

    # グラフを作る
    # left: 1..N (参加者), right: 1..M (プレゼント)
    # ソース: 0, シンク: N+M+1

    # グラフの隣接リスト表現（辺の容量付き）
    # 使用する頂点番号: 0（source）, 1..N（参加者）, N+1..N+M（プレゼント）, N+M+1（sink）

    INF = 10**9
    source = 0
    sink = N + M + 1

    # グラフ構築
    # 隣接リスト: graph[v] = [(to, cap, rev_index)]
    graph = [[] for _ in range(N + M + 2)]

    def add_edge(fr, to, cap):
        graph[fr].append([to, cap, len(graph[to])])
        graph[to].append([fr, 0, len(graph[fr]) - 1])

    # source -> 参加者: 容量1
    for i in range(1, N + 1):
        add_edge(source, i, 1)

    # 参加者 -> 希望するプレゼント: 容量1
    for i in range(1, N + 1):
        K = int(data[idx]); idx += 1
        for _ in range(K):
            c = int(data[idx]); idx += 1
            add_edge(i, N + c, 1)

    # プレゼント -> sink: 容量B[c]
    for c in range(1, M + 1):
        add_edge(N + c, sink, B[c])

    # 最大流を求める（Dinic法）
    def bfs():
        level[:] = [-1] * (N + M + 2)
        queue = deque([source])
        level[source] = 0
        while queue:
            v = queue.popleft()
            for to, cap, _ in graph[v]:
                if level[to] == -1 and cap > 0:
                    level[to] = level[v] + 1
                    queue.append(to)
        return level[sink] != -1

    def dfs(v, t, f):
        if v == t:
            return f
        while iter[v] < len(graph[v]):
            to, cap, rev = graph[v][iter[v]]
            if cap > 0 and level[v] < level[to]:
                d = dfs(to, t, min(f, cap))
                if d > 0:
                    graph[v][iter[v]][1] -= d
                    graph[to][rev][1] += d
                    return d
            iter[v] += 1
        return 0

    def max_flow():
        flow = 0
        while True:
            if not bfs():
                break
            iter[:] = [0] * (N + M + 2)
            while True:
                f = dfs(source, sink, INF)
                if f == 0:
                    break
                flow += f
        return flow

    level = [-1] * (N + M + 2)
    iter = [0] * (N + M + 2)
    result = max_flow()
    print(result)

solve()

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