解説と少しだけ方針が違ったのでメモ。
ある縦の行の区間 \([i,j]\) と、左端をとる列 \(k\) を固定して、(複雑さ \(x\) を考慮するときに)とれる右端の最大値を
dp[行の区間 \([i,j]\) ][左端をとる列 \(k\) ]={可能な右端の最大値(存在しない場合-1)}
という感じでdpしていくことを考えます。
複雑さ \(0\) の時の初期化は見なかったことにします(ちょっと面倒ですが累積和とかこねこねしたらできます(気になる人は実装を参考にしてください))
複雑さ \(x\) の場合のdp配列をdp、複雑さ \(x+1\) の場合のdp配列をndpで表します。(dpは遷移元、ndpは遷移先といった感じ)
まず、横に並んだ複雑さ \(x\) のブロックを2つ合わせて複雑さ \(x+1\) のブロックにするような遷移は簡単です。場合分けが少し発生しますがだいたい
\(ndp[ [i,j] ][k]=dp[ [i,j] ][dp[ [i,j] ][k]+1]\)
でokです。
面倒なのは縦に並んだ2つの複雑さ \(x\) のブロックの合成。
ここで、 \(O(N^3)\) 程度で解くために、要素2つ固定+線形というイメージを立てると、次のような遷移が浮かびます。
左端のある列 \(k\) と、ブロックの合成が発生する位置 \(p\) を固定する。そのうえで、合成対象のブロックの、上側の上限 \(st\) と下側の下限 \(fi\)を動かしていくことを考えます。(図のイメージ)
ここで、重大な観察として、「 \(st\) を引き上げても、 \(fi\) を降ろしても、動かした側のブロックの右端も求まる右端もだんだん小さくなっていく」ということが言えます。(複雑さ \(x\) のブロック、をイメージすれば複雑さの定義から直ちに理解できるくらいだと思います)
結論から言うと
\(ndp[ [st,fi] ][k] = min(dp[ [st,p] ][k] , dp[ [p+1,fi] ][k])\)
という遷移になるのですが、このうち「 \(st\) を1つ上に動かす」「 \(fi\) を1つ下に降ろす」のうち、甘いほうを行って遷移を続けるといったことを繰り返せば、だいたいうまくいきそうなことは分かります。
ただし、このままだと遷移を全て行えるわけではない(条件が甘い部分の遷移が甘い(伝われ))ので、 \(ndp[ [i+1,j] ][k]\) と \(ndp[ [i,j-1] ][k]\) に \(ndp[ [i,j] ][k]\) を遷移させるということを行えば、区間 \([i,j]\) より明らかに緩い条件の区間 \([i+1,j]\) と \([i,j-1]\) に遷移を伝搬することが出来ます。
このあたりの話も実装を見ていただくとわかりやすいとおもいます。
(直感的にこれで解ける、というのは分かるがちゃんと説明しようとすると言語化が難しいなこの問題…)
Submission #11653626 - AtCoder Grand Contest 033
