はじめに
RECRUIT 日本橋ハーフマラソン 2022夏(AHC013)にて、27位を取りました。今回はヒューリスティック的要素よりもアルゴリズム的要素の方が色濃い解き方をしたので、ヒューリスティック未参加のアルゴリズム勢の方が参加するきっかけになればと思い、解法記事を書いてみることにしました。
問題と初期考察
今回の問題はServer Roomという問題で、2〜5種類のコンピュータが各種類100台ずつ$N\times N$サイズの部屋に置かれており、コンピュータの移動・コンピュータ間の接続を行って指定手数内で極力大きな同種コンピュータのクラスタを作る、というものです。（詳細な諸条件は公式サイトの問題文参照）
初期の考察として、スコアの計算方法が各クラスタごとに相互接続数を加算していくというものだったので、実質的にクラスタ毎にクラスタサイズの2乗に比例する得点が得られるため、細かいクラスタが多くできるよりは1個の大きなクラスタを作った方が良いことがわかります。
そこで、最初の取り組みとしては「コンピュータの接続」「コンピュータの移動」を1アクションとして、以下のような感じの評価関数を作って貪欲に実行するということをしてみました。
- 接続によるスコア増分が大きいと高評価
- 移動によりスコアの高い接続候補ができると高評価。ただし移動手数が大きいと減点
これにより最初に成長し始めたクラスタが優先的に成長して100台全部つながって4950点を取る目論見でした。しかし結果は1ケースあたり平均3500点程度にとどまりました。5000点を超えるケースがある一方で、1000点にも満たないケースも出ていました。低い点数の状況を見ると、密部屋で接続したいコンピュータが埋もれてしまっていて接続困難になっていました。
今のままのアプローチだと埋もれているコンピュータを掘り起こすだけの動作にはならないと判断し、どうしたら掘り起こせるかを考えて作っていくことにしました。結果として、上記のアルゴリズムは最終的には全て捨てています。以下、最終的な解法を説明します。
解法
掘り起こし(領域連結)フェーズ
掘り起こしが必要な密部屋は以下のようなものです。中央に1のカタマリを赤枠で囲みましたが、他種類のコンピュータに阻まれてこれ以上接続することができません。
まずは、「自種類のコンピュータおよび空白マス」を同一グループとみなし、同一グループの領域を拡大していくことを目指します。
- 起点となるグループを決める(初期状態で一番大きいサイズのもの。これはDFSで求めた)
- グループ内の領域から多点スタートBFSで同一種類コンピュータの別グループの最短ルートを求める
- 今後2グループ目以降にも同じロジックを使用することを考慮し、BFSで通って良いマスは、クラスタ結合されていないコンピュータまたはケーブルのない空きマスとします
下記の赤枠のグループを起点グループとすると、例えば距離2で青枠のグループが見つかります(このケースでは他にも候補はいくつかありますが)。最短ルートは例えば緑枠で囲った部分です。
連結先が決まったので、次は実際に連結することを目指します。緑枠の部分を「連結パス」と呼ぶことにしましょう。この図の場合は連結パスは1マスですが、一般には複数マスのパスになります。目標はこの連結パスの各マスに空白マスを連れてくることです。
これを実現するには、連結パス内のマスを起点としてBFSで空白マスを探し、空白マスに近い方から順次移動していけば良さそうです。下図の左側では2回の移動で緑枠を空白にすることに成功しています。
しかし何となく危うさがあります。緑枠を空白マスにすることには成功したものの、青枠内に3が入ってしまいました。この場合は青枠の1があるところだけ見れば連結していて問題ありませんが、右の図の場合はどうでしょう？
仮に左の方にある空白マスを見つけてしまった場合(この図では最短距離ではないですが、仮に最短距離だったとします)、6手順番に移動することで緑枠は空白になりましたが、元々赤枠内だった場所に「2」が入ってしまっています(右図の赤文字「2」の部分)。これでは赤枠の連結グループが千切れてしまい良くありません。
何が良くなかったかというと、赤枠内の「交通の要所」に枠外から2が入ってしまったことです。「交通の要所」と言っているのは要はグラフで言う「関節点」であり、low linkというアルゴリズムで求められます。
このlowlinkというアルゴリズムは、アルゴリズムコンテストでは使ったことがないですが、ヒューリスティック十数回で2回目なので、ヒューリスティックではそれなりに頻出アルゴリズムのような気がしています。
さて、元の問題に戻ると、BFSで空白マスを探す際にグループ領域内外を出入りする時は関節点を通らないように判定する必要があります。この他、空白マスを連れて来ようとしている連結パスに隣接するグループ内のマスも別種のコンピュータが入ると連結性を損ねる場合があるので、それも通過禁止とします。
これをできることがなくなるまで繰り返すことで、9割以上の場合は100個全部を連結領域にすることができました。運悪く、関節点に阻まれて連れてくる可能な空白マスが見つからずに連結失敗する場合もありますが、それは諦めました。
また、このあと連結した領域のコンピュータを接続していくわけですが、仮に100個のコンピュータを連結できたとしても、残り手数が60手しかなかったら最大で61台しか接続できないわけなので、連結領域の台数よりも残り手数が少なくなった場合はその時点で処理を打ち切ることにしました。
また、残り手数ギリギリ一杯の状態だとせっかく連結した領域のコンピュータを余らせてしまう可能性が高く、それだったらもう少し連結を減らして接続用の手数を残しておきたくなることが想定されるので、領域を連結するたびにその状態を保存してそこから次のフェーズを進めることも可能にしておきました。
コンピュータ接続フェーズ
コンピュータを連結領域に集めることができたので、実際にケーブルでつないで行くことにします。これについては以下のようなやり方にしました。
- 連結グループ内で、起点となるコンピュータを決める。(今後これに他のコンピュータをつないで行くので、つながったコンピュータ群を起点クラスタと呼ぶことにします)
- 起点クラスタ内のコンピュータと、クラスタ未接続の同種コンピュータを連結する。これには以下の2パターンがある
- 起点クラスタ内のコンピュータを移動し、そこから接続線を伸ばす、伸ばした先に対象コンピュータを連れてきてつなぐ(下図左)
- 起点クラスタ内の接続線の場所に、対象コンピュータを連れてきてつなぐ(下図右)
- 上記をできなくなるまで繰り返す
いずれも、対象コンピュータはクラスタに未参加なので自由に動けることが前提です。起点クラスタ内のコンピュータを動かす際は、既存の接続に影響を与えないため、水平方向・垂直方向のどちらかにしか接続されていないコンピュータのみを対象に、その方向に動かすことだけを考慮します。つまり上図の左で①で移動しているコンピュータは上下方向に動くのはOKですが、左右方向に動くのはNGです。
他の方の解法と比べると起点側の移動・接続・対象側の移動をまとめて考えるという少しややこしいことをしているようですが、これは途中に邪魔コンピュータがあった場合に避けるという処理がうまく組み込めなかったため、このようなやり方で途中に障害物があったとしても連結できるようにしました。
実際の実装としては基本的には多点スタートBFSですが、いわゆる「耳DP」のように①②③がどこまで進んでいるかの状態を持ちながら進めています。
また、BFS時に通れるマスにも以下のように状態によって制約が異なります。
- ①起点移動時
- 空白マス
- 自分が発している方向のケーブルマス(先程の左側の図で移動しているコンピュータは、下方向に自分のケーブルがあるが、下への移動もOK)
- ②接続時
- 空白マス
- 自分と同種で未クラスタのコンピュータマス(接続目標コンピュータ)
- ③対象コンピュータ移動時(BFS探索時は逆方向に探索するので注意)
- 空白マス
- ケーブルマス
- 自分と同種で未クラスタのコンピュータマス(接続目標コンピュータ)
初期の解法はこのような形でしたが、最終的に起点移動時と対象移動時は以下のような玉突き型の移動も許容することにしました。
前者は起点コンピュータが自クラスタ所属のコンピュータを突き抜けて動くイメージで、最終的に移動に落とし込むときにはぶつかったコンピュータを先に動かしてから下のコンピュータを動かすことになります。これによって、上の図のBは横方向の接続があるので縦方向には動けないはずでしたが、縦方向にも線を伸ばしていくことができるようになります。
先の図の下側のパターンは対象コンピュータが起点クラスタコンピュータを突き抜けるパターンで、これも実際には玉突き型で移動します。これも元々移動できなかったところに対象コンピュータを引き込める可能性が出てきます。
これらの実現のためには、先程の移動可能マスに起点クラスタ内のコンピュータマスを加え、さらに移動する際には接続を引き継いで、と結構大変な実装になりました。
この接続処理はできることがなくなるか、手数が尽きるまで行いますが、手数が尽きたけれどもまだ接続可能なコンピュータが残っている場合は、フェーズ1の領域結合で手数を使い過ぎている可能性があるので、領域結合を少し戻して再度フェーズ2を実行するようにしました(実際には何段階まで戻ることになるかわからなかったので、二分探索で手数が尽きなくなるまで戻しつつ、一番つながった結果を返すようにしました)
初期コンピュータ種類のバリエーション
ここまで実装して実行してみると、あまり実行時間を消費していないことに気付きます。1個目のクラスタはかなりの確率で100個つなげられるようになりましたが、その結果がどうなっているかは完全に運任せで2個目がどこまでつなげられるかに大きく響いてきます。
なので、以下のように色々な種類のコンピュータに対して試せるようにして運良く2クラスタ目も大きなものが作れるパターンを探しました。
- 全種類のコンピュータに対してフェーズ1を実行
- それぞれの結果に対してフェーズ2を実行
- 結果の上位(スコアが高い、残り手数が多い)一定個数について、1から続行。これを手数が尽きるまで繰り返す
いわゆるビームサーチです。
さて、これを行っても、まだまだ時間に余裕がありました。時間を活用するため、上記の1回目のフェーズ1の結果を保持し、フェーズ2で接続を最初に開始する起点ノードのランダム性を持たせて、上記の処理を時間が尽きるまで繰り返すことにしました。いわゆる乱拓山登りです。
それ以外の工夫
- クラスタ済みのコンピュータで1方向だけしか接続されていないものについては、その方向に短縮して空きマスを増やせるので、領域結合処理時に必要に応じて短縮するようにした(接続処理時にもやろうとしたらバグって挫折)
- 最後に乱拓山登りをする際に、その時点での最高スコアを叩き出している初期状態は常にやるようにして、更なる改善を目指した(ほぼ誤差レベルの改善)
まとめ
今回、最終的には1ケース平均6570点くらいまで行きましたが、苦労の大半はアルゴリズム的な要素の部分で、最後の方で追加したビームサーチや乱拓山登りをやる前の時点で5800点くらいまでは行っていました。最終順位で言うと40〜50位に相当します。
今回のような問題ではアルゴリズムだけでも結構戦えるものなのだなと思い、記事にしてみました。
何かのご参考になれば幸いです。