ABC025 - 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;
}