概要
問題文 → ■
公式解説 → なさそう？
自分の提出 → ■ （1335 点）
Heuristic contest タイプの問題で、厳密解が得られなくともそこそこ良い解を出力することが要求されています。
とはいえ、この問題内容・テストケースに対して、厳密解が出ているみたいです。
解法
常に $2$ 人重なって動くことを考えます。いずれかのミッションとなる点を、すべて踏破することを考えます。
本問題のテストケースにおいて、これが実現可能のようです。しかも、単純な貪欲法で達成可能です。次を繰り返します。
- その時点で未踏破であるようなミッション対象点に、最短経路で進む。
コメント
複雑なロジックを書きたくないので 2 人を重ねて単純化。この状態で、2-opt 法くらいまで実装しようかな？と思っていたら、初手の貪欲解で満点が出てしまったｗ
