E - Don't Isolate Elements Editorial by cn449
操作は可換で、同一の \(i\) に対して操作を \(2\) 回行うと元の状態に戻るので、各 \(i\) に対して操作を行うのは高々 \(1\) 回としてよいです。
孤立した要素が存在しなくなるように、各 \(i\) に対して操作を行うかを \(i\) について昇順に考えていきましょう。
\(i\) 行目に対して操作を行うかどうかを確定したとき、 \(i-1\) 行目の要素についてそれらの要素が孤立した要素となるかが確定します。また、それより上の行については、\(1,2, \ldots, i-1\) 行目に対する操作は孤立した要素が存在しないように行われていることから孤立した要素は存在しません。
また、\(i-1\) 行目の要素が孤立した要素となるかは \(i-2,i-1,i\) 行目の要素にしか依存しません。
ここで、\(dp_{i,j,k}\) を \(i\) 行目までについて操作を行うかを確定して、\(j\) を \(i-1\) 行目に対して操作を行ったか、\(k\) を \(i\) 行目に対して操作を行ったかを表す flag としたときに \(i-1\) 行目までに孤立した要素が存在しなくなるという条件を満たすために必要な操作回数の最小値とします。
すると、上に述べたことからこの設定による動的計画法で本問題を解くことができますが、\(H\) 行目の要素が孤立した要素とならないよう \(dp_{i,j,k}\) において \(i = H\) のときは \(i\) 行目についても孤立した要素が存在しないようにする、あるいは答えを求める際に適切な \((j,k)\) の組に対してのみ \(dp_{H,j,k}\) の 最小値を取るなどの工夫が必要です。
この動的計画法は状態数が \(O(H)\)、遷移が \(O(W)\) の計算量で行えるので本問題を \(O(HW)\) の計算量で解くことができました。
実装例
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
constexpr int inf = 1000000010;
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }
int main() {
int h, w;
cin >> h >> w;
vector<vector<int>> a(h, vector<int>(w));
rep(i, h) rep(j, w) cin >> a[i][j];
vector<vector<vector<int>>> dp(h, vector<vector<int>>(2, vector<int>(2, inf)));
dp[0][0][0] = 0;
dp[0][0][1] = 1;
for (int i = 1; i < h; i++) {
rep(j, 2) {
rep(k, 2) {
rep(l, 2) {
vector<int> x(w, -1);
if (i != 1) x = a[i - 2];
if (j) rep(m, w) x[m] = 1 - x[m];
vector<int> y = a[i - 1];
if (k) rep(m, w) y[m] = 1 - y[m];
vector<int> z = a[i];
if (l) rep(m, w) z[m] = 1 - z[m];
bool ok = true;
rep(m, w) if (x[m] != y[m] && y[m] != z[m] && (m == 0 || y[m] != y[m - 1]) && (m == w - 1 || y[m] != y[m + 1])) ok = false;
if (i == h - 1) {
rep(m, w) if (z[m] != y[m] && (m == 0 || z[m] != z[m - 1]) && (m == w - 1 || z[m] != z[m + 1])) ok = false;
}
if (ok) chmin(dp[i][k][l], dp[i - 1][j][k] + l);
}
}
}
}
int ans = inf;
rep(j, 2) rep(k, 2) chmin(ans, dp[h - 1][j][k]);
cout << (ans == inf ? -1 : ans) << '\n';
}
posted:
last update: