Day 120-Q2 — 病院・研修医問題（Hospital/Residents・多対一安定マッチング）

2026-08-12 赤色 Master / Phase 8+ ★★★★★★★★★ マッチング理論・Gale-Shapley多対一拡張

問題

$N$人の研修医と$M$個の病院がある。病院$j$には受け入れ可能な人数（定員）$\mathrm{cap}_j$ が定められている。

各研修医は$M$個すべての病院について、自分の希望順位（好きな順）を持つ。各病院は$N$人すべての研修医について、採用したい順位（好きな順）を持つ。

以下の条件を満たす「安定マッチング」を1つ求めよ（研修医最適安定マッチングが必ず存在することが知られている）。

  • 各研修医は高々1つの病院に割り当てられる
  • 各病院に割り当てられる研修医の数は定員以下
  • ブロッキングペア（研修医iが現在よりjを好み、かつjが定員に空きがある、または現在の最悪保持者よりiを好む状況）が存在しない

入力形式

N M
cap_1 ... cap_M
pref_r[1][1..M]
...
pref_r[N][1..M]
pref_h[1][1..N]
...
pref_h[M][1..N]

pref_r[i]は研修医iの病院への希望順位（病院番号を好きな順に並べた列）、pref_h[j]は病院jの研修医への希望順位。

制約

$1 \le N, M \le 300$
$1 \le \mathrm{cap}_j \le N$
pref_r[i]は1〜Mの順列
pref_h[j]は1〜Nの順列

入出力例

入力例1

3 2
2 1
2 1
1 2
1 2
1 2 3
3 1 2

出力例1

2
1
1

研修医1は病院2を最も希望し病院2は定員1で最初の申込者を受け入れる。研修医2・3は病院1を第一希望とし、定員2にちょうど収まる。

概念図: 提案→仮受理→弾き出しのサイクル

病院jの定員2に対して研修医が次々に提案する 研修医たち(free) 1 2 3 提案 病院j (定員2) held = {2, 3} 満杯のとき: 最悪保持者と比較 好ましければ入替 (弾き出し→再提案) 全員のnext_idxが尽きるか free集合が空になったら終了

ヒント（段階的開示）

ヒント1: 方向性
1対1の安定結婚問題（Gale-Shapley）はよく知られているが、本問は病院側が複数人を受け入れられる多対一マッチングである。研修医が病院に「提案」し、病院がその提案を「保留・拒否」するという同じ枠組みを、定員を考慮した形に拡張すればよい。
ヒント2: アプローチ
未割り当ての研修医に、まだ提案していない病院の中で最も希望順位の高い病院へ提案させる。病院側は定員に空きがあれば無条件で仮受理し、埋まっていれば現在の最悪保持者と比較して入れ替えるかどうかを決める。弾き出された研修医は再度提案キューに戻る。各病院に「現在の最悪保持者」を高速取得できる最大ヒープを持たせる。
ヒント3: 誘導（コード骨格） 
free = deque(range(1, N+1))
while free:
    i = free.popleft()
    if next_idx[i] >= M:
        continue
    j = pref_r[i][next_idx[i]]; next_idx[i] += 1
    r = rank[j][i]
    if len(held[j]) < cap[j]:
        held[j].add(i); matched_hospital[i] = j
        heapq.heappush(heap[j], (-r, i))
    else:
        while heap[j] and heap[j][0][1] not in held[j]:
            heapq.heappop(heap[j])
        worst_negr, worst_i = heap[j][0]
        if r < -worst_negr:
            heapq.heappop(heap[j]); held[j].discard(worst_i)
            matched_hospital[worst_i] = 0; free.append(worst_i)
            held[j].add(i); matched_hospital[i] = j
            heapq.heappush(heap[j], (-r, i))
        else:
            free.append(i)

模範解答 (Python)

