[ARC132] C - Almost Sorted

[Q] https://atcoder.jp/contests/arc132/submissions/28201565

1. d=5が、とても厳しい制限。けど何に使うんだろう？
2. indexごとに状態遷移するからDPっぽい。どの数値を使ったか保持しておきたいと思う。
3. DP[510][2^500] は無理。
4. d=5だとして、a-5 ~ a+5の11通りの数字しかとりえないのがわかる。DP[510][2^11]で求められそう。
5. indexを動かすごとに、右に1bitずらせばよさそう。

Q. 

D=2
-1 -1 -1 -1 
とする。

0. bit管理
D=2なので、どの値も5個の範囲をとる。
DP[5][2^5] で管理。

1. 初期条件
DP[0][00011] = 1をとる。
入力値を0-indexedとみなして、


bit:0 0 0 1 1
    2 1 0-1-2 が入るかどうかを表している。
-1, -2 は入りえないので、すでに使用済み扱い。1を立てている。

2. DP遷移
・-1(0index)の処理

まず、現状から1つbitを追加できる場合に遷移する。
DP[0][00011] = 1 -> DP[0][00111] = 1 // 0を採用する
                 -> DP[0][01011] = 1 // 1を採用する
                 -> DP[0][10011] = 1 // 2を採用する
                          210-1-2 // この5bitが管理しているのは2 ~ -2

次に、bitを1つ右にずらして、確定させる
DP[0][00111] = 1 -> DP[1][00011] = 1
DP[0][01011] = 1 -> DP[1][00101] = 1
DP[0][10011] = 1 -> DP[1][01001] = 1
                          3210-1 // この5bitが管理しているのは3 ~ -1

3. 終了条件。
DP[4][00011] = 14 が回答になる。

// 初期条件
DP[0][00011]:1

// 新たにbitを1本追加して、右に1bitシフト
DP[1][00011]:1
DP[1][00101]:1
DP[1][01001]:1

// 新たにbitを1本追加して、右に1bitシフト
DP[2][00011]:2
DP[2][00101]:2
DP[2][00110]:2
DP[2][01001]:1
DP[2][01010]:1
DP[2][01100]:1

// 新たにbitを1本追加して、右に1bitシフト
DP[3][00011]:6
DP[3][00101]:4
DP[3][00110]:4
DP[3][00111]:4
DP[3][01001]:2
DP[3][01010]:2
DP[3][01011]:2
DP[3][01100]:1
DP[3][01101]:1
DP[3][01110]:1

// 新たにbitを1本追加して、右に1bitシフト
DP[4][00011]:14 << ans
DP[4][00101]:10
DP[4][00110]:7
DP[4][00111]:15
DP[4][01001]:6
DP[4][01010]:4
DP[4][01011]:8
DP[4][01100]:2
DP[4][01101]:4
DP[4][01110]:2
DP[4][01111]:1
14

実装

ll N, D;
mint DP[510][1 << 11];
ll A[510];

int main() {
 cincout();

 cin >> N >> D;
 rep(i, N) {
   cin >> A[i];
   --A[i];
 }

 DP[0][(1 << D) - 1] = 1;  // 00011
 rep(i, N) {
   ll a = A[i];
   if (a != -2) { // 定数が来て、それが条件を外れてるならダメ
     if (a > i + D || a < i - D) {
       cout << 0 << endl;
       return 0;
     }
   }

   rep(j, 1 << (D * 2 + 1)) {
     if (DP[i][j] == 0) continue;
     if (a != -2) {
       ll shift = a - i + D;
       if (is_pop(j, shift)) continue;
       ll nj = j | (1 << shift);
       nj >>= 1;
       DP[i + 1][nj] += DP[i][j];
     }
     // 00011->00111にしたい
     else {
       rep(x, D * 2 + 1) {
         if (is_pop(j, x)) continue;
         ll nj = j | (1 << x);
         nj >>= 1;
         DP[i + 1][nj] += DP[i][j];
       }
     }
   }
 }
 cout << DP[N][(1 << D) - 1] << endl;
}

https://atcoder.jp/contests/arc132/submissions/28201857