[1]動的計画法の利用

隣り合う要素の差の絶対値が全て \(1\) である数列(長さ \(1\) も含む)を「素晴らしい整数列」と呼ぶこととします。

\(\mathrm{dp}[i][j][k]:=i\) 以下の値のみを使い「素晴らしい整数列」の列 \(C_1,C_2,\dots,C_j\) を作る方法の個数。ただし、以下の条件を全て満たす必要がある。

• $2 \le l \le j$ を満たす整数 $l$ に対し、$C_l$ の先頭は $i$ である。
• $1 \le l \le j-1$ を満たす整数 $l$ に対し、$C_l$ の末尾は $i$ である。
• $C_1$ の先頭、$C_j$ の末尾のうち、$k$ 個が $i-1$ 以下である。

上記の動的計画法を考えます。つまり、\(B\) から \(i\) 以下の値のみを取り出したときにあり得る列の列の個数です。例えば、\((2,3,2,1,2,3,4,3,4,3,2,3)\) という「素晴らしい整数列」は以下の \(4\) 箇所の \(\mathrm{dp}\) 配列を通ります。

• \((1)\) \((\mathrm{dp}[1][1][0])\)
• \((2),(2,1,2),(2)\) \((\mathrm{dp}[2][3][0])\)
• \((2,3,2,1,2,3),(3),(3,2,3)\) \((\mathrm{dp}[3][3][1])\)
• \((2,3,2,1,2,3,4,3,4,3,2,3)\) \((\mathrm{dp}[4][1][1])\)

挿入 dp のように考えることで、遷移を行うことができます。\(\mathrm{dp}[i][j][0],\mathrm{dp}[i][j][1],\mathrm{dp}[i][j][2]\) の結果を合算したものが \(\mathrm{dp}[i+1]\) となります。

\(\begin{cases} \mathrm{dp}[i+1][A_{i+1}-j][0] = \mathrm{dp}[i][j][0] \times \binom{A_{i+1}-1}{j} \\ \mathrm{dp}[i+1][A_{i+1}-j+1][1] = \mathrm{dp}[i][j][0] \times 2 \times \binom{A_{i+1}-1}{j-1} \\ \mathrm{dp}[i+1][A_{i+1}-j+2][2] = \mathrm{dp}[i][j][0] \times \binom{A_{i+1}-1}{j-2} \end{cases}\)

\(\begin{cases} \mathrm{dp}[i+1][A_{i+1}-j+1][1] = \mathrm{dp}[i][j][1] \times \binom{A_{i+1}-1}{j-1} \\ \mathrm{dp}[i+1][A_{i+1}-j+2][2] = \mathrm{dp}[i][j][1] \times \binom{A_{i+1}-1}{j-2} \end{cases}\)

\(\begin{cases} \mathrm{dp}[i+1][A_{i+1}-j+2][2] = \mathrm{dp}[i][j][2] \times \binom{A_{i+1}-1}{j-2} \end{cases}\)

---

[2]計算量

上記の動的計画法で、全ての \((i,j,k)\) を持ってしまうと計算量が \(\mathrm{O}(N \times \max A)\) となってしまいます。

\(\mathrm{dp}[i][j][k] \neq 0\) となる \((i,j,k)\) だけを持つことにより計算量を削減することを考えます。

\((i,k)\) を固定した場合の \(\mathrm{dp}[i][j][k] \neq 0\) となるような \(j\) の値について調べます。簡素化のため、\(X_i = A_i - A_{i-1} + A_{i-2} - A_{i-3} + \dots\) とします。

\(\begin{array}{c|ccccc} & 0 & 1 & 2\\ \hline 1 & X_1 & & \\ \hline 2 & X_2 & X_2+1 & X_2+2 \\ \hline 3 & X_3 & X_3,X_3+1 & X_3,X_3+1,X_3+2 \\ \hline 4 & X_4 & X_4,X_4+1 & X_4,X_4+1,X_4+2 \end{array}\)

上記からわかるように、\(\mathrm{dp}[i][j][k] \neq 0\) であるような \((i,j,k)\) の個数は \(\mathrm{O}(N)\) となります。

---

[3]まとめ

よって、この問題を \(\mathrm{O}(N + \max A)\) で解くことができます。

連想配列などを使うことにより、実装を簡潔にすることができます。