AtCoder Beginner Contest 025 D - 25個の整数

問題

abc025.contest.atcoder.jp

解法

1 から順番に数を入れていくことを考えます。この時, ある数 a を入れる場所に応じて場合分けをしてみます。上下に対しても同じようにできるので, 左右についてのみ考えます。

• a が端っこにある時 … a がなんであろうとそれ以前のおき方が valid であるならば, a を端っこに置くことも valid です。
• a の両端 2 つの数が確定している時 … (小)(大)(小) という形になることが確定するので, それ以前のおき方が valid なら a を置くことも valid です。
• a の両端のうち, 片方の数だけが確定している時 … (大)(中)(小) または (小)(中)(大) となることが確定します。これは条件に反するので NG です。

で, このように数を置いていくと,

• valid でないケースは NG になる場合を必ずチェックされるので, 数えられることはない
• valid なケースは, 上の条件をすべて満たすので, 必ず数えられる

ので, ちゃんと場合の数を数えてくれることになります。

このように 1 から順番に数を入れていくのは, 「既にどの場所に数を置いたか」ということしか関係ないので, bitDP で処理できます。下のコードでは以下のようにしました。

1 から順番に盤面に数を入れていく。このとき,

• 盤面に入れようとしている数が入力で既に与えられている数の場合, その場所に数を入れても矛盾しないかをチェックするだけ
• 入力で与えられていない数の場合, 入れることの出来る場所をすべて試し, チェックする

const int MOD = 1e9+7;
int board[5][5], memo[5][5];
// 確定している数の場所
pii pos[26];
// state の各フラグに対応する場所
pii assign[25];
bool exist[26];

// state という状態に xy を突っ込んでも大丈夫か
bool check(int state, int xy, int now, int k) {
    memset(memo, 0, sizeof(memo));
    // state から
    for (int i = 0; i < k; i++) {
        if ((state>>i)&1) {
            int y = assign[i].first, x = assign[i].second;
            memo[y][x] = 1;
        }
    }
    // exist から
    for (int i = 1; i < now; i++) if (exist[i]) {
        int y = pos[i].first, x = pos[i].second;
        memo[y][x] = 1;
    }
    // で, 入れてみる
    int y = xy/5, x = xy%5;
    if (memo[y][x]) return false;
    // y
    {
        int cnt = 0;
        for (int i = -1; i <= 1; i++) {
            int ny = y+i;
            if (ny < 0 || ny >= 5) {
                cnt = 10;
                continue;
            }
            if (memo[ny][x]) cnt++;
        }
        if (cnt == 1) return false;
    }
    // x
    {
        int cnt = 0;
        for (int i = -1; i <= 1; i++) {
            int nx = x+i;
            if (nx < 0 || nx >= 5) {
                cnt = 10;
                continue;
            }
            if (memo[y][nx]) cnt++;
        }
        if (cnt == 1) return false;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 1; i <= 25; i++) pos[i].first = -1;
    for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) {
        cin >> board[i][j];
        pos[board[i][j]] = pii(i, j);
        exist[board[i][j]] = true;
    }
    int k = 0;
    for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) {
        if (board[i][j] == 0) assign[k++] = pii(i, j);
    }
    vector<int> dp(1<<k);
    dp[0] = 1;
    for (int i = 1; i <= 25; i++) {
        vector<int> _dp(1<<k);
        for (int s = 0; s < 1<<k; s++) {
            if (!dp[s]) continue;
            if (exist[i]) {
                int xy = pos[i].first*5 + pos[i].second;
                if (check(s, xy, i, k)) (_dp[s] += dp[s]) %= MOD;
            } else {
                for (int j = 0; j < k; j++) {
                    if ((s>>j)&1) continue;
                    int xy = assign[j].first*5+assign[j].second;
                    if (check(s, xy, i, k)) (_dp[s|1<<j] += dp[s]) %= MOD;
                }
            }
        }
        dp = _dp;
    }
    cout << dp[(1<<k)-1] << endl;
    return 0;
}