第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023）やったこと
問題
https://atcoder.jp/contests/ahc023/tasks/asprocon10_a
やったこと
一般グリッドグラフで考えると大変なので、全域木を取り、葉から根に向けて値が小さくなるようにしていく。
こうすることで、取り出せることは保証される。
全域木の取り方
最初の全域木は、出入口を root とする BFS 木をとり、下で述べる配置の方法に従い一度シミュレーションする。
そうすると、ほとんど置かれない場所が存在する。これを通路とよぶ。(ケースによって値を変えているが、下の値が大体 50 以下の場所のイメージ)
この通路を根とした多点 BFS 木をとる。これを初期解とし、あとは適当に使う辺を swap しながら、全域木を構築し、シミュレーションして山登りする。
配置
が小さい最初の 400 個は、葉から順に
が大きいほうからおく。それ以降は、当月が
月のもののうち、
月が大きいものからおいていく。
月内で置く場所や置くものを適当に swap し、シミュレーションして山登り
結果
pretest: 58 位(?)
