Daycare Matching

解説

この問題は，DAアルゴリズム（受入留保アルゴリズム/Gale-Shapleyアルゴリズム）によって解くことができます．

児童側応募DAアルゴリズム

• 全児童・保育園について，仮内定なしの状態とする．
• 仮内定のない児童が1人以上いる場合，以下を繰り返す．
  • 仮内定のない児童を1人選び，$i$ とする．
  • 児童 $i$ がまだ応募していない保育園のうち，最も希望度の高い保育園を $j$ とする．
  • 児童 $i$ は保育園 $j$ に応募する．
  • 保育園 $j$ に仮内定している児童数が $q_j$ 未満である場合
    • 児童 $i$ を保育園 $j$ に仮内定とする．
  • 保育園 $j$ に仮内定している児童数が $q_j$ に等しい場合
    • 保育園 $j$ に仮内定している児童の中で最も優先順序の低い児童を $i'$ とする．
    • 児童 $i$ の優先順序が $i'$ より高い場合，$i'$ の仮内定を取り消し，$i$ を新たに保育所 $j$ へ仮内定とする
    • 児童 $i$ の優先順序が $i'$ より低い場合，$i'$ は $j$ に仮内定したまま， $i$ は仮内定なしのままとする．
• 上記の繰り返しが終了した時点において，各児童 $i$ が仮内定している保育園を $\mu_i$ とする．

証明

• 有限回のステップで終了することの証明
  • 仮内定のない児童がいる場合，その児童がまだ応募してない保育園が存在することを示します（それが示されれば，メインループにおいて児童が1人が1園に応募するので，繰り返しは最大で $N M$ 回で終了します）．背理法のため，仮内定のない児童 $i$ がいて，$i$ がすでに全保育園に応募してしまっているとします．児童 $i$ が各保育園 $j$ に断られた（応募して仮内定しなかったor仮内定を取り消された）とき，$j$ はすでに $q_j$ 人を他に受け入れています．アルゴリズムのステップ内において，$j$ に仮内定している児童数が $q_j$ 人に達した場合，以後仮内定している児童数が減ることはありません．したがって，終了時においてすべての保育園は $q_j$ 人を仮内定させています．しかし，1人の児童が同時に複数の保育園に仮内定することはなく，児童 $i$ は仮内定を得ていないため，$q_1 + \dots q_M = N$ に矛盾します．
• 返されるマッチングが，受入人数制約を満たすことの証明
  • アルゴリズム実行中において，各園 $j$ に仮内定している児童数は常に $q_j$ 以下であるため，終了時においても園 $j$ に入園する児童数は $q_j$ 以下です．また，アルゴリズム終了時には，すべての児童がいずれかの保育園に入園しています．したがって，$q_1 + \dots + q_M = N$ より，すべての園 $j$ について入園児童数は $q_j$ となります．
• すべての児童が不満を持たないことの証明
  • 背理法のため，ある児童 $i$ が不満を持つと仮定し，条件に合う園を $j$ とします．児童 $i$ は園 $j$ より希望度の低い園に入園しているため，アルゴリズムのステップ中どこかで園 $j$ に断られています．この時に代わりに仮内定している他の児童のうち，園 $j$ の優先基準において最も低い児童を $\overline{i}$ とします．児童 $i$ よりは $\overline{i}$ の方が優先順序が高いです．以後のアルゴリズムのステップにおいて，園 $j$ は，$\overline{i}$ よりも優先度の低い児童を受け入れることはありません．したがって，終了時に児童 $i$ よりも優先度の低い児童 $i'$ が園 $j$ に入園していることはなく，矛盾します．

よって，この児童側応募DAアルゴリズムが必ず良いマッチングを返すことが示されました．計算量は，メインループが最大 $NM$ 回であり，ループの内側は各園に仮内定してる児童の優先順序番号を優先度付きキューなどで管理することで1回 $O(\log N)$ で処理できるため，適切な実装のもとで全体で $O(MN\log N)$ で実行でき十分高速です．

本解説では児童側応募DAアルゴリズムを説明しましたが，同様に保育園側応募DAアルゴリズムを考えることもでき，そちらでも良いマッチングを得ることができます．ただし，児童側応募DAアルゴリズムと保育園側応募DAアルゴリズムは，異なるマッチングを返す場合もあります¹²．

サンプルコード：C++はこちら，Pythonはこちら．

Footnotes

1. 児童にとっては児童側応募DAアルゴリズムの方が，保育園にとっては保育園側応募DAアルゴリズムの方が嬉しいマッチングを返すことが知られています．興味のある方は，例えばWriterによるこちらの記事などをご参照ください（リンク先記事では本問のような多対一の設定ではなく，一対一の設定となっています）． ↩

2. 良いマッチングを一つ見つけるアルゴリズムとしては上記のように効率的なアルゴリズムがが知られていますが，良いマッチングをすべて求める問題はNP困難です．$N=M\simeq 80$ 程度ではすべてを求めることができます（Writerによる実装はこちら．こちらも一対一の設定です．）． ↩