AtCoder Heuristic Contest 005に参加しました。
MM128の疲れが取れていないんですが…。
問題はPatrolling。低コストな巡回ルートを作る問題でした。
結果は12,224,847点で、提出561人中、192位でした。
考察
まず事前のメタ読みとして、高校生のマラソン大会と同じ問題なので、高校生程度の知識で解けるある程度素直な問題が出ると予想。
全ての道を視界に入れるには、全ての交差点を通れば良さそう。あとは全ての交差点を通る最短ルートを構築すればよさげ。全ての点を通る最短ルート…あ、これTSP(巡回セールスマン問題)か。そうなると2-optのライブラリは事前に作ってあったので、あとは問題固有の場所を実装すれば良いっぽい。
通るべき交差点は上手く組み合わせれば削減出来そうだけど、まずは最低限のコードで取れる点を取るところからやろう。
グラフがちょっと複雑かな。移動コストがちょっと特殊で有向グラフになりそうだけど、各交差点を1回ずつ通るという前提を付けることで交差点間の経路のみのコストを取って、無向グラフに置き換えることができた。
実装
まずは交差点の列挙、交差点間の移動コストの計算、交差点→交差点の移動ルートの計算と出力、といったところをやる。多対多を求めるせいか、頭がバグって冗長な計算をしていた…。（普通にグリッドベースのダイクストラで良かったんだけど、前処理してから交差点間でワーシャルフロイドしてた）で、まあまあ時間ロス。(90/240分)
次に2-optライブラリを貼る。…んだけど、座標間のマンハッタン距離を見る形のライブラリになっていたので、計算済みのコストを与える形に改造。こういうのは何度か実戦投入してみないとどういう形がいいのか分からないことも多い。動かしてみると初期解から全然変わらない…であれこれデバッグしてみると、ライブラリ自体は問題なくて処理結果を見ないコードになっているだけだった。で、滅茶苦茶時間ロス。(200/240分)
ここでもうほとんど時間が無くて、雑に交差点を削減するところを書いたら交差点間のコストを取得するところと干渉して動かなくて、あと5分あれば動くのに～というところで終了。
感想
writer解は見つからなかったけど、やはり使用する交差点の選定と、使用する交差点でのTSPが肝の問題だったっぽい。あとは2-optじゃなくて2点swapが強かったとか？ただ交差点の選定の方がより重要だったらしい。
重要パートまで行けなかったので、はい。実装も凡打でもとりあえず打てたのは良かったですかね…。いや、これは良くない。ライブラリ無ければ破滅してましたよね？*1
4時間コンともなると1箇所詰まるだけで破滅するので大変だと思いました（小学生）
ワーシャルフロイドを初めて書いて理解したのと、2-optライブラリを初めて実戦投入出来たのは良かったです。
*1:ライブラリのせいで破滅してた気もする
