問題概要
文字からなる $h \times w$ のグリッドがあり，セル $( i, j )$ に書かれた文字は $S_{ i, j }$ で与えられ，$S_{ i, j } \in \{\text{$`$o', $`$x', $`$.'} \}$ である．
このグリッドに対して，次の操作を $0$ 回以上適用することができる：
- $S_{ i, j } = \text{$`$.'}$ な $( i, j )$ をひとつ選び，$S_{ i, j } \leftarrow \text{$`$o'}$ をする．
縦または横に連続した $k$ 個のセルについて，それらに書かれた文字が全て $\text{$`$o'}$ であるような状態*1にするために必要な操作回数の最小値はいくらか？ 不可能な場合はそのことを報告せよ．
制約
- $1 \leq h, w$
- $h w \leq 2 \times 10^5$
- $1 \leq k \leq \max( h, w )$
解法
$S$ を転置して得られる $w \times h$ グリッド $$S^T_{ j, i } = S_{ i, j }$$ を考えると，$S$ における縦の条件は $S^T$ における横の条件になるので，横の条件だけについて考える部分問題を $S$ と $S^T$ の両方について解いて，答えたちの内大きくない方をとれば元の問題が解けたことになります．また，横の条件というのは各行について独立なので，$$f( T ) := \begin{cases}
\text{文字列 $T$ 中に連続する $k$ 個の $\text{$`$o'}$ を作るために必要な操作回数の最小値} & \text{(条件を満たせるとき)} \\
\infty & \text{(otherwise)}
\end{cases}$$
*2という関数を実装できれば，その最小値 $$\min_{ 1 \leq i \leq h } f( S_i )$$ をとることで部分問題を解けます．
では，文字列 $S_i$ について解くことを考えましょう．$S_i$ の $l$ 文字目から $r - 1$ 文字目 ($1 \leq l \leq r - 1 \leq n$) までを取り出して得られる部分文字列を $S_i[ l, r )$ と書くことにします．連続する $k$ 文字をとる位置を全て試すことにします．次のようなコスト関数 $$\mathit{ cost }( c ) = \begin{cases}
0 & \text{($c = \text{$`$o'}$)} \\
\infty' & \text{($c = \text{$`$x'}$)} \\
1 & \text{($c = \text{$`$.'}$)}
\end{cases}
$$ を考えます．ここで，$\infty'$ は適当に大きい定数であるとします*3．また，文字列 $T$ を全て $\text{$`$o'}$ にするコストを求める関数 $g( * )$ を考えると，部分文字列中の文字全てを $\mathit{ cost }$ に食わせてから和をとればよいので，$$g( T ) =\sum \{\{ \mathit{ cost }( c ) \mid c \in T \}\}$$*4 です．これを使うと，$S_i[ j, j + k )$ を全て $\text{$`$o'}$ にするコストは $$g( S_i[ j, j + k ) )$$ と書け，$j$ のとり方を全て試せば行に関する答えが求まるので，$$f( S_i ) = \min\limits_{ 1 \leq j \leq n - k + 1} g( S_i[ j, j + k ) )$$ となります．
正しい値を求めるだけならばこれでよいのですが，
- 部分文字列の走査に $O( w )$ 時間．
- 部分文字列が行あたり $O( w )$ 個．
- それが $\Theta( h )$ 行分ある．
ので，全体で $O( h w^2 )$ 時間となって TLE するので，より高速に計算する必要があります．やや唐突な感じもありますが，$g( S_i[ j, j + k ) )$ を知っている状況から $g( S_i[ j + 1, j + k + 1 ) )$ を高速に計算できれば，$j$ を順にズラしていくことで，必要な値たちを求められます．$S_i[ j, j + k )$ と $S_i[ j + 1, j + k + 1 )$ の差分を考えると，$S_i[ j, j + k )$ の先頭文字を取り除いてから後ろに $S_{ i, j + k }$ を連結すると $S_i[ j + 1, j + k + 1 )$ が得られます．このことから，コストの関係は $$g( S_i[ j + 1, j +k + 1 ) ) = g( S_i[ j, j + k ) ) - \mathit{ cost }( S_{ i, j } ) + \mathit{ cost }( S_{ i, i + k } )$$ となります．各値を適切に保存しておいて適宜読み出せば，$j$ を $1$ ズラしたときの次のコストは $O( 1 )$ 時間で求めることができるようになります．行ごとに $j$ が $O( w )$ 回動いて，それが $\Theta( h )$ 行分あるので，全体で $O( h w )$ 時間となって，これなら間に合います*5．
あとは，$$\min\left( \min\limits_{ 1 \leq i \leq h } f( S_i ), \min\limits_{ 1 \leq i \leq w } f( S^T_i ) \right)$$ を出力すればよいです（値が $\infty'$ 以上のとき，不可能であることを表します．）．
コード
constexpr auto INF = LIM<>::max() / 2; int cost( const char c ) { switch ( c ) { case 'o': return 0; case 'x': return INF; case '.': return 1; } assert( false ); return -1; } int solve( const VS &board, const int K ) { const int H = SZ( board ), W = SZ( board[0] ); if ( W < K ) { return INF; } LL res = INF; FOR( row, board ) { LL c = 0; REP( j, K ) { c += cost( row[j] ); } chmin( res, c ); REP( j, K, W ) { c -= cost( row[ j - K ] ); c += cost( row[j] ); chmin( res, c ); } } return res; } int main() { IN( int, H, W, K ); VS board( H ); cin >> board; VS boardT( W, string( H, '-' ) ); REP( i, H ) { REP( j, W ) { boardT[j][i] = board[i][j]; } } const LL res = min( solve( board, K ), solve( boardT, K ) ); cout << ( res == INF ? -1 : res ) << endl; return 0; }
