はじめに

みなさんこんにちは！現在、内定者インターン中の内藤です。
本日は、先日レバレジーズで行われ予想以上に（失礼）大盛況だった「第一回テックフェスのテックバトル」についてお話しします。

この記事を通して、レバレジーズのエンジニア組織の風通しの良さを少しでも感じてもらえると嬉しいです！

そもそもテックフェスとは？

テックフェスとは何なのか簡単にお話しします。
テックフェスは、レバレジーズのエンジニア組織メンバー全員を対象としたテクノロジーの祭典です。弊社エンジニアの技術力を向上させ、よりよいサービスを世の中に提供できるようにするために企画されました。

今回、テックフェスは記念すべき第一回を迎えました🎊
その記念すべき第一回目は、以下のようなタイムスケジュールで行われました。

テックバトル

テックバトルでは、3人1組チームに分かれ、コーディングの「正確さ」と「速さ」を競うコーディングバトルを行いました。コーディングバトルってやっぱりエンジニアならではで楽しいですよね！

では、早速今回のテックバトルで扱った問題を見ていきたいと思います！

問題概要

今回のテックバトルの問題は、以下の3つの実装を各人が担当し3人で協力して一つのものを作るという内容でした。

※ 今回、企業数と候補者数は同じ（ $n=1000$ ）であるとします
※ この安定マッチングとは、企業と候補者、共に現在組んでいるペアよりも希望順位が高いペア（以降では、ブロッキングペアと呼びます）が存在しない状態を指します

テックバトルの問題に挑戦！

上記でも少し触れた通り、この問題の肝はCさんであり、Cさんが如何にこのプログラムを実装するかにチームの命運がかかってます笑

今回、企業(候補者)数 $n$ に対して、全組み合わせを力任せで調べるBrute-Forceアルゴリズムを用いると計算量は $n !$ になります。 $n$ が小さい値の時はまだマシですが、 $n=1000$ ともなると計算量があまりに膨大になってしまうので、このような時はアルゴリズムの知識が重要になりますね！

今回の問題で活躍するのは、Gale-Shapleyアルゴリズムというもので、このアルゴリズムを用いると計算量は $O(n^2)$ で済ませる事が出来ます。恐ろしいほど強力ですね！😲

Gale-Shapleyアルゴリズム

今回の問題で重要なのは、如何にしてブロッキングペアの存在しない安定マッチングを実現するかという点です。
Gale-Shapleyアルゴリズムは以下のようにして、安定マッチングを実現します。

では、アルゴリズムを確認したところで、実際にコードを書いてみましょう！

実際に書いてみた！

今回は、Aさん, Bさんの実装は置いておいて（ごめんなさい笑）、CさんのGale-Shapleyアルゴリズムに該当する部分のプログラムをpythonで書いてみました。
（pythonにしたのは、自分が日頃業務とは別に使うことが多いからです）

今回使う変数は以下の7つです。

# 初期に与えられている変数
n : 企業(候補者)数  ... 今回、企業数と候補者数は同じ数とします
corps : 企業のリスト ... ['A', 'B', 'C', 'D', 'E'] のような形
candidates : 候補者のリスト ... ['a', 'b', 'c', 'd', 'e'] のような形
corp_desire_order : 企業の希望順位リスト ... {'A': ['b', 'e', 'd', 'c', 'a'], 'B': ['c', 'a', 'e', 'd', 'b'],}...のような形
candidate_desire_order : 候補者の希望順位リスト ... {'a': ['B', 'D', 'A', 'E', 'C'], 'b': ['C', 'A', 'D', 'E', 'B'], ...}のような形
 
# 最終的に出力する変数
corp_to_candidate : 企業と候補者のマッチングリスト ... {'a': 'D', 'b': 'C', ...}のような形
candidate_to_corp : 候補者と企業のマッチングリスト ... {'D': 'a', 'C': 'b', ...}のような形

この7つの変数を基に、プログラムを書くと以下のようになります。

def gale_shapley(corps, candidates, corp_desire_order, candidate_desire_order, corp_to_candidate, candidate_to_corp):
   # 1. 候補者とマッチングしてない企業1社が、希望順位が一番高い候補者にマッチングを申し込む
   for corp in corps:
       if corp not in corp_to_candidate: free_corp = corp
   candidate = corp_desire_order[free_corp][0]
 
   # 2-B. 1で選ばれた候補者がマッチング中であった場合、現在マッチング中の企業とマッチングを申し込まれた企業の希望順位を比較する
   if candidate in candidate_to_corp:
       another_corp = candidate_to_corp[candidate]
      
       # 2-B-b. もし、マッチングを申し込まれた企業の方が希望順位が上なら、候補者は現在のマッチングを解消し、マッチングを申し込まれた企業とマッチングをする
       if candidate_desire_order[candidate].index(free_corp) < candidate_desire_order[candidate].index(another_corp):
           del corp_to_candidate[another_corp]
           corp_to_candidate[free_corp] = candidate
           candidate_to_corp[candidate] = free_corp
           corp_desire_order[another_corp].pop(0)
 
       # 2-B-a. もし、現在マッチング中の企業の方が希望順位が上なら、候補者はマッチングを申し込まれた企業を断る
       else:
           corp_desire_order[free_corp].pop(0)
  
   # 2-A. 1で選ばれた候補者がマッチングしていなかった場合、候補者は企業からの申し込みを承諾する
   else:
       corp_to_candidate[free_corp] = candidate
       candidate_to_corp[candidate] = free_corp

# 3. 1~2を全ての企業と候補者がマッチングするまで繰り返す
while len(corp_to_candidate) < n:
   gale_shapley(corps, candidates, corp_desire_order, candidate_desire_order, corp_to_candidate, candidate_to_corp)