[典型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;
}

https://atcoder.jp/contests/typical90/submissions/28353319