ABC025D - 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 種類に分けられます。
1. 端のマスに書き込む。
2. 書き込むマスの両側がすでに書き込まれている。
3. 書き込むマスの片方がすでに書き込まれている。
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;
}