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

THIRD プログラミングコンテスト 2021 （AtCoder Heuristic Contest 007）に参加して、優勝しました。

問題

解法

辺が与えられるたび、今の辺を使わない場合に代わりに使うことになる辺の長さの期待値をモンテカルロ法で求めます。

具体的には、今の辺は使わないと仮定し、まだ長さのわからない各辺の長さを $d _ i \leq l _ i \leq 3d _ i$ の範囲で一様にランダムに決め、クラスカル法によって最小全域木を求めることを考えます。今の辺の両端点が初めて連結になるときの、追加した辺の長さの平均値を求めます。

代わりに使うことになる辺の長さの期待値が今の辺の長さの0.95倍以上となるときに今の辺を採用し、そうでない場合は採用しません。

コード：Submission #27880973 - THIRD PROGRAMMING CONTEST 2021 （AtCoder Heuristic Contest 007）

解説（なぜ0.95倍するのか）

辺 $i$ を採用するか否かでスコアに影響するのは、 $u _ i$ と $v _ i$ を結ぶパス上の最長の辺の長さの分だと仮定します。辺 $i$ を採用した場合のこの値は $l _ i$ ですが、辺 $i$ を採用しない場合のこの値は厳密には計算できません。（その後の解答プログラムの挙動に依存するため。）その代わりにすべての辺の長さが分かっているとして最小全域木を求めてその際の値を使っていますが、これは実際に達成できる値よりも小さくなっているはずなので、前者を0.95倍して調整します。（0.95という値はいろいろ試して決めるほかないです。）

細かい工夫

辺の長さは高々 $2400 \sqrt {2}$ で抑えられ、実際にはグラフの作り方からもっと小さくなるので、クラスカル法で辺をソートするする際にはバケットソートすると速くて試行回数が増やせます。

延長戦

モンテカルロ法をする際に範囲を少し小さくとるとスコアが改善するという話がありました。

参照：

#AHC007
14,239,593,099(3位!!)
まだ使用を確定させていない辺の長さを乱数で変化させて、
長さが判明した辺を使うかをx回やって多数決で決める。
xは、i(<M/2)ターン目なら361、そうでないなら701。
乱数で変化させる際、rand(1.13d,2.87d)にした
(これが1と3の場合、14.18Gになる)
— bin (@5bin101) 2021年12月12日

試してみるとこの解法でもスコアが良くなりました。

（14241733941->14243380547）

コード：Submission #27894297 - THIRD PROGRAMMING CONTEST 2021 （AtCoder Heuristic Contest 007）

正確なことはわかりませんが、モンテカルロ法をして平均値を求める際には多少分布が歪んでも収束が速い（つまり分散が小さい）方が良いということだと思います。

自分語り

こういった記事を書くのは初めてなので簡単に自己紹介をしておきます。

中高生のときは情報オリンピックや数学オリンピックに参加していました。JMO、JOIで優勝したこととIMOで銅メダル、IOIで金メダルを獲得したことがあります。

大学に入ってからも競技プログラミングを続けていて、普段はアルゴリズムコンテストに参加しています。ICPCにもUT a.k.a. Isのメンバーとして参加しています。

ヒューリスティックコンテストには2年ちょっと前くらいから参加し始め、2020年5月にあったAsprovaコンテストあたりから熱心に参加するようになりました。

2021年にAHCが始まったときにヒューリスティックコンテストでそれなりに上達することを2021年の目標の一つにしていたので、2021年最後のAHCで優勝できて良かったです。