マス目の穴埋め [第四回 アルゴリズム実技検定 N]

https://atcoder.jp/contests/past202010-open/tasks/past202010_n

前提知識

• bitDP

解説

https://atcoder.jp/contests/past202010-open/submissions/21474259

横幅が制限されているのでbitDPで解ける。

bitDP

以下のようなbitDPを作ろう。

dp[y][msk1][msk2] := y行目まで確定していて、y-1行目がmsk1で、y行目がmsk2であるような有効な書き換え方の組み合わせ

基本的には埋め方を全通り試してみて、条件に合うものがあれば採用していく方針を取っていく。
条件の判定を適切にモジュール化しながら実装していけば、メイン処理自体はそれほど難しい形にはならない。
遷移としては、
dp[y][msk1][msk2]からdp[y+1][msk2][msk3]のように遷移させてmsk3を全探索していけばいい。

実装について

自分の実装では主に2つの関数を作成して解いている。
どちらも念のためメモ化を行っている。

canPlace(line, msk) := line行目にmskの状態が置けるか

?ならなんでも置いてもいいが、そうでない場合は矛盾したものは置けないのでその辺を判定

checkMedian(int msk1, int msk2, int msk3) := 1行目がmsk1, 2行目がmsk2, 3行目がmsk3であるときに2行目が中央値的に問題ないか判定

端の判定ではmsk1=0としてやればいいので、これだけ作れば判定はすべて行える。

string S[18];
ll dp[19][1 << 6][1 << 6];
int dx[5] = { 0, 1, 0, -1, 0 }, dy[5] = { -1, 0, 1, 0, 0 };
//---------------------------------------------------------------------------------------------------
string toStringBinary(int msk) {
    string res;
    rep(i, 0, 6) res += char('0' + (((1 << i) & msk) != 0));
    return res;
}
//---------------------------------------------------------------------------------------------------
bool memo1[18][1 << 6];
bool cache1[18][1 << 6];
bool canPlace(int line, int msk) {
    if (memo1[line][msk]) return cache1[line][msk];
    memo1[line][msk] = true;

    string mskstr = toStringBinary(msk);
    rep(x, 0, 6) {
        if (S[line][x] == '?') continue;
        if (S[line][x] != mskstr[x]) return cache1[line][msk] = false;
    }
    return cache1[line][msk] = true;
}
//---------------------------------------------------------------------------------------------------
bool memo2[1 << 6][1 << 6][1 << 6];
bool cache2[1 << 6][1 << 6][1 << 6];
bool checkMedian(int msk1, int msk2, int msk3) {
    if (memo2[msk1][msk2][msk3]) return cache2[msk1][msk2][msk3];
    memo2[msk1][msk2][msk3] = true;

    vector<string> mskstrs = { toStringBinary(msk1), toStringBinary(msk2), toStringBinary(msk3) };

    rep(x, 0, 6) {
        int zero = 0, one = 0;
        rep(d, 0, 5) {
            int xx = x + dx[d];
            int yy = 1 + dy[d];
            if (xx < 0 || 6 <= xx) {
                zero++;
                continue;
            }
            if (mskstrs[yy][xx] == '0') zero++;
            else one++;
        }

        if (zero < one && mskstrs[1][x] == '0') return cache2[msk1][msk2][msk3] = false;
        if (zero > one && mskstrs[1][x] == '1') return cache2[msk1][msk2][msk3] = false;
    }
    return cache2[msk1][msk2][msk3] = true;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    rep(i, 0, 18) cin >> S[i];

    // 初期状態の作成
    rep(i, 0, 19) rep(msk1, 0, 1 << 6) rep(msk2, 0, 1 << 6) dp[i][msk1][msk2] = 0;
    rep(msk1, 0, 1 << 6) if (canPlace(0, msk1))
        rep(msk2, 0, 1 << 6) if (canPlace(1, msk2))
            if (checkMedian(0, msk1, msk2)) dp[2][msk1][msk2] = 1;
    
    rep(i, 2, 18) rep(msk1, 0, 1 << 6) rep(msk2, 0, 1 << 6) if (0 < dp[i][msk1][msk2]) {
        rep(msk3, 0, 1 << 6) if (canPlace(i, msk3) && checkMedian(msk1, msk2, msk3)) dp[i + 1][msk2][msk3] += dp[i][msk1][msk2];
    }

    ll ans = 0;
    rep(msk1, 0, 1 << 6) rep(msk2, 0, 1 << 6) if (checkMedian(msk1, msk2, 0)) ans += dp[18][msk1][msk2];
    cout << ans << endl;
}