Aobayama sugerstep(ha15 mine691 tarakojo1019) で参加 mine691 視点
コンテスト
多分最初のほうは難易度順だろうから A tarakojo1019, B mine691 だけ決めて、ha15 には全体を見てもらう
Bを読むと最小全域木やるだけじゃん？ってなったけど誤読してた。頂点云々よりも区間を分割する問題。パニックになってヘルプを出したけど冷静になったら簡単だった。
区間を指定したとき、その区間の中央値をワープポイントに割り当てればよく、これは座圧して BIT するとできる。あとは累積和を用いて DP をすればいい。
ところで、 BIT の lower bound がバグっていて中央値が取得できません。仕方ないのでうしさんのを借ります。AC(02:17)
開始15分くらいでAが通っていたらしい。涙
ha15 が E をやっているらしい。差分制約どばあな問題なので牛ゲー（最短路問題の双対）になりそう と指摘。できそう。書きます書きます。丁寧に丁寧に辺を貼る。
ところで値の範囲を [-1e9,1e9] だと思って 1WA しました。涙の AC(04:00)
ha15 が F に出して WA が出たらしい。解法自体は正しそうなので誤差の可能性を疑う。
CHT の色々を long double でやっていて、long long でできるところは long long でやる。
ここでもまたうしさんの CHT を拝借する。もう時間がないのでとりあえず出す。AC(04:42)
通らないと思ってたので反応に困る。
感想
Bで詰まると全てが終わる。二週間ぐらい競プロやってなかったから実装が下手になってた。
今日から熱烈 Codeforces 精進をします。
