Day 094-Q1 — 安定マッチング問題（Gale-Shapley Algorithm）

2026-07-17 赤色 Master / Phase 8+ ★★★★★★★★★ 安定マッチング・男性最適安定マッチング

問題

$N$ 人の男性と $N$ 人の女性がいる。各男性は $N$ 人の女性全員に対する選好リストを、各女性も $N$ 人の男性全員に対する選好リストを持つ。

マッチングが安定であるとは、「男性 $m$ と女性 $w$ が互いに現在のパートナーよりも相手を好んでいる」という不安定なペアが存在しないことをいう。男性がプロポーズする Gale-Shapley アルゴリズムを用いて、男性全員にとって最も好ましい安定マッチング（男性最適安定マッチング）を求めよ。

入力形式

N
m_pref_1
:
m_pref_N
w_pref_1
:
w_pref_N

m_pref_i: 男性iの選好リスト（女性番号を好きな順に並べたN個の整数）。w_pref_i: 女性iの選好リスト（男性番号を好きな順に並べたN個の整数）。

制約

$1 \le N \le 2000$
各選好リストは $1..N$ の順列

入出力例

入力例1

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

出力例1

1 2 3

出力のi番目は「男性iとマッチした女性の番号」。この例では男性1-女性1、男性2-女性2、男性3-女性3が男性最適安定マッチング。

概念図

男性からのプロポーズ → 女性が仮受理／破棄 男性 女性 m1 m2 m3 w1 w2 w3 m1→w1 (受理) m2→w2 (受理) m3→w1 (拒否: w1はm1をより好む) 拒否されたm3は次候補w2へ→さらに拒否→w3で成立

ヒント（段階的開示）

ヒント1: 方向性
貪欲に「一番好きな相手同士をペアにする」だけでは安定性が壊れる。一度成立したペアを仮の状態として扱い、より良い提案が来たら破棄する仕組みを考えよ。
ヒント2: アプローチ
未婚の男性が選好リストの上から順に、まだプロポーズしていない女性にプロポーズしていく。女性は「今の仮の相手」と「新しい提案者」を比べ、選好リストで順位が高い方を残し、もう一方を未婚に戻す。全員が結ばれるまで繰り返す。
ヒント3: 誘導（コード骨格） 
next_proposal = [0]*(n+1)
woman_partner = [0]*(n+1)   # 0 = 未婚
free_men = list(range(n, 0, -1))

while free_men:
    m = free_men.pop()
    w = man_pref[m][next_proposal[m]]
    next_proposal[m] += 1
    if woman_partner[w] == 0:
        woman_partner[w] = m
    elif woman_rank[w][m] < woman_rank[w][woman_partner[w]]:
        free_men.append(woman_partner[w])
        woman_partner[w] = m
    else:
        free_men.append(m)

woman_rank[w][m]は女性wにとっての男性mの順位（小さいほど好み）を事前計算しておく。

模範解答 (Python)

import sys


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1

    man_pref = []
    for _ in range(n):
        row = [int(data[idx + j]) for j in range(n)]
        idx += n
        man_pref.append(row)

    woman_pref = []
    for _ in range(n):
        row = [int(data[idx + j]) for j in range(n)]
        idx += n
        woman_pref.append(row)

    woman_rank = [[0] * (n + 1) for _ in range(n + 1)]
    for w in range(1, n + 1):
        for rank, m in enumerate(woman_pref[w - 1]):
            woman_rank[w][m] = rank

    next_proposal = [0] * (n + 1)
    woman_partner = [0] * (n + 1)
    free_men = list(range(n, 0, -1))

    while free_men:
        m = free_men.pop()
        w = man_pref[m - 1][next_proposal[m]]
        next_proposal[m] += 1
        if woman_partner[w] == 0:
            woman_partner[w] = m
        elif woman_rank[w][m] < woman_rank[w][woman_partner[w]]:
            free_men.append(woman_partner[w])
            woman_partner[w] = m
        else:
            free_men.append(m)

    man_partner = [0] * (n + 1)
    for w in range(1, n + 1):
        man_partner[woman_partner[w]] = w

    sys.stdout.write(' '.join(str(man_partner[m]) for m in range(1, n + 1)) + "\n")


main()
計算量: 各男性は最大N回プロポーズするため総プロポーズ回数は $O(N^2)$。女性側の判定は事前計算した順位表で $O(1)$。

Step-by-Step 解説

1順位表の構築
女性側の「男性番号→順位」の逆引き表woman_rankを作り、比較を $O(1)$ にする。
2未婚男性のスタック管理
free_menに未婚男性を積み、1人ずつ取り出してプロポーズさせる。
3プロポーズと判定
女性が未婚なら即受理。既に相手がいればwoman_rankで比較し、好みの高い方を残す。
4停止性と出力
各男性のプロポーズ回数は高々N回なので必ず停止する。woman_partnerからman_partnerを逆算する。

よくあるミス

ミス原因正しい書き方
女性側の好みを毎回index()で線形探索順位表を事前計算していないwoman_rank[w][m]を $O(1)$ で引けるように前処理
同じ女性に何度もプロポーズするnext_proposalのインクリメント忘れプロポーズのたびに必ず+= 1
女性最適マッチングと勘違い問題文の「男性最適」の見落とし男性からプロポーズするアルゴリズムを実装
安定性を「片方だけが好む」で判定不安定ペアの定義の理解不足Gale-Shapleyの出力は自動的に安定になることを利用

次のステップ

  • 発展: 定員が複数人の「病院・研修医マッチング問題」（多対一安定マッチング）への拡張
  • 発展: 選好リストが不完全な場合の安定マッチング
  • 次回予告: Tonelli-Shanks法（mod p の平方剰余）

自己評価

自分の回答

気づき・メモ