yukicoder contest 464

　ABの二完。

コンテストへのリンク

No.3101 Range Eratosthenes Query

　解説AC。これが見えなかったのは良くない。

　たとえば、[L,R]中にあるx=20を食べるかどうか考えるとき、xの1でない一番小さい約数は2なので、20/2=10が[L,R]中に存在するかどうか、で判定できる。Lが10以下か10以上かで変化する。

　このことに気付いていなかった。

　これが分かれば、クエリを先読みし、Lの順にソートして見ていけば解くことができる。

No.3102 floor sqrt xor

　解説AC。

　x^√xを考えると、上半分の桁はxのままなことを利用できそう。xを動かすとまずいけど、√xを固定すると、ルートして切り捨てた値が√xになるような範囲が分かるので、それで調べられる。

　……というようなことを考えたはずなのに、実装する段階になると分からなくなってTLEの解法を書いてしまい、解説を見て考察していた内容を思い出した。

　ちょっとあやふやなところはあったけど本質的解法は一度自力で考察したはずなので、時間があれば解けていたと信じたい。

No.3103 Butterfly Effect

　自力AC。

　その人がはじめて噂を知った時刻を持って、毎回ダイクストラすれば良いように見えるが、それだとTLE。

　同じ辺は二度通らないように見えるため、なぜTLEするのかしばらく気付けなかった。

　なぜTLEするかというと、ある人から辺（AさんとBさんの噂話）がたくさん出ているとき、（伝播しないのに）それらの辺を何度も見ることがあるため。

　じゃあ、「同じ辺は二度通らない」という性質があるのなら、辺もheapqで持ち、一度通った辺は削除すれば良い、と気付きAC。

　「ダイクストラで解けそう」という方針自体は思いつきやすいけれど、ちゃんとそこから一捻りしてあった。