【AtCoder】ABC 442 F - Diagonal Separation 2

2026-01-31

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1295 / NoviSteps: 1D / 配点: 500 点

問題概要

$N \times N$ のグリッドがあり、グリッドの上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ と表す。

グリッドの各マスは白または黒に塗られていて、グリッドの情報は $N$ 個の文字列 $S_1, S_2, \ldots, S_N$ によって与えられ、 $S_{i, j} =$ . のときマス $(i, j)$ は白く塗られており、 $S_{i, j} =$ # のときマス $(i, j)$ は黒く塗られている。

あなたは、いくつかのマスの色を塗り替えて以下の条件をともに満たすようにしたい。

すべての行に対して以下の条件が成り立つ。
- $0 \leq k \leq N$ を満たす整数 $k$ が存在して、その行の左から $k$ 個のマスは白く塗られており、その他のマスは黒く塗られている。
すべての列に対して以下の条件が成り立つ。
- $0 \leq k \leq N$ を満たす整数 $k$ が存在して、その列の上から $k$ 個のマスは白く塗られており、その他のマスは黒く塗られている。

条件を満たすために塗り替える必要のあるマスの数として考えられる最小値を求めよ。

制約

$1 \leq N \leq 5000$
$N$ は整数
$S_i$ は., #からなる長さ $N$ の文字列

ここで、 $\min(\mathrm{dp}_{i-1, 3}, \mathrm{dp}_{i-1, 4}, \mathrm{dp}_{i-1, 5})$ は両方の計算で共通しているため、重複して計算されてしまっている。この部分の最小値が事前に分かっていれば、 $\mathrm{dp}_{i, 2}$ の計算時にはその値と $\mathrm{dp}_{i-1, 2}$ とを新たに比較すればよく、計算量を削減できるはずだ。

したがって、直前の行のDPテーブルに対して、あらかじめ後ろからの累積minを計算しておくことで、式 $(1)$ の第二項を $O(1)$ 時間で計算できるようになる。

具体的には、累積minテーブルを

\mathrm{ps}_{i-1, k} = \min(\mathrm{dp}_{i-1, k}, \mathrm{ps}_{i-1, k+1}) \quad (0 \leq k \leq N)

のように定義し、DPの漸化式を以下のように書き換える :

\mathrm{dp}_{i, k} = \mathrm{cost}(i, k) + \mathrm{ps}_{i-1, k} \tag{2}

これにより、 $\mathrm{cost}(i, k)$ の適切な実装によりDP遷移は $O(1)$ 時間となり、全体で $O(N^2)$ の計算量で解くことができるようになった。

$\mathrm{cost}(i, k)$ の計算

最後に、 $\mathrm{cost}(i, k)$ の計算方法について考える。

$i$ 行目を「左から $k$ 個を白、残りを黒」にするためには、

左側 $k$ 個のマスの中の黒マスを白に塗り替える。
右側 $N-k$ 個のマスの中の白マスを黒に塗り替える。

とすればよく、このときに塗り替えるマスの個数の和が $\mathrm{cost}(i, k)$ となる。

グリッドの各行について、黒マスの個数の累積和を前計算しておけば、この値は $O(1)$ で求められる。

具体的には、 $b_{i, x}$ を $i$ 行目の左から $x$ 個のマスの中の黒マスの個数とすると、

右側 $N-k$ 個にある黒マスの数: $b_{i, N} - b_{i, k}$
右側 $N-k$ 個にある白マスの数: $(N-k) - (b_{i, N} - b_{i, k})$

と表せるので、

\mathrm{cost}(i, k) = b_{i, k} + (N-k) - (b_{i, N} - b_{i, k})

と計算することができる。

実装例

実装では、式 $(2)$ による遷移でDPテーブルを参照していないことを利用して、in-place にDPテーブルを更新していく形にしている。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define all(x) (x).begin(), (x).end()
5.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
6.#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)
7. 
8.constexpr int INF = 1e+9;
9. 
10.// ======================================== //
11. 
12.int main()
13.{
14.    int N;
15.    cin >> N;
16.    vector<string> S(N);
17.    rep(i, 0, N) cin >> S[i];
18. 
19.    vector<int> dp(N + 1, 0);
20.    rep(i, 0, N)
21.    {
22.        vector<int> blacks(N + 1, 0);
23.        rep(j, 0, N) blacks[j + 1] = blacks[j] + (S[i][j] == '#');
24. 
25.        auto calc_cost = [&](int k) -> int
26.        {
27.            int to_white = blacks[k];
28.            int to_black = (N - blacks[N]) - (k - blacks[k]);
29.            return to_white + to_black;
30.        };
31. 
32.        vector<int> ps_min(N + 2, INF);
33.        rrep(k, N, 0) ps_min[k] = min(ps_min[k + 1], dp[k]);
34. 
35.        rep(k, 0, N + 1) dp[k] = calc_cost(k) + ps_min[k];
36.    }
37. 
38.    cout << *min_element(all(dp)) << endl;
39. 
40.    return 0;
41.}