AHC017 上位解法から学べることまとめ
上位解法から学んだことのまとめ
1) コンテスト序盤で最高のパターンと最悪のパターンを知る。
AHCに取り組む時に、まずその課題に対して「目指すべき最良の結果」と「提出してはならない最悪の結果」を知ることは良いことのようだ。考えてみれば当たり前だが。
参考：https://hackmd.io/@qLethon/r1osxMBhs#%E6%9C%80%E6%82%AA%E3%81%AE%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3
まずは制限時間を気にせず、ローカル環境で最高のパターンと最悪のパターンを発見する。
問題を最初に見た時は、工事する辺を位置的にバラけさせるのが良さそうと思ったけど、実際には最短経路木のようなパスを作った方が良いらしい。
こういった直感では想像もつかない事実に気づくことができれば、長期コンテスト中の取り組み方針もある程度決めることができて、闇雲にアイデアを実装するよりも遥かに有意義な開発が行えそうだ。
2) 完璧な解を求めない。中途半端でも良い。
全ての頂点の組み合わせN * (N - 1)の最短経路を求めようとすると、とても間に合わない。
これでは正確な評価関数を実装しても意味が無い。
しかし、これはヒューリスティックコンテストなのだから、評価関数だって確実に正確なものではなくとも、それに近似するものであれば良い。
3)問題文に書いてある注意点は必ず考慮する。
孤立する頂点が出ないようにする。辿り着けない頂点がある時コストが109となってしまう。これが一番大事だったかもしれない。
ダイクストラでコストを計算する評価関数を作っていたが、そもそも孤立する頂点が出るような変更や、初期解の時点で孤立する頂点があるような解からスタートしてしまうと、全くと言っていいほどスコアが改善しなかった。
これは上位勢の「ダイクストラでコスト計算して評価点を出し焼きなまし（or 山登り）」解法を使っている人たちのコードから孤立する頂点が出ないようにする処理だけをコメントアウトして実行することで同様の結果を確認できた。
参考：Submission #38566380 - THIRD PROGRAMMING CONTEST 2022（AtCoder Heuristic Contest 017）
4) 試行回数を稼げるのであれば焼きなまし法、そうでなければとりあえず山登り法。
「前述の孤立する頂点が出ないようにする」と「各日、最短経路木っぽく工事する」がまず大事な前半の処理で、後半の処理として、工事する辺の日を変更して不満度が下がるなら変更という処理を繰り返していけば改善する。Pythonだと計算時間が足らなくて後半の焼きなまし（or 山登り）のパートにあまり時間を使えない。時間に余裕があって試行回数を稼げるのであれば焼きなましをしても良いっぽい。
感想
普段のアルゴリズムのコンテストもそうだが、長期ヒューリスティックコンテストは特に考察をじっくりやってまともな方針を立ててから動き出さなくてはならないと思った。
(1)と(3)は特に大事だと思う。無駄な時間を浪費せずに済む。
