■146F - Sugoroku
単純にdpをするとO(NM)かかる
貰うdpで考えると結局欲しいのは区間minなので
セグ木におまかせする。
■147F - Sum Difference
選ぶ個数に着目する。
数列が(4,6,8,10)だったとすると
２個選ぶ場合：10,12,14,16,18
３個選ぶ場合：18,20,22,24
という感じで小さい方からi個数選んだ場合から大きい方からi個選んだ場合
の間を交差Dでまんべんなく選択できる。
mod Dで考えれば場合分けそうな気がする。
上の例だと
２個は0+2*5から0+2*9を
３個は0+2*9から0+2*12なので
[5,9],[9,12]のような形管理しておき
最終的にmodごとで[5,12]のような形にマージすると答えが出る
マージ部分は座圧imos法っぽくすれば良い。
dが負のケースがあるので単調増加にならないことに注意。
d = 0もコーナーケース。
■148F - Playing Tag on Tree
dfsを２回する。
注意する点は、捕まる場所は葉ではなく、葉の親になること。
■149F - Surrounded Nodes
各点を独立に考える。
?-0-?
見たくなっていたとして
穴あきにならないのは全ての?上の頂点がすべて白
と
どれか一つの?には黒があるが、それ以外の?には白しかない時。
なのでdfsすれば良い。
■150F - Xor Shift
xorで書いているからややこしくなるのであって
ただの数列に+xして一致するかのように考えればよい
1,2,5を
11,7,8をシフトと+xをして一致できるかはかは差を見れば良い
というわけaとbの階差数列を用意しそれらがスライドしたら一致するかを考えれば良いので
bを2周分持つようにし、KMPを使う。
