https://atcoder.jp/contests/ahc005
とりあえず問題を読んだ。 巡回セールスマン問題系かな。 始点が固定なのは助かるような助からないような。
初手でやること:
- 自明に使わなくていいマスを消去する作業
- とりあえず始点からの Dijkstra
- このマスにこの向きから来たら次はこの向きにいくしかないみたいなやつの列挙
- グリッドグラフでなくて一般の平面グラフを再構築した方がいい気がする
- 「この場所を目視する必要がある」でなくて「これらのいずれかの場所を踏む必要がある」に持ちなおす
- 入力例を眺める
- 入力の生成方法とスコアの計算方法を確認する
スコアは v = r の場合だけ考えてよい。 とにかく所要時間 t を減らせばよい。
道は偶数行の偶数列に線分を引くことを繰り返して生成される。
前処理を書いた後の方針をどうしよう。
とりあえず行き止まりの削除はできた。 交差点を集めてくれば必要最小限の小さな平面グラフに落とせそう。
やっと初期解が書けた。しんどかった。まだ何もまともな探索を入れられてなくてやばい
2-opt みたいにしてるがバグりまくり。ぜんぜんうまくいってない
ちょっとバグ取れた。でもまだ残ってる。やばい。どうするのこれ
バグ取れた。うれしい。間に合った。天才
点数がぜんぜん足りていません。終わった……
焼きなましのコードを消したら伸びたが