Day 121-Q4 | Stable Roommates Problem（安定ルームメイト問題）

問題

$N$人（$N$は偶数）がおり、各人は自分以外の$N-1$人全員に対する選好順位を持っている。この$N$人を2人1組の$N/2$組のペアに分割したい。

ペア分割が不安定であるとは、ある2人 $a, b$ が互いに現在のパートナーよりも相手を好む状態が存在することをいう。そのような2人が存在しない分割を安定マッチングと呼ぶ。安定マッチングが存在するなら1つ出力し、存在しないなら-1を出力せよ。

入力形式

N
pref_1
pref_2
...
pref_N

pref_i は人 $i$（0-indexed）の選好順位を好きな順に並べた $N-1$ 個の整数。

制約

$2 \le N \le 500$（偶数）

各pref_iは$\{0,\ldots,N-1\}\setminus\{i\}$の順列

入出力例

入力例1

出力例1

0 1
2 3

入力例2（安定マッチングが存在しない典型例）

出力例2

-1

概念図: 三すくみの循環と回転除去

ヒント（段階的開示）

ヒント1: 方向性

Gale-Shapleyは「男性グループ」と「女性グループ」という2つの独立したグループの間でマッチングを作るので常に安定マッチングが存在する。しかしルームメイト問題は全員が同じ1つのグループに属し、互いに互いを選好するため、安定マッチングが存在しない入力が起こりうる。

ヒント2: アプローチ

Irvingのアルゴリズムは2フェーズ。フェーズ1（提案）: Gale-Shapleyと同様に各人が選好リストの先頭から提案し、拒否された側はより悪い候補をリストから削除する。リストが空になれば不可能と確定。フェーズ2（サイクル除去）: 「全順回転（rotation）」と呼ばれる循環構造を見つけて除去する操作を、各人のリストがちょうど1人になるまで繰り返す。

ヒント3: 誘導（コード骨格）

def phase1():
    free = list(range(N))
    holder = [None] * N
    proposal_ptr = [0] * N
    while free:
        p = free.pop()
        if proposal_ptr[p] >= len(pref[p]):
            return False  # 安定マッチング不可能
        q = pref[p][proposal_ptr[p]]
        proposal_ptr[p] += 1
        if holder[q] is None:
            holder[q] = p
        elif rank[q][p] < rank[q][holder[q]]:
            free.append(holder[q])
            holder[q] = p
        else:
            free.append(p)
    return True

模範解答 (Python)

import sys


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

    pref = []
    for i in range(N):
        row = [int(data[idx + k]) for k in range(N - 1)]
        idx += N - 1
        pref.append(row)

    rank = [[0] * N for _ in range(N)]
    for i in range(N):
        for order, j in enumerate(pref[i]):
            rank[i][j] = order

    pref_list = [list(p) for p in pref]

    def remove_pref(a, b):
        if b in pref_list[a]:
            pref_list[a].remove(b)
        if a in pref_list[b]:
            pref_list[b].remove(a)

    holder = [-1] * N
    free = list(range(N))

    while free:
        p = free.pop()
        if not pref_list[p]:
            print(-1)
            return
        q = pref_list[p][0]
        if holder[q] == -1:
            holder[q] = p
        else:
            cur = holder[q]
            if rank[q][p] < rank[q][cur]:
                holder[q] = p
                free.append(cur)
                remove_pref(cur, q)
            else:
                free.append(p)
                remove_pref(p, q)
                continue
        qlist = pref_list[q]
        pos = qlist.index(p)
        worse = qlist[pos + 1:]
        for w in list(worse):
            remove_pref(q, w)

    for i in range(N):
        if not pref_list[i]:
            print(-1)
            return

    def get_second(i):
        return pref_list[i][1] if len(pref_list[i]) > 1 else None

    while True:
        if all(len(pref_list[i]) == 1 for i in range(N)):
            break
        start = -1
        for i in range(N):
            if len(pref_list[i]) > 1:
                start = i
                break
        if start == -1:
            break

        x = [start]
        y = [get_second(start)]
        seen_pairs = set()
        while True:
            xi, yi = x[-1], y[-1]
            key = (xi, yi)
            if key in seen_pairs:
                cut = x.index(xi)
                x = x[cut:]
                y = y[cut:]
                break
            seen_pairs.add(key)
            nxt_x = yi
            nxt_y = get_second(nxt_x)
            if nxt_y is None:
                nxt_y = pref_list[nxt_x][0] if pref_list[nxt_x] else None
            x.append(nxt_x)
            y.append(nxt_y)
            if len(x) > 2 * N + 5:
                break

        k = len(x)
        for i in range(k):
            xi = x[i]
            yi = y[i]
            y_next = y[(i + 1) % k]
            if yi is None or y_next is None:
                continue
            if yi in pref_list[xi]:
                pos = pref_list[xi].index(yi)
                for w in list(pref_list[xi][pos:]):
                    if w != y_next:
                        remove_pref(xi, w)
            if not pref_list[xi]:
                print(-1)
                return

    out_lines = []
    used = [False] * N
    for i in range(N):
        if not used[i]:
            j = pref_list[i][0]
            used[i] = used[j] = True
            out_lines.append(f"{min(i,j)} {max(i,j)}")
    out_lines.sort(key=lambda s: int(s.split()[0]))
    print('\n'.join(out_lines))


solve()

計算量: フェーズ1・フェーズ2いずれも削除される選好ペア数の合計が$O(N^2)$に抑えられるため全体で$O(N^2)$。入力例1は互いに最上位選好が一致するペア(0,1)(2,3)を持つ自明に安定な例、入力例2は循環拒否により不可能と確定する例として手計算で検証済み。

Step-by-Step 解説

1なぜ常に安定マッチングが存在するとは限らないか
全員が同じ役割を持つルームメイト問題では、拒否の連鎖が自分自身に戻ってくる循環的な三すくみが発生しうる。

2フェーズ1（提案フェーズ）の意味
各人が選好リストの先頭に提案し続け、より良い提案者を得た相手はより下位の候補をリストから削除する。

3フェーズ2（all-or-nothing cycle除去）
回転$(x_0,y_0),(x_1,y_1),\ldots$を見つけて除去する。この除去は「全部か無か」でしか成立しないことが理論的に証明されている。

4停止条件
全員のリストがちょうど1人になれば安定マッチング確定。途中で誰かのリストが空になれば不可能。

5計算量
各回転除去で少なくとも1組の関係が削除されるため全体で$O(N^2)$。

よくあるミス

ミス	原因	正しい書き方
フェーズ1だけで安定マッチングが求まると思い込む	Gale-Shapleyとの類推でフェーズ2を見落とす	全員のリストが1人になるまでフェーズ2を繰り返す
回転除去で全部消してしまう	rotation除去の境界条件を誤解する	$y_i$以降(ただし新パートナー$y_{i+1}$は残す)を削除する
安定マッチングが一意だと期待してしまう	安定結婚問題の男性最適等との混同	実装によって具体的な組は変わりうる点を理解する
N=2の自明ケースでエラーになる	特殊ケースの考慮漏れ	N=2なら常に{0,1}の1組で確定するので特別扱いしてもよい

次のステップ

発展: Irvingのアルゴリズムを$O(N)$空間で効率化し、$N\le2000$程度まで高速化する。
次回予告: Sqrt Tree（静的冪等半群の$O(1)$区間クエリ構造）

自己評価

完全理解おおむね理解要復習

Day 121-Q4 — Stable Roommates Problem（安定ルームメイト問題）

問題