AHC005 解説 - eijirouの競プロ参加記

コンテスト中は10,370,989点で231位、コンテスト後は22,301,086点で2位相当のスコアを出しました。ここではコンテスト後の解法を紹介します。

紹介する解法は一例です。もっといい解法があるかもしれません。

問題概要

$N\times N$ の二次元グリッドが与えられます。各マスは道路か障害物です。指定されたマス $si,sj$ からスタートして、 $si,sj$ に戻るような経路で、全ての道路を一度は視界に入れるようなもののうち、移動距離が短いものを求める問題です。

$49\leq N\leq69$

交差点をうまく選んでTSP（巡回セールスマン問題）に帰着しました。

貪欲法で求めた解をベースにして、交差点の入れ替え、3-opt、Double-Bridgeを繰り返しました。

交差点を"上または下、かつ、左または右に道路が続いているマス"と定義します。道路と道路は交差点で接続しています。

例えば上の図では道路（青）が交差点（赤）で接続していることがわかると思います。

よって、全ての道路を網羅するように交差点を選ぶことで、TSPに帰着することができます。TSPを解くためのアルゴリズムは非常によく研究されており、それらを使用することができます。

全ての交差点間の距離を求めます。私はワーシャルフロイド法を使いましたが、ダイクストラ法を $\vert V\vert$ 回適用しても同様の結果を得られます。いずれにせよ、後から経路復元を行えるようにしておく必要があります。

$si,sj$ も交差点として扱うと実装が楽になります。また、後でSymmetric TSPに帰着するために、交差点のコストを0とみなすとよいと思います。（コスト計算のときは交差点のコストも考えます。）

全ての道路を網羅するためには、各道路が含む交差点のうち、最低1つの交差点を通る必要があります。下の図を例に見てみましょう。

最下段の横の道路は、3,4,5番の交差点のうち1つを通れば十分です。

最も右の縦の道路はどうでしょうか。この道路は5番の交差点しか含まないので、5番は必ず通る必要があります。このように、必ず通る必要がある交差点を"必須交差点"と呼ぶことにします。

必須交差点を1つずつ最適位置に挿入し、その後、無駄にならない交差点を1つずつ最適位置に挿入することで、1つの貪欲解を得ることができます。

貪欲法のやり方は人それぞれだと思うので、参考程度にしていただけたらと思います。

交差点の入れ替えと3-optで山登り法を行い、たまにDouble-BridgeでKickを行いました。3-optやDouble-Bridgeなどがわからない人は下記のサイトを読むといいと思います。

回数の割合としては、Double-Bridge、交差点の入れ替え、3-optの順に 1 : 2,000 : 10,000 にしました。

また、下のグラフのように、スコアが激しく振動し続けるため、最良の解をコピーしておくとよいと思います。

必須交差点以外の交差点をランダムに1つ削除します。削除した交差点を含む道路が縦と横に1本ずつあるので、それぞれの道路について、視界に入らなくなってしまった場合にランダムに1つだけ交差点を追加します。山登り法ですので、スコアが悪化した場合には元に戻すようにします。

ランダムに3ヶ所を選び、最適な順序に入れ替えます。

例えば、ランダムに3ヶ所選んだ結果、A,B,C,Dの4つの範囲に分解されたとします。Xの逆順をX'と表記すると、次の8つのパターンが考えられます。

これらを全て試し、最もよかったものを採用します。

なお、2-optでもかなりの高スコアを出すことができるうえ、2-optのほうが実装が楽なため、時間が短いコンテストでは2-optを使用するのが現実的かもしれません。

ランダムに4ヶ所選んだ結果、A,B,C,D,Eの5つの範囲に分解されたとします。
$A\rightarrow D\rightarrow C\rightarrow B\rightarrow E$
の順に入れ替えます。

このような処理によって、局所解から脱出できる場合があるのだと思います。

atcoder.jp 約500行です。実装には4時間以上の時間がかかりました。

かなり頑張ったつもりなのですが、コンテスト1位のc7c7さんのスコアを上回ることができませんでした。c7c7さん強すぎ！

最後まで読んでいただき、ありがとうございました。