RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013） に参加しました。時間をかけてどっぷり参加でき、システス前 355,714 点 14 位、システス 14,231,546 点 14 位の結果を出すことができました。本解法には以下の特徴があると思っています。
- コンピュータの移動方法 + コンピュータの接続方法で焼きなましを行う。
- BFSやDFSといった探索を行わず、貪欲も行わないので実装は軽め。
問題を見たときの第一印象
- コンピュータの移動はスコアに直接寄与しないので、移動回数を最小限にして接続回数を稼いだほうが良さそう。
- とりあえず、同じ種類のコンピュータ同士の接続のみを考えたい。
- 接続の交差を許さないのがめんどくさそう。平面グラフに関するアルゴリズム何も知らない...。
- 移動するパート + 接続するパートの
つを同時に考えるのが難しそう。
方針決め
- 連結成分の大きさの
つの大きなクラスタを作ったほうがお得。
点 (
ケースだと
点) になるが、上位陣のスコアはそれよりも全然高い。
よって、 種類のコンピュータでクラスタを作成しつつ、
種類目のコンピュータでのクラスタ作成も視野にいれることで、
点あわよくば
点を取れうることを目指す。
どうやって方針を実現する？
主に以下の 点で悩んだ。
- Q1. クラスタを作る
- Q2. コンピュータの移動方法をどうやって決める？
- Q3. コンピュータの接続方法をどうやって決める？
- Q4. 移動回数と接続回数のバランスはどうやって決める？
それぞれに対して、以下の通りにした。
A1.
種類の結果のうち最もスコアが高いものを使用する。
A2. 「どのコンピュータ」が「どの向きに1マス移動するか」の順番を決めておく。移動にてコンピュータ同士が衝突してしまった場合は移動を行わない。
A3. コンピュータから右もしくは下へとケーブルを伸ばす順番を決める。盤面外に到達する（赤色点線）、他の種類のコンピュータに到達する（青色点線）、既存の接続と交差する（緑色点線）場合は接続しない。それ以外の場合は接続する。
ケーブルを伸ばす順番を変更することで、以下の つの状態間を遷移できる。
- A4.
回程度の接続回数を確保できるように、移動回数を固定しておく。例えば
のときに移動回数は常に
回とした。もし移動にてコンピュータ同士が衝突した場合、衝突した回数分を接続回数へと追加した。
A1 で作成した初期解を元に、A2, A3の状態で焼きなましを行えそうだったので、焼きなましを行った。
焼きなましで保持する状態
- 移動方法 (対象コンピュータ, 移動方向) の手順。配列で表現。
- 接続方法 (対象コンピュータ, ケーブルを伸ばす方向) の手順。配列で表現。
焼きなましの近傍
- 移動手順の
回行う。
- 接続手順の
ただし、コンピュータの密度を としたとき
とする。コンピュータが密であるほど
は大きくなる。狙いとしては、コンピュータが密であるほど、コンピュータ同士がぶつかり移動が無効なるケースや、そもそも接続同士が交差しないケースが発生しやすいので、たくさん更新することで状態が変わるようにした。
スコア計算、評価関数について
- 移動手順をシミュレートした後に、接続手順をシミュレートする。
- シミュレート後の盤面の状態を元にスコアを計算する。
- 接続の管理には Union Find を使用する。AtCoder Library で言うところの
group()を使えばそれぞれの連結成分の大きさが分かり、スコア計算ができる。 - 正確なスコア計算とは別に以下の評価関数を用意した。
- 評価1.
乗オーダーで評価する（大きなクラスタを過大評価する）。
- 評価2.
- 評価1.
- 焼きなまし過程では時間経過ごとに、評価1を利用、評価2を利用、真のスコアを利用するようにした。
高速化について
- vectorや配列を使いまわし、生成をできる限り行わないようにした。
- UnionFind の経路圧縮を行わないようにした。
- コンピュータの位置や接続状態などを map や unordered_map で持つのではなくサイズ
の配列で管理した。
- コンパイラを GCC ではなく Clang を使用した。
