# 2021/12/12　AHC007(THIRD)

https://atcoder.jp/contests/ahc007

◆感触
全域木をつくる問題。辺はすでに決まっているがコストが未知。
ユークリッド距離のL～3*Lまでの間なので、期待値問題。
最初にユークリッド距離で決めてしまって、その上で工夫ごにょごにょかな。

- 16:40
クラスカル法で、単純に最小全域木は求まった。
次、でかい値が来た時に、飛ばして別の所から繋げるかを考える。
距離のブレは一様ランダムっぽい。1～3倍なら、2倍をしきい値に考えれば良さそう。

- 17:10
お、できた。
今度は逆に小さい方もやる
逆も良さそう出す。
- 17:20、WAあれ？

- 17:30
d > L*2で除外する時、最終形の接続判定忘れてた。OK。
64位、13,931,658,236点
んー、しぶい。
1位が14,208,658,311点

- 17:45
ブレの倍率の調整をした。1.8が一番良さそう。
→倍率を基準によりよい方を取るので、単純平均値よりも良さ目に寄るのはそう。

63位、14,073,929,927点
こっから上が詰まっている。

ある頂点からの残っている辺について、サイコロを降って最小値を更新する可能性が高いなら、見送るのが良さそう。
ちゃんと計算するより、例えば11個先に決めた世界があって、多数決で採用不採用が多い方に寄せるとか。

- 18:30
13個の世界を作って、採択率が過半数-1以上の時に採用。(ちょっと強引目に採用した方がいい？)
こうなると高速化の世界。
確定したやつはさっさと採用する。

- 19:10
24位、14,124,692,080点
よっしゃ。この方向で後はひたすら高速化勝負。
世界19個がギリギリかな？それ以外になんかないかな。
37位、14,147,099,916点。苦しい。

- 最終
悪あがきして40位、14,165,184,043点。

## 感想戦

上位はMTSしてた。確かに後半の辺が確定しているのとしてないのとで、選択は変わる。
wataさんはDPで1位。なるほど、わからん。
https://atcoder.jp/contests/ahc007/editorial/3099