1 マッチング

2016 年 データ構造とアルゴリズム 小テスト（第一回） 模範解答
1 マッチング
問 1-1
女性のグループは (Alice, Becky, Carol), (Alice, Becky), (Becky, Carol), (Carol, Alice) の 4 通り．これ
らのグループで場合分けを行い，いずれの場合も選好を操作してもグループの全員がより好ましい男性とペア
になることが不可能であることを示す．
(i) (Alice, Becky, Carol) のとき
Alice と Becky のより好ましい男性は John である．したがってこの二名が同時により好ましい男性と
ペアになることは不可能．
(ii) (Alice, Becky) のとき
(i) と同様にしてグループの全員がより望ましい男性とペアになることは不可能．
(iii) (Becky, Carol) のとき
Becky のより好ましい男性は John，Carol のより好ましい男性は Lee である．ここで選好を操作するこ
とで Carol と Lee がペアになるとする．このとき Alice は John を第 1 希望としているので，Becky が
John にプロポーズしても John とペアになることはない．したがってグループ全員がより好む男性とペ
アになることは不可能．
(iv) (Carol, Alice) のとき
Carol のより好ましい男性は Lee，Alice のより好ましい男性は John である．ここで選好を操作するこ
とで Alice と John がペアになるとする．このとき Becky は第 1 希望の John に断られるので第 2 希望
の Lee にプロポーズを行う．このとき Carol は Lee に断られてしまうので，グループ全員がより好む男
性とペアになることは不可能．
問 1-2
(Alice, Becky, Carol) のグループを考える．選好を操作して Alice, Becky, Carol がそれぞれ Ken, John,
Lee を第一希望にしたとする．このとき Alice-Ken, Becky-John, Carol-Lee のペアからなるマッチングが得
られる．Becky, Carol はより好ましい男性とペアになり，Alice は正直に行動した場合と同じ男性とペアにな
ることが可能．
1
2 川渡りパズル
問2
グラフは図 1 に示す．最短経路の長さは 7．
図1
川渡り
3 アルゴリズム設計
問 3-1
アルゴリズムを以下に示す．
STEP1 N umM erge = 0 とする．
STEP2 A, B を読み取り機械に入れてそれぞれのデータを 2N umM erge 個ごとに区切ってソートしていく．
それぞれ 2N umM erge 個のデータを読み取るまで 1 つずつデータを読み取って比較し，小さいほう
のデータを C に書き込む（C が排出されたら続きを D に書き込む）．一方のテープから 2N umM erge
個読み取ったら他方のテープから 2N umM erge 個になるまでデータを読み取り C に書き込む．次の
2N umM erge 個ずつのデータについても同じ操作を行う．これをテープ A, B が排出されるまで行う．
STEP3 N umM erge = N umM erge + 1 とする．
STEP4 N umM erge = 7 なら操作を終了する．そうでないなら A と C，B と D の役割をそれぞれ入れ替え
て STEP2 に戻る．
2
問 3-2
N umM erge = 7 のとき操作を終了する．つまり STEP2 の操作を 7 回行うことになるが，1 回の操作で各
テープはちょうど 1 回セットされる．したがって A がセットされる回数は 7 回．
4 Θ 記法
ある定数 c1 , c2 , n0 が存在し，任意の n ≥ n0 に対して式 (1) が成立することを示す．
c 1 n2 ≤
(1) 式を n2 で割ると c1 ≤
1
3
−
2
n
1 2
n − 2n ≤ c2 n2
3
≤ c2 となる．c2 ≥
1
3
なら n ≥ 1 に対して右辺の不等式が成立．c1 ≤
なら n ≥ 7 に対して左辺の不等式が成立．したがって c1 =
3
1
21 , c2
(1)
1
21
= 13 , n0 = 7 とすれば式 (1) が成立する．