olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

Online MST(THIRD プログラミングコンテスト 2021 (AtCoder Heuristic Contest 007))

AtCoder

$8$位だったのでやったことを書く。

問題

$N=400$ 頂点 $M=1995$ 辺のグラフがある。辺のコストははじめ不明である。 $ M $ 本の辺について重さの情報が与えられるので、与えられるたびにその辺をグラフに残すかどうかを選択する。与えられる辺の重さは頂点間のユークリッド距離を四捨五入した値の $1$ 倍以上 $3$ 倍以下である。 最終的にグラフが連結である必要がある。 残した辺のコストの総和を小さくしたい。
なお、グラフの辺は最小全域木$5$個の和集合である。

初動

木以外を作る意味はないので最終的には木だけが完成するようにする必要がある。 後の方の辺の重さが分からない状態である辺を使うかどうかを決めないといけないので、後の方の辺の重さを適当に決めておく必要がある。これは期待値である2倍にする場合とそれぞれランダムに決める場合があると思うが、とりあえず $2$ 倍に設定して毎回最小全域木を求めると、$13917323561$ 点($221$ 位相当)になる。実際には使う辺の倍率は $2$ 倍よりも小さいので、適当に $1.8$ 倍とかに設定して求めると $14080471444$ 点($153$ 位相当)とかになる。

辺の重さをランダムに

一律に何倍とかに決める代わりにそれぞれの辺の重みをランダムに決めてから最小全域木を求めて、辺を使う場合と使わない場合のスコアの期待値を比較する。これを時間いっぱい回すと $14136487217$ 点($59$ 位相当(強くない？))になる。辺の使用状況を見ると、最初の方の辺と最後の方の辺で使用率が異なるように見えたので、不明な辺の重さをランダムに決めたあと適当に定数を加えると調整できると考えたので、何個か試すと $2$ 加えるのがよさそうだったのでそうする。$14189655151$ 点($28$ 位相当)になる。

高速化

手元で動かすときに生成回数を増やしてみるとかなりスコアが改善されたように見えたので高速化を行うことにした。各辺について過去の採用確率を求めてみると、過去の採用確率が実際の採用確率に強く影響しているように感じたので過去の採用確率が一定以上だと強制的に採用するようにした。あと、最初の方の探索回数を犠牲にして後ろの方の探索回数を増やしたが、これは効いてるかよくわからん。ここまでで $14205289770$ 点($19$ 位相当)

スコアの差の期待値が大きくなった場合途中で採用/非採用を確定するようにするとかなり速くなる。$14224313041$ 点($8$位)

やらなかったこと

あらかじめグラフを生成しておくと、毎回辺のソートしなくてもいいらしい。

おまけ

これ、下の方はほぼ採用されるし上の方はほぼ採用されないので予想するだけ無駄みたいなのがあるのか？