import sys
import heapq
from collections import deque


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    cap = [0] * (M + 1)
    for j in range(1, M + 1):
        cap[j] = int(data[idx]); idx += 1

    pref_r = [None] * (N + 1)
    for i in range(1, N + 1):
        pref_r[i] = [int(data[idx + k]) for k in range(M)]
        idx += M

    rank = [None] * (M + 1)
    for j in range(1, M + 1):
        lst = [int(data[idx + k]) for k in range(N)]
        idx += N
        r = [0] * (N + 1)
        for pos, res in enumerate(lst):
            r[res] = pos
        rank[j] = r

    next_idx = [0] * (N + 1)
    matched_hospital = [0] * (N + 1)
    held = [set() for _ in range(M + 1)]
    heap = [[] for _ in range(M + 1)]

    free = deque(range(1, N + 1))
    while free:
        i = free.popleft()
        if next_idx[i] >= M:
            continue
        j = pref_r[i][next_idx[i]]
        next_idx[i] += 1
        r = rank[j][i]
        if len(held[j]) < cap[j]:
            held[j].add(i)
            matched_hospital[i] = j
            heapq.heappush(heap[j], (-r, i))
        else:
            while heap[j] and heap[j][0][1] not in held[j]:
                heapq.heappop(heap[j])
            worst_negr, worst_i = heap[j][0]
            worst_r = -worst_negr
            if r < worst_r:
                heapq.heappop(heap[j])
                held[j].discard(worst_i)
                matched_hospital[worst_i] = 0
                free.append(worst_i)
                held[j].add(i)
                matched_hospital[i] = j
                heapq.heappush(heap[j], (-r, i))
            else:
                free.append(i)

    out = [str(matched_hospital[i]) for i in range(1, N + 1)]
    print('\n'.join(out))


solve()
計算量: 各研修医は各病院に高々1回しか提案しないため、提案の総回数はO(NM)。ヒープ操作を含めてもO(NM log N)。N,M≤300のもとで乱択200試行のstress test（生成したマッチングにブロッキングペアが1つも存在しないこと、各病院の受け入れ人数が定員を超えないことを全探索で検証）を実際に実行し、全試行で安定性・定員制約を確認済み。

Step-by-Step 解説

11対1安定結婚問題からの拡張
古典的なGale-Shapleyは提案する側・される側がそれぞれ1人ずつ。多対一への拡張では「提案される側（病院）が複数人を保持できる」点だけが異なり、提案ロジック自体は変わらない。
2「弾き出し」の仕組み
定員が埋まっている状態で新しい提案が来たとき、現在保持している中で最も好ましくない研修医と比較する。新しい提案者の方が好ましければ弾き出し、その研修医を再び提案キューへ入れる。
3最悪保持者の高速な取得
病院ごとに(-順位, 研修医番号)を格納した最小ヒープを持つと先頭が常に最も好ましくない研修医になる。弾き出された研修医のエントリは遅延削除方式で無効化する。
4停止性と安定性
提案回数は研修医1人あたり高々M回なので全体でO(NM)回のループで必ず終了する。研修医提案型アルゴリズムが研修医最適の安定マッチングを出力することはRoth(1985)による拡張として証明されている。
5なぜ最悪保持者との比較だけで十分か
提案者が最悪保持者より好ましくなければ、他のどの保持者にも劣るので拒否が最適。好ましければ最悪保持者を弾き出して受け入れることでより良い集合を維持できる。

よくあるミス

ミス原因正しい書き方
ヒープから取り出した要素をそのまま最悪保持者と信じてしまう弾き出し済みの古いエントリがヒープに残っていることを考慮しない参照前に必ずheld[j]集合との整合性を確認し無効なエントリは読み飛ばす
拒否された研修医のnext_idxを進め忘れる、または二重に進めてしまう提案処理と拒否処理のタイミングを混同するnext_idx[i]は提案した直後に必ず1回だけ進める
病院側の希望順位を入力の並び順と誤解し数値をそのまま比較してしまう順位と研修医番号を混同するrank[j][研修医番号]=リスト中の位置という対応表を作る
定員0の病院を考慮しない実装にしてしまう制約でcap≥1と決め打ちして境界チェックを省略するlen(held[j])<cap[j]の判定だけで常に満杯として自然に扱われることを確認する

次のステップ

  • 発展: 研修医側にも「これ以下の病院なら未割り当ての方がマシ」という不完全な希望リストに対応させる。
  • 次回予告: Suffix Automaton拡張（辞書順K番目相異なる部分文字列）

自己評価

自分の回答

気づき・メモ