概要
JOI の output only の問題です。
Heuristic contest タイプの問題で、厳密解が得られなくともそこそこ良い解を出力することが要求されています。また、手元実行でよいため実行時間制限はあまり気にしないでよく、例えば数十分の実行時間を前提とすることもできます。
出力に対する評価方法は、当時参加者による相対評価です。全ケースで、当時参加者ベスト水準である $20$ 点を得られたので、書いておきます。
解法
Steiner 木問題という、NP 困難問題がモチーフですね。
貪欲法
集落が連結になるまで、以下を行います。
- 適当な集落をひとつ選ぶ
- その集落から、各集落までの距離（刈り取る必要のある最小の草の個数）を計算する
- 距離 $1$ 以上かつ最寄りの集落への最短経路上の草を刈り取る
単一始点の最短距離の計算は、01-bfs により $O(HW)$ 時間で行うことができます。また連結性の判定を別に行う必要はなくて、距離の計算をしたうえですべての集落との距離が $0$ になったら終了です。
これを実装するだけでも、かなり $20$ 点に近いスコアが出るようです。「適当な集落をひとつ選ぶ」にランダム性があるため、適当な試行回数だけ反復することで、当たり待ちもできます。
山登り法
解を局所的に作り直す方法を考えます。次のようにしました。
- 適当な長方形領域を選ぶ
- 領域内の、刈り取り済であるような草を、生やし直す
- 集落と連結でないマスについて刈り取っている草があれば、生やし直す
- その状態から上述の貪欲法で、解を作り直す
「長方形領域」の大きさの調整は、良く分からなかったのでとりあえず、random(5, H), random(5, W) とかしています。近傍は大きくとる分、初期解はひとつで進めました。
結果
計算量が割と大きい感じになってしまいましたが、$20$ 点にはかなりすぐ届くみたいです。$10$ 分ほど回すと、巨大盤面ではそこからまだまだスコアが改善していきました。
もうひとアイデア
「最短経路」にもランダム性を持たせてみます。最短経路の探索アルゴリズム内を、次のようにしました。
- 確率 1/2 で、次のどちらかを使う。
- 横方向優先の探索：dxdy = ((1,0), (-1,0), (0,1), (0,-1))
- 縦方向優先の探索：dxdy = ((0,1), (0,-1), (1,0), (-1,0))
ある領域を、縦方向優先から横方向優先に作り直すような遷移が生まれ（近傍の多様性？）、山登りの成功確率が上がったみたいです。一部の問題では短時間で上述のスコアを上回りました。
