THIRDプログラミングコンテスト2022（AtCoder Heuristic Contest 017）参加記

こんにちは。競技プログラミングをしているssaattooと申します。THIRDプログラミングコンテスト2022（AtCoder Heuristic Contest 017）に参加して84位でした。

反省、または誰かの為になることを期待して参加記録を残します。

 

問題概要

頂点数N、辺数Mの重み付き平面グラフで表される道路網が与えられます。D日間で全ての辺を1回工事（=辺の削除）する必要があります。1日に工事できる道路数の上限はKです。ランダムに日付と2頂点を選んだ時の最短距離の増加分の期待値を最小化してください。

解法

工事日を変更するような焼きなましを書きました。

初期解は連結性と工事数上限を守ったランダムなスケジュールを作成。

スコア計算は下図に示される点に最も近い3点を代表始点として、各点でdial's algorithmを用いて最短距離を計算しました。dial's algorithmの計算量は辺の最大コストをWとしたとき、O(E+WV)で表されます。2項目を小さくする為に、事前に辺の重みを3000分の1に圧縮しました。

焼きなましの近傍は以下の4つです。

  • 2道路の工事日程を交換（60%）
  • 1道路の工事日程をランダムに変更（10%）
  • 1道路のスケジュールを受理されるまで変更し続ける（20%）
  • 同じ日に工事する2道路のスケジュールを受理されるまで変更し続ける（10%）

イテレーション回数は数万回でした

日記

自分の考察メモとして書いていたので、読み辛い可能性があります。

コンテスト１日目

問題を読んだ．忙しい．

コンテスト２日目

問題を理解するために簡単な焼きなましを書いた（370位くらい）．スコア計算が重すぎて10回ほどしか回らなかった．全頂点間の距離を計算をせずに間引いた頂点間の計算だけだとダメなのかな．

平面グラフの性質として高速に最短経路を求められるらしい．連結を保つのはマストっぽいので，ダイコネで判定か．
ハイパーグラフを作ってその頂点内と頂点間で連結性を保っていれば，辺を削除してもそんなに距離が変わらないのでは．

コンテスト３日目

連結を保ったものを適当に作る→100位．
連結を保ったものを沢山作り、1番良いものを出力。ダイクストラの開始点を適当に間引いてスコア計算を高速化→これも100位．

同じ日に工事する道路はできるだけ離れていた方がいい気がする．部分破壊山登りを思いついたが駄目だ．

コンテスト４日目

初期解が連結の2辺の工事スケジュールをスワップする嘘スコア計算の焼きなましを提出して50位．イテレーションは5000回だった．イテレーションを10倍にするとさらに２割ほど削れることを確認した．これで15位くらいになるのか？上位が高速化ゲーだったらつらい．

psyhoさんが満点だ．天才的な解法があるのかな．

工事する辺は離れていた方がいいと思っていたけど，工事辺周辺は最短経路になりにくいから逆に工事する辺を集めた方がいいのかも．

コンテスト５日目

意味のない高速化をしてしまう．ダイクストラのpriority_queueをradixheapにしたり配列を使いまわしたりして微改善．イテレーションが10倍になっても7％しか改善しないらしい．方針が間違っているのかもと思って焦る．

やるべきこと：

  • キックの実装．ある点からの距離が一定以下の辺のスケジュールを適当に変更とか？
  • best_scoreがどれだけ更新されているか調べる．更新が少ないなら多点スタート山登りを試す．

コンテスト６日目

部分破壊の後，乱択で作り直すやつを作ってみたけどダメダメだった．乱択ではなく貪欲ならスコアが出るかもしれないけど，ここでいう貪欲ってどんなの？

ダイクストラの遅さが憎い．代わりにBFSでしてみると誤差が大きい．正確でなくともそれなりの短い距離がわかる高速なアルゴリズムがあれば今後のマラソンでも役立ちそう．

コンテスト７日目

スコア計算をdial's algorithm に変更したらイテレーションが1.5倍になった．

高速化したいのに，パフォーマンスプロファイラの使い方がわからない．

コンテスト８日目

近傍を追加，近傍の比率を変化．

コンテスト９日目

もうやることがない．

終わりに

日記を見返していると、「スコア計算は間引いて良い」、「削除する辺は連結の方が良い」など良い性質に早くに気づいていることがわかります。

では何故満足のいく結果が得られなかったのか？それは、焼きなましという問題の本質から目を背けてもそこそこ良い解が得られるアルゴリズムに最初から飛びついていたからだと思います。問題の本質は貪欲です。焼きなましの近傍としても、1辺の工事日を貪欲に変更するものが強かったらしいです。

貪欲は大切です。