THIRD プログラミングコンテスト 2021 (AHC007) 参加記
問題
結果
14,165,902,434点で39位。
解法
毎ターン、不確定の辺の長さを[d, 3d]からランダムに決めてクラスカル法でMSTを求めることを複数回行い、半分以上で対象辺が使われていたら採用する。解法としてはこれだけで、ひたすら高速化していた。以下高速化のためにやったこと。
- 前処理として、全部の辺の長さをランダムに決めてMSTを求めるのを150回行い、150回すべてで採用された辺は採用確定、1回も採用されなかった辺は不採用確定とする。
- MSTを複数回求める部分で、はじめの5回全て不採用だったら不採用とする。
- 採用の閾値を超えたら終了。また、残り全て採用でも閾値を超えないなら終了。
- クラスカル法のUnion-Findで、すでに確定した辺をuniteするところは同じ操作となるので、そこまで終了した時点での状態(親の配列とランクの配列)を保存して、毎回それを復元してMSTを求める。
- ソートすべき辺はvectorで管理して、確定した辺は順次削除していく。
以上をやって1ターンに60回程度のMSTを行なった。
反省点・その他
- ある程度MSTの試行回数が増えるとスコアの伸びに限界が見えたので、何か工夫をしないととは思っていたけど、結局いつもの通り何もできずに終わった。どうすればいいですか？
- [d, 3d]ではなく[1.13d, 2.87d]とかにするとスコアが伸びるらしいのでやってみたところ14.2Gを超えた。生成ロジック通りにやるのが最善じゃない場合もあるというのは覚えておく。
- 50位以内入ったし転職できるならしようかな。
