AtCoder Heuristic Contest 005 参加記

AtCoder Heuristic Contest 005に参加し、16.3Mで143位でした。

atcoder.jp

解法

本番では一番近くのまだ到達していない「通り」に進むだけの貪欲しかできなかったため上記の点数でした。
やりたかった解法は以下のとおり。

問題の解釈

問題を良く読むと、縦か横のひと繋がりの道を「通り」としたとき、
「全ての道路を見渡す」は「全ての通りに最低１回は到達する」と同値であることがわかる。
また、それぞれの通りには必ず交差点で到達するので、経路を考えるときには交差点のみを考えれば良い。

つまり、「どの順番で通りを巡回するか、それぞれの通りにおいてどの交差点を経由するか」を定める問題と解釈しなおすことができる。

解法

前者の「どの順番で通りを巡回するか」は巡回セールスマン問題の2-optのような解法で焼きなましていけば良さそう。
後者の「それぞれの通りにおいてどの交差点を経由するか」は真面目にはさまざまな解法がありそうだが、シンプルにはスタートから 順に交差点を定めていき、前の交差点から最も近い交差点を選んでいけば良い。

交差点間の距離

上記の解法で経路の長さを求めるには各交差点間の距離が必要になる。
テストデータの交差点数は最大で1000個くらいあるように思えた（もうちょっと少ないかもしれない）
ここで、ワーシャルフロイド法を使うとO（交差点数の3乗）のため交差点数=1000だと間に合わない。
しかし、各点を始点とするダイクストラ法を行えば良い。ダイクストラ1回の計算量は O（(辺の数+交差点数) log 交差点数）であり、辺の数＜交差点数 x 4 なので十分間に合う。
本番ではここが思いつかず、どうにもそこから先に進めなかった。

スコア

前処理で交差点間の距離の計算を行っておけば、2-optで差分計算をせずに素朴に計算しても3秒で150万回くらいは試行できた。温度を適当に調整すると20.8M, optunaでもうちょっと調整すると21.5Mで、15-20位前後のスコアになった。 https://atcoder.jp/contests/ahc005/submissions/24899313