AtCoder Beginner Contest 296 Ex - Unite

グリッドマンユニバースを見に行かないといけない

問題へのリンク

問題

白黒で塗られた $ N \times M $ のグリッドがある。 黒マス全体を連結にするために、追加で黒に塗るべきマスは最小でいくつ？

制約

  • $ 1 \leq N \leq 100 $
  • $ 1 \leq M \leq 7 $ ← 小さい！

前提

とくになし

解法

「連結性 DP」「面倒 DP」などと呼ばれているやつ。

$ \mathrm{dp}(i, S) := ( $$ i $ 行目まで決めて、連結性が $ S $ であるときに塗るべきマスの個数の最小値$)$

のようにして DP する。遷移を計算する際には $ i $ 行目の白黒のパターン $ 2 ^ M $ 通りを全探索する。

連結性について詳しく説明する。

連結性を数列で表現する様子

例えば、上の図において左の二つの塗り方は同じ状態に圧縮できる。一番下の行はどちらも 黒白黒黒白黒白 であり、$ 1 $ 列目と $ 6 $ 列目、$ 3 $ 列目と $ 4 $ 列目の黒マスがそれぞれ連結になっている。よって、白マスには $ 0 $、黒マスには左から順に連結成分番号を振っていくことにすると、二つの塗り方はいずれも $ (1, 0, 2, 2, 0, 1, 0) $ という数列で表現できる。

実装が大変そうだが、私はいつも $ i - 1 $ 行目と $ i $ 行目を合わせた $ 2M $ 頂点のグラフに対する Union-Find 木を用意し、

  1. $ i - 1 $ 行目において、連結成分番号が同じ黒マスをマージ
  2. $ i $ 行目の各黒マスと隣接する黒マスをマージ
  3. 長さ $ M $ の配列 $ a $ を用意し、$ a _ j $ には $ (i, j) $ が白なら $ 0 $、黒なら $ (i, j) $ が属する集合の代表元 $ + 1 $ を入れる
  4. map などを持ちながら $ a $ を順番に舐めて、連結成分番号を $ 1 $ から振り直す

のようにしている。

また、今回は $ i , S $ に加えて、これ以上黒マスが登場しないかを状態として持つ（耳 DP）。

状態を $8$ 進数で表現して int 型に詰め込むと高速化できる。$ 2 ^ k $ 進数にすると、値をビット演算で取り出せるので都合が良い。

コード

遷移を計算する部分で $ N $ と $ M $ を取り違えないように、$ N $ は main 内、$ M $ はグローバルで宣言している。

https://atcoder.jp/contests/abc296/submissions/40333675

int m;
 
int next_phase(vector<int> &v, int phase, int S) {
    if (phase == 0) {
        return (S == 0 ? 0 : 1);
    } else if (phase == 1) {
        return (S == 0 ? 2 : 1);
    } else {
        return (S == 0 ? 2 : -1);
    }
}
 
optional<pair<vector<int>, int>> next_state(pair<vector<int>, int> state,
                                            int S) {
    auto [v, phase] = state;
    auto np = next_phase(v, phase, S);
    if (np == -1) return nullopt;
    if (S == 0) {
        if (*max_element(v.begin(), v.end()) >= 2) {
            return nullopt;
        } else {
            vector<int> res(m, 0);
            return make_pair(res, np);
        }
    }
 
    atcoder::dsu uf(m * 2);
    rep(i, m) For(j, i + 1, m) {
        if (v[i] != 0 && v[i] == v[j]) uf.merge(i, j);
    }
    rep(i, m) {
        if (!(S >> i & 1)) continue;
        if (i + 1 < m && (S >> (i + 1) & 1)) {
            uf.merge(i + m, i + 1 + m);
        }
        if (v[i] != 0) {
            uf.merge(i, i + m);
        }
    }
    rep(i, m) {
        if (v[i] == 0) continue;
        bool flag = false;
        rep(j, m) {
            if (uf.same(i, j + m)) {
                flag = true;
                break;
            }
        }
        if (!flag) return nullopt;
    }
 
    vector<int> nv(m, 0);
    rep(i, m) {
        if (!(S >> i & 1)) continue;
        nv[i] = uf.leader(i + m) + 1;
    }
    map<int, int> mp;
    int cur = 1;
    rep(i, m) {
        if (nv[i] == 0) continue;
        if (mp.find(nv[i]) == mp.end()) {
            mp[nv[i]] = cur;
            ++cur;
        }
        nv[i] = mp[nv[i]];
    }
    return make_pair(nv, np);
}
 
int main() {
    int n;
    scanf("%d%d", &n, &m);
    int mask[n];
    int offset = 0;
    rep(i, n) {
        string s;
        cin >> s;
        mask[i] = 0;
        rep(j, m) if (s[j] == '#') mask[i] += (1 << j), ++offset;
    }
 
    map<pair<vector<int>, int>, int> dp;  // (state, phase) -> num
    {
        vector<int> init(m, 0);
        dp[{init, 0}] = 0;
    }
    rep(i, n) {
        map<pair<vector<int>, int>, int> nxt;
 
        rep(S, 1 << m) {
            if ((S & mask[i]) != mask[i]) continue;
 
            for (auto [state, val] : dp) {
                auto ns = next_state(state, S);
                if (!ns) continue;
 
                int tmp = val + __builtin_popcount(S);
                if (nxt.find(ns.value()) == nxt.end()) {
                    nxt[ns.value()] = tmp;
                } else {
                    chmin(nxt[ns.value()], tmp);
                }
            }
        }
 
        dp.swap(nxt);
    }
 
    int ans = n * m;
    for (auto [state, val] : dp) {
        auto [v, phase] = state;
        if (*max_element(v.begin(), v.end()) <= 1) {
            chmin(ans, val - offset);
        }
    }
    printf("%d\n", ans);
}

関連