THIRD プログラミングコンテスト 2021 （AtCoder Heuristic Contest 007）に参加しました。
問題はOnline MST。不完全情報から最小木を作るインタラクティブ問題でした。
結果は提出632人中158位でした。ジャスト上位25%。
問題
予測値でなんとなく最小木候補を作ってあるけど、実測値で改めて作り直してね。
辺のコストを1つ受け取るたびに、その辺を採用するかを決めてね。
コストは距離(事前に分かる)の1～3倍の一様乱数だよ。
考察
候補辺の生成方法が最小木作成の抽出*5回なので、複数候補のコスト値はかなり近いものになっていそう。
とはいえとりあえず実距離で最小木を作って、受け取った実コストを見て変更をかけるのが本筋かな。
コストの他に可能性の大小という要素があって、見送っても代わりとなる辺(より低い、悪くても同程度のコストで最小木を構築できる)があるなら採用見送りしやすい。
モンテカルロも有効そうだけど、チューニングも考えると実装時間も実行時間も厳しそう。
実装
～1:00
とりあえず距離で最小木を作成。12,602,465,243点。
1位が14G強なので、1割強上がる感じか。
～1:12
一括実行のスコアを拾ったりするデバッグ環境を整える。
～1:56
実距離の最小木(0手目に1回作成)を保持して差異を判断するつもりだったけど、場合分けして差分計算って残り2時間でバグ取りまで出来るのか？そもそも拾い落としも多いよな？と考えて、厳しそうなので毎回最小木を作る方針にシフト。
～2:16
動いた。1割くらい上がっているけど1ケース10秒かかってる。(制限は2秒)
～2:46
2秒程度に速くなったけどバグって解が壊れた。苦しい。
～3:30
直った。
一番効いた高速化は、辺を予めコストの昇順にソートしておくこと。
なお、バグはここで採用を見送った枝が残って悪さをしていた。
お祈りしてsubmitすると、1秒弱でAC。13,915,411,325点。
…いや、順位低くない？
～3:50
橋でない場所を検出して、見送りすれば後で改善される確率みたいなのを求めてみる。
あの、橋でない場所が無いんですが…。
～3:59
未知の情報への期待。なんか聞き覚えあるな…。あ、AHC003か。あれは未知の道の見込みコストを期待値より下げたんだったか。0.9倍、0.85倍、0.95倍と10ケースほど試して、0.9倍が一番良かったので採用。*1
実際は序盤は改善可能性が高くて終盤は低いので、一律0.9倍でない方が良さそうなんだけど、残り90秒では調整もできない。
14,079,155,614点で終了。
…いや、順位低くない？(2回目)
やり残し
・0.9倍部分の可変化
・端数処理が雑だった(四捨五入の箇所を切り捨てにした)
他の人の解法
上位はモンテカルロで数十～数百回シミュレーションしてる人が多かった。
私は辺のコストを1つ受け取るごとにクラスカル法+UnionFindで最小木を作って1000ms前後かかっているので、2回しかシミュレート出来ない。*2何らかの高速化が出来ないと駄目そう。
writer解はDPらしい？*3
同じ解法で私よりスコアが高い人もいたけど、端数処理をしっかりした、同値でどちらを優先したかの差、辺りかな。倍率可変の人はやっぱり少し上らしい。
感想
苦手な短期マラソン(4h)にしては頑張ったというべきか。ロスも多かったとはいえ、ちょうど時間内に大きな改修をやりきったので身の丈に合わせて方針を選べるようになったというのは良い所。
高速化でバグったときにAssertを仕込んでみたらあっさりと解決したので、今後も不味そうなときは使ってみたい。あと、やる事は同じ高速化でも、コミット単位は小さくした方が良いですね。どの箇所でバグったか明確になるので…。
見えてる情報からの最善は選んだけど、可能性部分はあまり深堀り出来なかったかな。橋でない所はまず無いとかはビジュアライザを見れば気づけたので、まだ余分な動きはある。*4*5そこをやらなければ倍率可変化は出来ていたので…。
あと今回はUnionFindをとても多用する回だった。今まではUnite回数≒Root回数の用途が多かったけど、今回はひたすらRootが多かった気がする。ここのバランス次第でUnionFindの最適な実装が変わってくると思うので、実験してみたいかな。
