[典型90] 023 - Avoid War（★7）
Q. https://atcoder.jp/contests/typical90/tasks/typical90_w
解説は、
O(24*24*2^18)ですごい。効率化部分がわからず、俺のは
O(24*24*2^20)でギリギリ。7950ms/8000msでした。
解説3/4P の bitDP に従って解きます
https://github.com/E869120/kyopro_educational_90/blob/main/editorial/023-03.jpg
bitDPは、
1. 初期入れ
2. 配るDP
- bitずらし
- 遷移できるかどうかの判定
3. 解答はどれか
をどうしようという感じ。
Q. H=3 W=4
(0-indexed)
0123
4567
8901
W=4なので、W+1=5bitの状態遷移で、状況を整理できます。
DP[5]を決めるのは、0~4 の 5bit 情報。
DP[6]を決めるのは、1~5 の 5bit 情報。
DP[7]を決めるのは、2~6 の 5bit 情報。
DP[8]を決めるのは、3~7 の 5bit 情報。(ここだけ、4~7の4bitだけが実際に使用する情報）
1. DPの初期入れ。
DP[0]の状態だけベタに記述します。
1.) DP[0][00000] = 1 は確定。
2.) DP[0] == '.' なら、DP[0][00001] = 1 も加わります。
2. 配るDP
0~3index はイメージしにくいので、 4~7index について考える。
DP[4]の処理は、次のような状態遷移ができればいい。
01234 12345
DP[4][00000]=1 -> DP[5][00000] = 1
-> DP[5][00001] = 1
DP[4][00001]=1 -> DP[5][00010] = 1
-> DP[5][00011] = 0 // NG
やっていることは、
01234
1.) DP[4]のbit 00001 を選択して、
12345
2.) 1bit左にずらし、bit 0001X とする。
これで、1234のindex情報とみなせる。
3.) index5 には、0 (空きマスにする) は必ず入れられるので、遷移を確定させていい。
DP[5][00010] = 1
4.) 問題は、5のindexに1(使用マス) がいれられるかどうかを考える。
DP[5][00011] = 0 // NG
0123
4567
8
index5 に1を入れるとすると、0124はすべて0でなければならない。けど、4が1になっているためNG
3. indexごとの判定
これは3パターンに分けられる。
配るDPで処理するので、
DP[4]のとき、5に着目すると、0124がすべて0であれば、5==1が入れられる。
DP[5]のとき、6に着目すると、1235がすべて0であれば、6==1が入れられる。
DP[6]のとき、7に着目すると、236がすべて0であれば、7==1が入れられる。
DP[7]のとき、8に着目すると、45がすべて0であれば、8==1が入れられる。
これを一般化すると、
1.) 5-6 に着目するとき、4つ{ 1<<W, 1<<(W-1), 1<<(W-2), 1<<0 } が0であればいい。
2.) 7 に着目するとき、3つ{ 1<<W, 1<<(W-1), 1<<0 } が0であればいい。
3.) 8 に着目するとき、2つ{ 1<<(W-1), 1<<(W-2) } が0であればいい。
とわかる。
4. 解答
DP[11][00000] ~ DP[11][11111] までの総和。
~~~~~ ~~~~~ 2^25??Q. 2^25 = 1000*1000*32 は探索できる？
A. できない。解答だと2^18まで減らせているけど、わからなかった。
2^20への短縮方法を紹介。
0123
4567
bitを考えるときに、01100 のように、「11」が連番であったら、キングが配置できないかと思いきや
[01234]
00011 これは、
0001
1 折り返し地点で連番判定になっているので、問題なかったりする。
なので、条件を少し緩めて
0111000, 0110110など、
「11」の連番が2つ以上あったらNGとすれば、
2^25の場合を減らすと 1020218 ≒ 2^20(1048576)
まで落ちます。
・実装
ll H, W;
char C[25][25];
mint DP[25][1 << 20]; // W=24 vsz:1020218
vector<ll> initfib() {
// 111が1つ以上、もしくは11が2つ以上はだめ
vector<ll> fib;
fib.reserve(1 << 20);
ll cnt = 0;
rep(i, (1 << (W + 1))) {
cnt = 0;
rep(j, W) {
if (is_pop(i, j) && is_pop(i, j + 1)) {
++cnt;
if (cnt > 1) break;
}
}
if (cnt > 1) continue;
fib.push_back(i);
}
return fib;
}
/*
0123
4567
8901
45のときは 末端3つと、0を見る
6のときは末端2つと、0を見る
7のときは、末端から2,3だけ見る。
*/
bool check(ll k, ll j) {
bool ok = true;
if (j < W - 2) {
rep(i, 3) if (is_pop(k, W - i)) ok = false;
if (is_pop(k, 0)) ok = false;
} else if (j == W - 2) {
rep(i, 2) if (is_pop(k, W - i)) ok = false;
if (is_pop(k, 0)) ok = false;
} else if (j == W - 1) {
rep(i, 2) if (is_pop(k, W - 1 - i)) ok = false;
}
return ok;
}
void debug() {
rep(w, W) {
rep(i, (1 << (W + 1))) {
if (DP[w][i] > 0) {
cout << "DP[" << w << "][" << bitset<5>(i) << "]:" << DP[w][i] << endl;
}
}
}
}
int main() {
cincout();
cin >> H >> W;
rep(i, H) rep(j, W) cin >> C[i][j];
// 初期入れ
DP[0][0] = 1;
if (C[0][0] == '.') DP[0][1] = 1;
//数を知りたい。
vector<ll> fib = initfib();
ll vsz = fib.size();
//配るDP
/*
0123
4567
8901
初期
DP[0][00000]=1 ->1
DP[0][00001]=1 ->ここから1派生はしない。
配るDP。[0][00000]->[1][00000]に入れる。
DP[1][00000]=1 //000000 から、1個ずらしたもの
DP[1][00001]=1 //000001 から、1個ずらしたもの
DP[1][00010]=1 //000010 から、1個ずらしたもの
*/
rep(i, H) rep(j, W) {
// 配る先を初期化
mint nDP[1 << 20]{};
if (i == H - 1 && j == W - 1) break; //おしまい
// 配る先
ll ni = i + (j + 1) / W;
ll nj = (j + 1) % W;
rep(v, vsz) {
ll k = fib[v];
if (DP[j][v] == 0) continue;
// kを1個左にずらして、0付与。
ll nk = (k << 1) & ((1 << (W + 1)) - 1); // 減る場合も当然ある
auto it = lower_bound(all(fib), nk);
assert(*it == nk);
ll nv = it - fib.begin();
nDP[nv] += DP[j][v];
// 1を付与できるならする
if (C[ni][nj] == '#') continue;
if (check(k, j) == false) continue;
assert(fib[nv] + 1 == fib[nv + 1]);
nDP[nv + 1] += DP[j][v];
}
swap(nDP, DP[nj]);
}
mint ans = 0;
rep(v, vsz) { ans += DP[W - 1][v]; }
// debug();
cout << ans << endl;
}ここから先は
1字
¥ 100
この記事が気に入ったらサポートをしてみませんか？