Xmas Contest 2019 H - Stamps 3

問題はこちら。
snukeさんによる解説と方針が違ったので書いてみる。

とりあえず、上の解説に述べられている通り行ごとに独立に考えればよく、各行0, 1, 3回で塗れるかは容易に判定できる。
特に、事前に白マスの位置を配列で持っておくと、そのサイズをnとするとき、1回で塗れるかの判定はO(n + log W)でできる。(log WはGCDの計算のため)

さて、2回で塗れるかの判定についてであるが、「1つ目のスタンプを決めたときに、残った白マスを1回で塗れるか」を判定できればよい (ここまで上の解説と同じ)。
ここで、nマスを2回で塗れるということは、少なくとも片方のスタンプでn/2個以上のマスを塗る必要がある。このようなスタンプの間隔をpとする。
ところで、間隔pのスタンプで塗れるマスは高々ceil(W/p)個しかないので、ceil(W/p)>=n/2 が成り立たなければならない。言い換えると、考慮すべきpの上限はO(W/n)となり、nが大きければpの上限が小さくなる。
また、そのようなスタンプの初期位置についても、(白マス位置) mod pの頻度がn/2以上となるものだけ試せばよく、これは高々2箇所しかない。残った白マスを1回で塗れるかは前述の通り。

計算量は緩く見積もってもO(HW log W)となる。