差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:contest_history:atcoder:2019:0504_agc033 [2019/05/09] – [解法] ikatakos
+++ programming_algorithm:contest_history:atcoder:2019:0504_agc033 [2019/05/10] – ikatakos
@@ 行 38: / 行 38: @@
     * $185^4 = 1,171,350,625$ であり、この時点で整数1個1byteとしても、メモリ制限を超えてしまう
   * 計算量
-    * ある長方形の複雑さを求めるには、全ての分割を試して最適を求める必要があり、計算量が $O(H^2W^2(H+W))$ くらいかかる（もっと効率的な方法があるのかも知れないが）
+    * ある長方形の複雑さを求めるには、全ての分割を試して最小値を求める必要があり、1つの長方形につき $O(H+W)$、全体で $O(H^2W^2(H+W))$ くらいかかる（もっと効率的な方法があるのかも知れないが）
 ===解説の方法===
@@ 行 57: / 行 57: @@
 $(a,b,c)$ によっては複雑度 $k$ では長方形が作れないかも知れないので、その場合はそれと分かる値、たとえば''-1''で埋めておく。
-DPは2段階で更新する。まず、DP1を使ってDP1を、DP2を使ってDP2を暫定更新する。次に、双方の情報を合わせてDP1、DP2を修正更新する。
+まず、$k=0$ の時を埋める。
-まず第1段階。a,b,cが決められたとき、「縦に分割するとして」複雑さkの長方形を最大限とることを考える。左右とも複雑さ $k-1$ になる長方形に分割するのがよい。
+$DP1[0][a][b][a]$ は、$(a,b)$ から数えて $a$ 行で同色が続く右限。これは各 $a$ に対して $b$ の大きい方から埋められる。
-    複雑さk-1     複雑さk-1
+$DP1[0][a][b][c]$ は、まず $(a,b)～(c,b)$ が全て同色でなければ ''-1''。同色なら $DP1[0][a][b][c]～DP1[0][c][b][c]$ の最小値で、各 $a,b$ に対して $c$ の小さい方から埋められる。
+続いてDPの遷移を考える。2段階で更新する。まず、DP1を使ってDP1を、DP2を使ってDP2を暫定更新する。次に、双方の情報を合わせてDP1、DP2を修正更新する。
+まず第1段階。a,b,cが決められたとき、「縦に分割すると決めて」複雑さkの長方形を最大限とることを考える。左右とも複雑さ $k-1$ になる出来るだけ広い長方形に分割するのがよい。
+    複雑さk-1 r   複雑さk-1
   (a,b)------>|(a,r+1)------->|
   |           |               |
@@ 行 75: / 行 81: @@
 よって、DP1[k-1][a][b][c] でまず左の長方形の右端を求めて（rとする）、次にDP1[k-1][a][r+1][c] で右の長方形の右端を求めると、それがDP1[k][a][b][c]の暫定値となる。
-DP2も、縦方向に同様にすれば求められる。
+DP2も、同様にすれば、横に分割すると決めた場合の暫定値を求められる。
 次に、先ほどの更新は縦に分割するという仮定をおいたが、実際は横に分割した方が複雑さが抑えられ、より右まで複雑度 $k$ のまま範囲を伸ばせるかも知れない。
-横方向の分割での最適な下限はDP2にあるので、それを使ってDP1を更新する。
+横方向の分割での最適な下限は $DP2[k]$ にあるので、それを使ってDP1を更新する。
 a,bを固定して、dを大きい方から見ていく。
@@ 行 85: / 行 91: @@
   |
-もしある $d=d_2$ の時、DP2によって、複雑度 $k$ の長方形の下限が $c_2$ であるとわかったとする。
+もしある $d=d_2$ の時、$DP2$ によって、複雑度 $k$ の長方形の下限が $c_2$ であるとわかったとする。
   (a,b)               (a,d2)
@@ 行 92: / 行 98: @@
                      (c2,d2)v
-$DP1[a～c_2][b][c_2]$ と $d_2$ を各個比較し、もし $d_2$ の方がより右なのであれば、$d_2$ に更新する。
+$DP1[k][a][b][a]～DP1[k][a][b][c_2]$ と $d_2$ を各個比較し、もし $d_2$ の方がより右なのであれば、$d_2$ に更新する。
   (a,b)            |  (a,d2)
@@ 行 144: / 行 150: @@
 ここで、$S$ が全て'R'だった場合、１．の条件さえ満たせばよい。
 この場合の数え上げは、フィボナッチ数列のようにしてできる。
+                    長さ   1    2    3    4    5    6
+  赤から始まり、末尾が赤   1 → 1 → 2 → 3 → 5 → 8
+                             ×   ×   ×   ×   ×    ＼
+  赤から始まり、末尾が青   0    1    1    2    3    5  ー この3つの合計が答え
+                                                       ／
+  青から始まり、末尾が赤   0 → 1 → 1 → 2 → 3 → 5
+                             ×   ×   ×   ×   ×
+  青から始まり、末尾が青   1    0    1    1    2    3
 </WRAP>