THIRD プログラミングコンテスト 2022 （AtCoder Heuristic Contest 017）に参加、優勝しました！
コンテストページ
問題概要
沢山の頂点と辺（道）があってすべての辺を1回ずつ工事したい。
工事中の辺は通れなくなり、それにより頂点間の経路が伸びるとその分だけ不満が溜まる。
不満ができるだけ少ない工事日程を決めてください。
提出コード
最終提出コードをちょっとリファクタしてコメントを付けてみました。
https://atcoder.jp/contests/ahc017/submissions/38692385
以降の解説で説明が難しい箇所にコード行番号を記載します。
解法
山登り法をしました。
基本的な処理の流れは次のようになります。
(1)初期解の計算
辺1つずつ貪欲に工事日を決めていきます。
ある辺について、それぞれの日に工事した場合の評価値を計算し、一番評価の高い日に工事します。評価値は問題自体のスコア（ただし頂点間引きしている）と、工事が特定の日に集中しないようにその日の工事数で減点します。
処理する辺の順番が重要で、あらかじめ2点間の最短経路をたくさん出しておき、その中で長い経路のほうから辺をたどっていくような辺の順序にします。こうすることで、連続した道が同じ日に工事されやすくなります。（提出コード2331行目～）
(2)山登り
ランダムな辺の工事をキャンセルし、別な工事日にしてみてスコアが上がるなら採用、上がらないなら元に戻す、ということを時間いっぱい繰り返します。
ここでは2種類の遷移を行っています。
- 遷移1：1辺を選んで工事日を変える
- 遷移2：1頂点を選んでその周りの辺全部の工事日を変える
遷移1だけだと工事日がだんだん変わらなくなっていくので、遷移2のような大きい変化が必要でした。
以上が基本の流れで割と普通の山登りだと思います。
この問題で重要なことはスコア計算が重いことです。愚直にスコア計算すると初期解の計算ですら制限時間内に終わりません。これをいかに高速化したかを説明していきます。
代表点を使う（頂点を間引く）
問題のスコアはすべての頂点間の距離を計算する必要がありますが、頂点をいくつか間引いても実際のスコアと近い変動をするので間引いてしまいます。
間引き方は以下の2種類使用しました。
- 頂点番号で間引く（5N+1番頂点だけつかうみたいな）
- 頂点間の距離が一定以上になるように間引く（以下の図のピンクの点みたいな感じ）
間引いた状態で山登りをしていると、正確なスコア計算ではないためか実際のスコアが上がらなくなる現象が発生します。時間とともに代表点を増やしていくことで速度とスコア精度のバランスをとりました。最終的には32段階に代表点を増やしています。
山登りの遷移処理においては、まず少ない代表点ですべての日の工事を試してみて、一番良かった日について代表点を増やして再度スコア計算、これがもとのスコアより上がっていたら採用、というような2段階の評価をしています。
スコア計算の差分更新
スコア計算のためには、各日の全頂点間の距離を計算する必要があります。
ある1辺の工事をする時に変化があるのは工事する日の全頂点間距離のみなので、各日の全頂点間距離情報を保持しておくことで、変更のあった日のみ再計算で済みます。
さらに、工事をすることで影響がある箇所は限定的なのでその部分だけ再計算すれば済みます。
以下の図は、ピンクの点を始点としてそれ以外の頂点までの最短経路を青線で示したものです。最短経路はダイクストラで計算していて、各頂点は始点からの距離と1つ前の頂点からどの辺を通ってきたかという情報を持ちます。
以下の図は赤線の辺を工事したときに、再計算が必要になる頂点を緑色にしています。
この図を見てわかる通り、最短経路は木構造のようになっているので、工事した辺以降の部分木の範囲だけ更新すればよいです。
以下の図は、赤線の辺を工事したときの最短経路の変化のGIFです。
実装は、部分木を辿って更新が必要な頂点の距離をINFにしておき、その周りの更新不要な点を優先度付きキューに入れてダイクストラを行えば差分更新できます。
さらに、更新しても頂点間の親子関係が変わることが少ないため、BFSでたどった順番に更新処理を行っていくだけで大体は更新完了します。それで更新しきれない部分だけダイクストラすることで高速になりました。（提出コード1465行目～）（高速化の話は1930行目～1966行目あたり）
工事をキャンセルする場合は、辺の両端にある頂点の距離がその辺を通ることで縮むのであれば更新が必要で、遠いほうの頂点の距離を更新し優先度付きキューに入れてダイクストラを行えば差分更新できます。（提出コードの1507行目～）
スコア計算の打ち切り
初期値計算や山登り遷移の際に、それぞれの日に工事してみて一番良い日を選ぶという貪欲を行います。その際のスコア計算中に、それまでに調べた他の日のベストスコアより悪くなった時点でもうその日に工事する見込みはなくなるため、スコア計算処理を打ち切りるようにしました。
解法については以上です。
コメント
頂点を間引いたところからまともに山登りができるようになって楽しくなった。これを思いつけなかったら何もできずに終わってたかも。高速化でスコア上がるのは楽しい！
連続した道を同じ日に工事するのが良さそうというのは、じっくり山登りさせたことでわかってたけど、最後まで評価値に落とし込むことができなかった。たまたま試した辺の順序変更がうまくいってるみたい。でもあんまり良い方法ではないような？
頂点の間引き方は、等間隔以外にも外周に近いところだけにするとか試してたけど、最終日のごたごたでコードを巻き戻したりして採用できなかった。
最初スコア計算するときに全頂点間距離ならワーシャルフロイドやろーでやったら遅すぎてダメだった。これ過去に別なコンテストで同じことしてる……
おまけ：コンテスト中の動き
スコア計算実装→遅すぎぃ
貪欲してみる→TLE
じっくり時間をかけて山登り→連続した辺を工事するのがいいみたい
ダイクストラ差分計算→貪欲でぎりぎりTLEにならないぐらい
貪欲を頑張るしかないと思っていろいろ評価値考えてみる→日ごとの工事数の偏りを減らすのは良くなった。そのほかにいい評価値は出ず。
頂点を間引いてみた→計算が早くなって山登りができるように。
初期解貪欲の辺の順番をいじってみた→いい感じ
いろいろ高速化。
山登りの評価値いろいろ試したけど良くならず。
間引き量を増やすほどローカルではスコアが上がったが、最終日、提出したらスコアが下がる。なんでえ？
原因調査のためコードをロールバックしたりしてごたごた。
原因はローカルでの処理時間不足（３秒でやってた）により山登りが収束していないため。ジャッジサーバー上では６秒だから収束している→時間が余ってるなら間引き量を減らして精度を上げれるじゃない。
間引き量を徐々に下げたほうがスコア上昇が早そう→良くなった。
ロールバックしてしまった改善点を入れてくが全部は間に合わない。精神的にもつらくて手が動かない。
ちょっとパラメータ調整して終了。
おつかれさまでしたー
