Educational Codeforces Round 58 F Trucks and Cities

https://codeforces.com/contest/1101/problem/F


したのコメントの やりかたのホウが はやそうだ。サイダイチが かわるカイスウのキタイチが O(log N) であることを うまくいかしていて すごい。

https://codeforces.com/blog/entry/64438?#comment-483640

こういうのが すでに かかれてたのか。

https://codeforces.com/blog/entry/62602

ボクも randomized だけど すこし ちがう。


すべて ニブタンすると まにあわない。そこで ランダムに ひとつ えらんで その こたえだけ もとめる。そうすると もともとあったハンブンは このこたえを したまわる はずだから けしてよい。これによって どんどん ハンブンに へらせるから はやくなる。

ただし これでも まにあわなかったので マイカイ 10 コをサンプリングすることにした。マイカイ 1/2 よりは 1/10 のほうが はやいが ケイサンリョウは おなじで O(NM) である。

https://codeforces.com/contest/1101/submission/48256161



DP でも いけるらしい。どっちが ソウテイカイなんだろう。

ホウとかヨウ とか オンかあやしくて あてジだったら もうしわけない。