THIRD プログラミングコンテスト (AHC 017): 20位以内のスコアを出すシンプルな解法

THIRD プログラミングコンテスト (AtCoder Heuristic Contest 017) に参加し、7位を取ることができました。その過程で、本番20位以内相当のスコアを出すことができるシンプルなプログラムを作ることができたので、その解法について解説します。7位解法はそれを元にしたものではあるのですが、かなり煩雑になってしまったので、最後に方針を簡単に述べるにとどめておきます。

20位以内相当解法の方針は「辺の割り当てをひとつずつ変更する焼きなまし」です。ただし、定義通りにスコア計算をすると、遅すぎて試行回数がまったく稼げないので、以下の二点がポイントになります。

• 代表点をいくつか選んで、代表点から他の頂点への最短距離の平均値によって、全点対間最短距離の平均値を近似する。

• 辺の割り当てを変更したとき、変更前の最短路木の情報を利用することで効率良く逐次更新ができるように、Dijkstra のアルゴリズムを変形する。

代表点による近似

まず、ベースラインとして、辺を割り当てる日を変更した場合に、それぞれの日で全点対間最短路を求めるような解法を実装します。

まず、全点対間最短路を求めるには、各頂点を始点とする Dijkstra のアルゴリズムを実行するのが良いことに留意します。全点対間最短路を求めるアルゴリズムとしては Floyd-Warshall のアルゴリズムが有名ですが、これは計算量が$${O(|V|^3)}$$となります。一方、各頂点を始点とする Dijkstra のアルゴリズムを実行する場合の計算量は$${O((|V|^2 + |V| |E|) \log |V|)}$$となります。この問題ではグラフが疎である ($${|V| \leq 1000, |E| \leq 3000}$$) ので、各頂点を始点とする Dijkstra のアルゴリズムを実行する方が圧倒的に高速です。

では、以下のような山登り法を実装してみます。

• 各辺を適当な日に割り当てることで初期解を作る

  • 例えば、辺$${i}$$を日$${i \ \% \ D}$$に割り当てる

• ランダムな辺を選んで、その辺を現在割り当てられている日と別の日に割り当てることを試行する。影響を受ける二つの日で全点対間最短距離の平均値を求め、元の値以下になるならば、割り当てを更新し、元の値より大きいならば、新しい割り当てを棄却する。これを制限時間いっぱい繰り返す。

この方法を実装して、AtCoder のコードテストで seed 0 のケースを試したところ、割り当て変更の試行を40回しか試すことができませんでした。辺は2277個あるのでまったく足りません。この解法を提出したところ、50ケースのスコアは43Bとなり、1位解法の405Mとは比較にならない値になってしまいました。これは、グラフが非連結になるケースがあるためです。これでは話になりません。

そこで、4個の頂点を代表点として選んで、全点対間最短距離の平均値の代替として、「各代表点から他の頂点への最短距離の平均値」の平均値を計算することにします。この方法を実装して、AtCoder のコードテストで seed 0 のケースを試したところ、割り当て変更の試行を8000回試すことができました。まだ十分な回数とは言えませんが、50ケースのスコアは596Mとなり、bowwowforeach さんの1位解法に対する相対スコアは68%となりました。これは本番では100位前後に相当するスコアで、十分に良い解法と言えます。

代表点の選び方ですが、$${[0,1000] \times [0,1000]}$$の領域を$${2 \times 2}$$の格子に分割して、各格子の中心に最も近い頂点を選びました。より良い頂点の選び方はあると思います。

効率の良い最短路の逐次更新

二番目のトピックである、効率の良い最短路の逐次更新方法に移ります。ここでは、辺を一つだけグラフに追加あるいは削除した場合に、影響を受ける部分だけを再計算することで、Dijkstra のアルゴリズムを一から実行するよりも圧倒的な高速化をすることができます。以下の方法を実装して　AtCoder のコードテストで seed 0 のケースを試したところ、割り当て変更の試行回数を150倍の120万回に増やすことができました。

辺を追加する場合

追加の方が削除よりも簡単なので、まず追加の場合を考えます。

追加する辺を$${e=(v_0, v_1)}$$、その重みを$${w}$$とし、また始点から各頂点$${v}$$への最短距離が$${d[v]}$$に格納されているとします。

• $${d[v_0] + w < d[v_1]}$$のとき: $${d[v_1] := d[v_0] + w}$$と更新し、頂点$${v_1}$$をプライオリティーキューに入れて、プライオリティーキューが空になるまで Dijkstra のアルゴリズムと同様の処理を行う。

• $${d[v_1] + w < d[v_0]}$$のとき: $${d[v_1] := d[v_0] + w}$$と更新し、頂点$${v_0}$$をプライオリティーキューに入れて、同様の処理を行う。

• どちらでもない場合、最短路は変化しない。

注意点として、割り当ての更新が棄却された場合に状態を巻き戻す必要があるので、上記のアルゴリズムで最短路を更新した際には巻き戻しのためのデータを保存する必要があります。

辺を削除する場合

辺を削除する場合は、削除前の最短路木に注目することが必要になります。

• 削除する辺が最短路木に含まれていない場合、最短路は変化しない。

• 削除する辺が最短路木に含まれている場合、その辺の子孫となる頂点への最短路の情報を無効化する。そして、無効化された頂点のうち、無効化されていない頂点に隣接している頂点をプライオリティーキューに入れて、プライオリティーキューが空になるまで Dijkstra のアルゴリズムと同様の処理を行う。

上図では、黒い頂点が始点、青い頂点が最短路確定済みの頂点となっています。辺を削除した場合は、子孫の頂点を最短路未確定とした上で、黄色い頂点をプライオリティーキューに入れて、Dijkstra のアルゴリズムと同様の処理によって未確定の頂点への最短路を計算します。

代表点を増やす・山登りから焼きなましへの変更

以上の工夫によって大幅に高速化することができたので、代表点を増やしましょう。私の場合は21点まで増やしました（$${5 \times 5}$$の格子の中心のうち円に含まれるものに対して、最も近い頂点を選びました）。これだけ代表点を増やしても20万回以上の試行回数を確保することができました。また、十分な試行回数を確保することができたので、山登りを焼きなましに変更しました。ここまでを実装することで、50ケースのスコアは449Mとなり、1位解法に対する相対スコアは90%となりました。これは本番で20位以内に相当するスコアです。提出コード (650行)。

7位解法について

本番では、「スコア推定精度は低いが高速な別の焼きなまし」による解を初期解として、上述の焼きなましを行うことで、7位を取ることができました。

「精度は低いが高速な別の焼きなまし」として、「二辺の相性」に注目することで、二辺の相性のみから計算できるスコアを最適化する焼きなましを行いました。辺$${A}$$のみを工事する場合のコストを$${X}$$、辺$${B}$$のみを工事する場合のコストを$${Y}$$、二辺を同時に工事する場合のコストを$${Z}$$としたとき、$${Z - (X + Y)}$$を「二辺の相性の悪さ」（負になる場合もある）として定義しました。そして、同じ日に工事する辺のすべてのペアの相性の悪さの総和を最小にするような問題を焼きなましで解きました。すべての二辺の相性を計算するのは上述の逐次更新を使ってもまだ時間が足りないので、互いに干渉しない二辺については計算を省略する工夫が必要でした。