AtCoder Heuristic Contest 005(AHC005) -Patrolling- 参加記
問題
結果
21,784,788点で9位。初赤パフォ。嬉しい。
解法
前処理
- 直線の通路を全て列挙する。各通路にどの交差点が含まれるか記録する。
- 各交差点と開始点を始点にしてダイクストラする。
焼きなまし
全通路を1度ずつ触れば、全マスを視界に入れたことになるので、通路を回る順番を焼きなます。順番を決めた時のスコアは、greedyに一番近い交差点へ移動した際の経路の距離とする。近傍は2-optのみ。通路の総数は100前後だし、差分計算しても速くならなそうだったので、スコア計算は特に工夫せず、毎回開始点から計算し直した。遷移回数は200万回程度。
経路決め
焼きなましのスコア計算はgreedyな経路にしたが、最後に、通路を回る順番は固定して、最短経路を計算して出力する。ただ、greedyと比べて0.2%位しかスコア改善しない。まあやらないよりはマシ。
時系列
問題読み&考察 (0:00〜0:30)
問題読んだ感じTSPだけど、どのマスを視界に入れたかを管理するの大変では、と思う。交差点でTSPするのは諦めて、上手いこと全マス視界に入れる方法を考えていると、交差点じゃなくて通路を順番に回るように考えれば良さそうということに気づく。単純に2-optすれば良さそうだし、この方針でいくことに決定する。自分の実装力だとこの方針で実装した後、方針変更する時間は残されていないだろうから、本当に良さそうかは結構考えた。
実装 (0:30〜2:00)
頑張って実装する。
提出1 (2:02) スコア 18,467,888
とりあえず山登りで提出。
提出2 (2:20) スコア 20,469,123
雑に焼きなます。瞬間3位になってビビる。
提出3 (2:52) スコア 20,516,313
最後の経路をちゃんと最短経路にする。あんまり改善しないだろうなとは思いつつも、他にやることも思いつかなかったので実装する。
焼きなましスケジュール&パラメータ調整 (〜4:00) スコア 21,784,788
残り1時間位で、アルゴリズムの改良は思いつかなかったので、ひたすらパラメータとスケジュール調整した。最終的には線形で冷やすのが良かった。
反省点
他の上位勢の解法見ると自分より明らかに深く考察している。今回はたまたまシンプルで強い解法を引けただけで、もっと考察伸ばせるようにしたい。
