Codeforces 514Dの解いろいろ

こどふぉす 過去問

http://d.hatena.ne.jp/phyllo_algo/20150215/1423985061

Codeforces 514のD問題をかなり微妙な解法で通ってしまっていたけど、テストケースが35個ぐらいでそんなに悪意のあるケースがないためたまたま通ってしまっているようにも思われる。


http://kmjp.hatenablog.jp/entry/2015/02/15/0930
http://codeforces.ru/blog/entry/16398

解法はいろいろあるようだけど、想定解法がO(NM)のようで、しゃくとり法＋s〜eの最大値をO(1)で求めることになっている。uwiさんに「スライド最大値」という方法を教えてもらったのでまとめておく。

O(N^2 M)+無駄な計算を省く

http://d.hatena.ne.jp/phyllo_algo/20150215/1423985061
上のところで書いた方法で、しゃくとり法のときにs〜eの最大値をもとめてs+1していくのではなく、eから条件を満たす間sを広げていく方法。
しかし、これはO(N^2 M)なので、うんこ。撃墜。
(s〜eが大きくて、s〜e+1が条件を満たさずs+1〜e+1が条件を満たすようなものが連続するようなもの、、、作れるか怪しい)。

撃墜ケースの例

machyさんに、以下のケースでhackされました。(手元MBAでは25秒ぐらい)

100000 5 100000
99996 1 1 1 1
99995 1 1 1 1
...
74997 1 1 1 1
1 1 1 1 1
...
1 1 1 1 1
1 2 1 1 1
...
1 25001 1 1

「1 1 1 1 1」までは条件を満たすのでeを伸ばせるが、「1 2 1 1 1」は「99995 1 1 1 1」まで戻らないといけないので、大雑把に25000*75000*5=9.4*10^9回参照が必要になる。なるほど。


O(Nlog(N)M)解

しゃくとり法であれば、s〜eの最大値を効率的に求めるのに、SegTreeを使うとO(log(N))で求められる。
sを固定して、最大のeをSegTreeの二分探索で求める方法でもO(log(N))になる。

O(Nsqrt(N)M)解

kmjpさんのブログで紹介されている、平方分割でeを求めるとO(sqrt(N))になる。

O(NM)解

しゃくとり法で、s〜eの最大値をO(1)で求める必要がある。
これは「スライド最大値/最小値」という両端queue(deque)を使う方法を使うと実現できる(蟻本上級編)。
蟻本では、dequeを、「i