No.336

どの隣り合う3項も単調増加もしくは単調減少になっていなければいい. イメージ的にはギザギザになっているということである.

$1 \dots n$ の $n$ 個の数値からできる門松列列のうち, 最初の数値が $i$ で最初の2項が増加になっている組み合わせの数を $A(n, i)$, 最初の2項が減少になっている組み合わせの数を $B(n, i)$ とする.

このとき, $A(n, i)$ を考えると, 最初の数値が $i$ であり, 2項目には $i+1, i+2, \dots n$ が使える. 2項目以降を考えるときに1項目の数値は考慮にいれなくてもいいので, 2項目では $1 \dots n-1$ の $n-1$ 個の数値からなる門松列列を考えるようにすると, 2項目には $i, i+1, \dots n-1$ の数値が使えると考えることができる.

$B(n, i)$ も同様に考えると以下の漸化式になる.

$$A(n, i) = \sum_{j=i}^{n-1} B(n-1, j) \\ B(n, i) = \sum_{j=1}^{i-1} A(n-1, j)$$

サンプルから

$$A(3, 1) = 1 \\ A(3, 2) = 1 \\ A(3, 3) = 0 \\ B(3, 1) = 0 \\ B(3, 2) = 1 \\ B(3, 3) = 1$$

となる. これを素直に計算すると $O(N^3)$ となるが, 漸化式から

$$A(n, i) = A(n, i+1) + B(n-1, i) \\ B(n, i) = B(n, i-1) + A(n-1, i-1)$$

を導けるので, $O(N^2)$ で計算できる.