入力の作り方を見る限り、鉱脈はある程度まとまっているので、鉱脈を連結成分として表現して、連結成分とその間のパスを効率よく取っていくとよさそう……だが言うは易しという感じの方針なので具体的にどう実装するかで悩み続けた。
- 鉱脈を構成する点を判別していくつかの連結成分にわける
- 定数$\alpha$を決めて、$p_{ij}-C/\alpha \ge 0$である点$(i, j)$を鉱脈を構成する点と考える。鉱脈を構成する二点で隣接しているものをUnionFindでつなぐ。コスト$C/2$で取れる点がある程度あることを考慮に入れようとして$\alpha = 1.5$くらいで始めたが、最終的には$1.05$になった。後から考えると、これは$1$で問題なかったと思う。
- 連結成分はだいたい100個前後になる。
- 2つの連結成分間の距離を求めておく
- ある連結成分を始点とした場合の、グリッド上の各点への最短距離はダイクストラで求まるので、全連結成分間の距離をあらかじめ求めておく。連結成分は100個程度なので、100回程度ダイクストラすればよい。
- 「グリッドの外周」もひとつの連結成分とみなして最短距離を求めておく。
- ダイクストラをする際、鉱脈を構成する点は通れないことにしておく。こうしないと鉱脈を突っ切って別に鉱脈に行ったほうが得という場合にコストの推定を間違えてしまうし、そもそも負辺を含んでいることになるのでダイクストラできない。通れないことにしたせいで連結成分$A$から$C$への移動が連結成分$B$に阻まれても別に問題ない。（次のパートで、必要なら$A$から$B$、$B$から$C$みたいな経路ができるはずなので。）
- MST+ 焼きなまし
- 使う連結成分が決まっているとき、推定スコアは、連結成分中の$p_{ij} - C/\alpha$の総和から連結成分を頂点とする無向グラフ上のMSTの総コストを引いたものと考えられる。
- 連結成分を使う/使わないで焼きなます。毎回クラスカルした。最初は単純に山登りしたが、焼きなましで多少スコアが上がった。
- 基本の採掘経路を求める
- 使う連結成分が決まったので、「グリッドの外周」を表す連結成分を根としてMST上をDFSしながら採掘していく。隣接する連結成分へ移動するための具体的な経路は、上と同じようにダイクストラして復元すれば得られる。
- 頂点を取る順番もスコアに関係しそうだと思ったけれど、つめられず。
- 使う連結成分が決まったので、「グリッドの外周」を表す連結成分を根としてMST上をDFSしながら採掘していく。隣接する連結成分へ移動するための具体的な経路は、上と同じようにダイクストラして復元すれば得られる。
- 貪欲で仕上げ
- 既に採掘した点の隣接点でスコアが上がるものがあれば取る。
- 既に採掘した点の隣接点とさらにその隣接点の2点を取ってスコアが上がるなら取る。
- 以下、同様の貪欲を深さ4までやる。
267万点だった。
太字の部分に気づいて方針が決まるのに4時間、最初の提出までに6時間半かけてしまった。2～4時間のコンテストだと何もできずに終わってそう。
