AGC 033 D - Complexity

• 問題
• AC

$f(y_1, x_1, y_2, x_2) :=$ 矩形$[y_1, y_2) \times [x_1, x_2)$の複雑度

とすれば自明な漸化式が導けるが、時間的にも空間的にも間に合っていない。そこで、次の点に注目する:

• 複雑度は高々$\lceil \log_2(HW) \rceil = 16$と小さい
• $x_2$や$y_2$が増加すると複雑度は単調に増加する

したがって、ナップサックDPのように値と変数を入れ替えたDPができる。具体的には

$f(y_1, x_1, y_2, c) :=$ $[y_1, y_2) \times [x_1, X)$の複雑度が$c$以下になるような最大の$X$
$g(y_1, x_1, x_2, c) :=$ $[y_1, Y) \times [x_1, x_2)$の複雑度が$c$以下になるような最大の$Y$

としてDPする。$f(y_1, x_1, y_2, c)$の漸化式を与える。左右に分割する場合に限った$X$の最大値は、複雑度$c-1$以下の2つの横に並んだ矩形についてできるだけ横幅の合計を大きくすることで達成できるので

$f(y_1, f(y_1, x_1, y_2, c-1), y_2, c-1)$

また、上下に分割する場合の$X$の最大値は、複雑度$c-1$以下の2つの縦に並んだ矩形を、高さの合計が$y_2$以上になるようにするという条件でできるだけ横幅を大きくすることで達成できるので

$\argmax_X \bigl( g(g(y_1, x_1, X, c-1), x_1, X, c-1) \ge y_2\bigr)$

となり、この2つのうちの大きいほうが$f(y_1, x_1, y_2, c)$である。（後者は二分探索で得られる。） 同様に、$g(y_1, x_1, x_2, c)$は

$g(g(y_1, x_1, x_2, c-1), x_1, x_2, c-1))$

$\argmax_Y \bigl( f(y_1, f(y_1, x_1, Y, c-1), Y, c-1) \ge x_2 \bigr)$

の大きいほうに等しい。

$\alpha := \max (H, W)$とするとき、計算量は${\mathcal O}(\alpha^3 \log^2 \alpha)$。かなり厳しそうだが、TLが5秒なのでメモ化で一応通った。想定はボトムアップのDPで尺取り法っぽくやって${\mathcal O}(\alpha^3 \log \alpha)$らしい。

参考:
http://drken1215.hatenablog.com/entry/2019/05/10/215400