AHC017のざっくりとした解法解説

解法の概要

各辺間の相性のようなものを評価値とした貪欲による初期解生成と焼きなましを行った。

解法の詳細

評価関数の設計

工事を一切しなかった際の最短経路として使われる辺と、ある1辺のみを工事した際に最短経路として使われるようになった辺の差を考えた。

辺iと辺j間の評価値f(i, j)を

f(i, j) = (工事無しの際、辺iの両端から全点への最短経路で辺jを通った回数) - (辺iのみ工事している際、辺iの両端から全点への最短経路で辺jを通った回数)

とし、評価値が高いと相性が悪い、評価値が低いと相性が良いとした。

初期解の作成

最初にその日に工事する辺間で評価値が全て0以下になるものをD日分割り当てた。 最初の方法である程度割り当てた後、残った辺それぞれに対し、ある日にすでに割り当てられた辺全てと候補の辺との間の評価値の和を計算し、それが最も小さい日へ貪欲に割り当てた。

焼きなまし

焼きなましでは

1. 辺のスワップ
2. 辺の移動

の2種類の遷移を行った。

また、遷移前と後で変更予定の辺の端点間が行き来できるかを調べ、遷移すると行き来できないようであれば遷移しない、 遷移前段階で行き来できていなら評価値関係なく遷移するという処理も加え、非連結な日ができにくいようにした。

(最終提出では焼きなましで提出したが、どうやら山登りのほうがスコアがよかったみたいです…)

おまけ

コンテストではRustで提出しましたが、一応Python解も載せておきます。一部Rustの提出と違うところがありますが、そこまで大きな違いはないと思います。 ジャッジでは時間が厳しいですが、手元のPyPyで実行時間を5倍ほど伸ばしたところそれっぽい解が出ました。 REになっていますが、だいたいのケースで動くと思います。

PyPyでの提出