ABC025 - D 25個の整数

解説

D - 25個の整数

解説を見て実装を放置していたため、考察要素はないです。

問題概要

5 * 5 のマスがあります。 1 ~ 25 までの数値を、各マスに一つずつ書きます。ただし、以下の条件を満たすように書かなければいけません。

縦、あるいは横に 3 つ並んだどのマスの数値も、単調減少、あるいは単調増加してはいけない。

あらかじめいくつかのマスはすでに数値が書かれています。
条件に従い全ての全てのマスを埋めるとき、何通りの埋め方がありますか。

考えたこと

制約は N ≤ 20 だけど、2^25のdpテーブル持ちたい…

2^25のdpテーブルをギリギリ持てた。

マスに何も書かれていない状態から考える。

dfsで 1 から順番に書いていき、全部埋められたら 1 を返す。また、メモ化して無駄な部分を減らす。

元々数値が書いてあるということは、数値が書ける場所が 1 箇所しかないと考えられる。

bit と 2 次元の盤面を行き来する必要がある。

(x, y)は、bit の (x + y * 5) 番目と考えればよい。

実装

check関数で書けるかどうかの判定をしています。 atcoder公式の解説にある通り、数値を書く時のマスの状況が 4 種類に分けられます。

端のマスに書き込む。
書き込むマスの両側がすでに書き込まれている。
書き込むマスの片方がすでに書き込まれている。
書き込むマスの両方が書き込まれていない。

そして、書き込めないパターンは 3 番のみです。書き込むマスの前後の bit の xor を取り、反転させれば条件を満たすかを判定できます。それを縦横両方確かめ、and を取れば、書き込めるかわかります。

1 から順番に埋めていくため、実際に値の大小を比べる必要はありません。

dfs関数では、 num を書き込むマスを全通り試しています。書き込める場所は、 "入力で 0 が与えられている" かつ "集合 s に含まれていない" 場所です。 1 から順番に書き込んでいくとはいえ、元々書き込まれている部分に書き込むことはできません。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

const int M = 1000000007;

int dp[1 << 25];
vector<bool> used_number(25,0);
vector<bool> vacant_space(25,0);
pair<int, int> p[25];

bool getBit(int num, int i){
    return ((num & (1 << i)) != 0);
}

int setBit(int num, int i){
    return num | (1 << i);
}

bool check(pair<int, int> p, int s){
    int y = p.first;
    int x = p.second;

    bool xf, yf;
    if(x == 0 || x == 4){ //端に置くケース
        xf = true;
    }else{
        bool left_bit = getBit(s, (x - 1) + y * 5);
        bool right_bit = getBit(s, (x + 1) + y * 5);
        xf = not (left_bit xor right_bit);
    }

    if(y == 0 || y == 4){
        yf = true;
    }else{
        bool up_bit = getBit(s, x + (y - 1) * 5);
        bool down_bit = getBit(s, x + (y + 1) * 5);
        yf = not (up_bit xor down_bit);
    }

    return xf and yf;
}


int dfs(int s, int num){ //s = 埋められた場所の集合
    if(dp[s] != -1) return dp[s];

    if(used_number[num]){ //あらかじめ数字が置かれている場合
        int y = p[num].first;
        int x = p[num].second;
        int next = setBit(s, x + y * 5);

        if(check(p[num],s)){
            return dfs(next, num + 1);
        }else{
            return dp[next] = 0;
        }
    }

    int res = 0;
    rep(i,25){ // num を置ける場所を探す
        if(not getBit(s,i) && vacant_space[i]){
            if(check(make_pair(i / 5, i % 5), s)){
                res += dfs(setBit(s,i), num + 1);
                res %= M;
            }
        }
    }

    return dp[s] = res;
}

signed main(){
    memset(dp, -1, sizeof(dp));
    dp[(1 << 25) - 1] = 1; //全部埋まったら1通り

    rep(i,5) rep(j,5){
        int a;
        cin >> a;
        if(a == 0) vacant_space[i * 5 + j] = true;
        else used_number[a - 1] = true;
        p[a - 1] = make_pair(i,j);
    }

    cout << dfs(0,0) << endl;
}