AtCoder Beginner Contest 295 Ex - E or m

E or m よりは、三 or 川 という感じがする

問題へのリンク

問題

各マスが白、黒、灰色に塗られた $ N \times M $ のグリッドが与えられる。 各灰マスを白か黒に塗り替えてできるグリッドのうち、以下のようにして生成できるものはいくつあるか？

• グリッドの全てのマスを白で初期化する。
• 各 $ i = 1, \dots, N $ に対して、$ i $ 行目のマスのうち左からいくつかを黒に塗る。
• 各 $ j = 1, \dots, M $ に対して、$ j $ 列目のマスのうち上からいくつかを黒に塗る。

制約

• $ 1 \leq N, M \leq 18 $

前提

とくになし

解法

まずは生成可能な塗り方を観察してみる。

OK            NG
1010  1111    0100  0111
1111  1001    1110  1111
1110  1110    0110  0011
0010  1000    0001  0010

すると、ある塗り方が生成可能であることの必要十分条件は

「全ての黒マスについて、そのマスの上全部か左全部が黒で塗られている」

ことだと分かる。

よって、

$ \mathrm{dp}(i, j, f, S) := ($マス $ (i, j) $ まで塗って、左を全て黒で塗っているか否かが $f$ で、上を全て塗っているマスの集合が $S$ であるような塗り方の数$)$

として DP すればよい。時間計算量は $ O(NM2 ^ M) $。

コード

https://atcoder.jp/contests/abc295/submissions/40530818

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    char c[n][m];
    rep(i, n) rep(j, m) scanf(" %c", &c[i][j]);
 
    vector<vector<vector<mint>>> dp(
        m + 1, vector<vector<mint>>(2, vector<mint>(1 << m, 0)));
    dp[m][1][(1 << m) - 1] = 1;
    rep(i, n) {
        // init
        vector<vector<vector<mint>>> nxt(
            m + 1, vector<vector<mint>>(2, vector<mint>(1 << m, 0)));
        rep(f, 2) rep(S, 1 << m) { nxt[0][1][S] += dp[m][f][S]; }
        dp.swap(nxt);
 
        // dp
        rep(j, m) rep(f, 2) rep(S, 1 << m) {
            if (dp[j][f][S] == 0) continue;
 
            rep(col, 2) {
                if (c[i][j] != '?' && col != c[i][j] - '0') continue;
                if (col == 1 && !f && !(S >> j & 1)) {
                    continue;
                }
 
                int nf = f & col;
                int T = S;
                if (col == 0 && (S >> j & 1)) {
                    T -= (1 << j);
                }
                dp[j + 1][nf][T] += dp[j][f][S];
            }
        }
    }
 
    mint ans = 0;
    rep(f, 2) rep(S, 1 << m) ans += dp[m][f][S];
    printf("%u\n", ans.val());
}

関連