はまやんはまやんはまやん

hamayanhamayan's blog

Nasty Queries [CodeChef May Cook-Off 2017]

https://www.codechef.com/problems/COOK82D

問題概要

N頂点M辺の無向グラフがある。
良いグラフは「全ての頂点がその頂点から初めて全ての辺を通りその頂点に戻ってくるパスが存在する連結なグラフ」とする。
完璧なグラフは「全ての連結成分が良いグラフであるグラフ」とする。
Q個のクエリが与えられ、[L[i],R[i]]の辺のみ使ったグラフは完璧なグラフか判別せよ。

※ 問題文と違い、Deadwing=完璧と訳している


















解法

良いグラフの条件は丁度オイラー路の存在条件と一致する。

その為、[L[i],R[i]]の辺のみつかったグラフで全ての頂点の次数が偶数であるかをチェックすればよい。
これはすぐに思いつく。あとはクエリをどう高速化するか。2通りのやり方がある

Mo's Algorithm解
https://www.codechef.com/viewsolution/13710325
ぱっとみて、Mo's Algorithm使うだろうな感が強いので、これを使ってみる。
丁度、区間を伸ばす操作は簡単に行えるようなので、これで通るやん!という感じ。
N=10^6,Q=10^6なので、O( (N+Q)sqrt(N))が既にO(20^9)でTLEやばそうな感じはある。
本番は定数倍高速化しきれずにACできなかったが、これで通している人はまあまあいる。


ハッシュ解
https://www.codechef.com/viewsolution/13710441


コドフォのコメントのハッシュ解
Zobrist Hashの方は理解していないが、Rolling Hashで今回はいける。

まずbitmaskとして考えてみる。
各頂点の次数が偶数なら0,奇数なら1として、i番目の辺まで使った時のbitmaskを考えてみる。
すると、[L,R]番目の辺を使った時のbitmaskは「R番目までのbitmask xor (L-1)番目までのbitmask」であることが分かる。
今、完璧なグラフになるにはこれが0になる必要があるため、言い換えると、「R番目までのbitmaskと(L-1)番目までのbitmask」が等しくなれば良い。
これを高速に判定するためにハッシュを使う。
Zobrist Hashはxorを使ったハッシュらしいので、この辺がZobrist Hashを使うヒントなのだろうか。
自分の解法ではRolling Hashで通している。

追記: Zobrist Hash解で通した 解法