ABC475 F - Rectangle Filling

考え方

まず、$O(H^2W^2)$ くらいでもいいと思って考えてみる。
できた盤面ごとに、そうなるような最も狭い範囲のときだけカウントすると考えてみる。
すると、上下左右の端の列全てに白マスがあるようなもの $+1$ だけ考えればよいことになる。
$+1$ は、そもそも操作をしない分。

こうすると、上下左右の端の選び方を全探索すれば $O(H^2W^2(H+W))$ で求められる。
各行各列の白マス数を累積和を事前準備しておけば、$O(H^2W^2)$ にもできる。

さて、これを $O(H^2W)$ に高速化しよう。
つまり、上下については同じように全探索をして、左右方向を $O(W)$ に高速化する。

ある右端を固定したときに、選べる左端の個数を考える。

まず、その上下区間のなかで、白マスが $1$ つもない列は、そもそも存在を無視してよい。
これを調べるのは、上下幅の探索順を利用することで、上下区間 $1$ つあたり $O(W)$ でできる。

そして、選んだ左端との間で、最上段と最下段それぞれ $1$ 回以上白マスが登場していなければならない。
つまり、以下の値が $O(1)$ 分かっていれば、右端 $1$ ヶ所での値を $O(1)$ で求められる。
単純に、上下の最終登場位置の小さい方がその個数となる。

• その右列より左に、白マスが $1$ つ以上ある列が何個あるか
• 上で数えた列の中で、最後に最上段/最下段に白マスがあったのは何番目だったか

これらは、右端の位置をだんだん右に動かしていけば、動的計画法の要領で合計 $O(W)$ で求められる。
これで、$O(H^2W)$ で求めることができ、$H \leq W$ であれば解けた。

$H>W$ である場合は、最初に対角線反転で転置すれば $O(HW^2)$ で解ける。
両方を合わせて、計算量は $O(HW\min(H,W))$ となる。

入力例1での動作

入力を受け取る。

h: 2
w: 3
s:
"#.."
".##"

白マスは $(1,2),(1,3),(2,1)$ の $3$ マスである。
$H=2\leq W=3$ なので、転置は行わない。

まず、操作をしない場合を $1$ 通りとして数えておく。

次に、上下端の組を固定して数える。
その上下区間の中に白マスが $1$ つ以上ある列だけを残し、左から $1,2,\dots$ と番号を付ける。
右端を左から順に動かしながら、最上段・最下段に白マスが最後に現れた列の番号を更新する。
その小さい方が、その右端に対して選べる左端の個数になる。

操作をしない $1$ 通りも合わせて、答えは $1+3+2+1=7$ となる。

注意点

特になし。

別解

特になし。