12,599,577,888で438位でした。惨敗。
前置き
連結済みかどうか、連結成分が1になったかどうかなどはUnion-Findを使って判定しています。
時系列
初手
全部1を出力して、1338761965点を得ました。
・・・本当は連結成分が1になったら以降0を出力する（繋がない）というロジックにしていたつもりが、nとmを間違えてました。
初手やり直し
先程バグってたところを修正して、2570777203点。ここから当面の目標は頻出値の6600871568点となります。
すでに連結しているところは繋がない
連結済みのところを繋いでも無駄なのでそれは0を出力することにすると、6600871568点と出ました。なるほど・・・。
というわけで次の目標はこれも頻出値の126nnnnnnnn点あたりです。（なぜかこの点数帯に頻出値が数通りあったのが不思議・・・）
雑に間引く
l が d の2.5倍を超えたら繋がないという雑なロジックを入れるとWA。橋の部分は繋がないとだめなので、橋を判定するロジックを入れて投げ直すと7558805354点。まあ雑なのでそれほど伸びません。
2.5倍を1.5倍で判定すると9977083418点になり、それに加えてlが80以上で繋がないことにすると10072395311点となりました。適当な割には伸びましたね。
ここで、dとの差よりlの絶対値のほうが重要なのでは？と思い、lが80以上で繋がないのロジックだけを残すと11689141821点となり、閾値を70に変えると11817931965点になりました。
しかし 120億にはまだ足りないし、そもそもこの方針では伸びしろがなさそうで、発想を変えることを迫られます。
dが小さいものを優先
いきあたりばったりではダメなので、あらかじめ d で当たりをつけておくべきではと考え、手始めに d の小さいものを優先して採用する実装に変えました。（l はとりあえず無視）
すると12599577888点まで伸びました。
繋ぎ変え
上記のロジックで未使用となった辺をランダムで採用してつなぎ直す、を時間いっぱいまでやるようにしてみました。繋ぎ変える本数やランダムの頻度などいろいろ試して、seed0 ではそれなりに効果がありそうでも提出するとほぼ変わらず、しかも伸びずを繰り返しているうちにコンテストが終了してしまいました。
結局、前段の貪欲だけのものが最終スコアになってしまいました。ええ・・・。結局 l は全く使ってないし・・・。
まとめ
ひさびさに青パフォを逃したどころか緑パフォまで落ちてしまいましたが、レートが3だけ伸びてぴったり青になりましたｗ
