18,424,648点で 77位/561人 でした。
最終提出はこちら Submission #24829278 - AtCoder Heuristic Contest 005
入力例１のビジュアライズ結果がこんな感じ。
最終提出の内容
- 交点を列挙
- 交点の内、訪れなくても別の交点でカバーできるものを全削除。削除対象の選び方はテキトー。
- 2で残った交点をノードとして、TSPを焼きなましで解く
時間があればやりたかったこと
削除する交点の選び方、で多点スタート
所感
これまでのAHC短期マラソンより大筋の方針が見えやすい回だったように感じました。交点の一部だけ抑えればいいのだから、あとはそこをどれだけ短く巡るかだけって感じで。 TL眺めてた感じでも、大筋の方針は同様で、使う交点の選び方で差がついていたように感じました*1。
一方で実装は、コンテスト時間４時間がなかなかに厳しく感じました。
- 交点列挙・削除
- 交点間にエッジを張る
- TSP
あたりのまずまず重い実装を、時間内に仕上げなければならないのは中々キツかったように感じます*2。
