問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$(1,2, \dots, N)$ の順列の組 $(A,B)$ のうち, 以下で定義される類似度が $K$ であるような組の数 (を $P$ で割った余り) を求めよ.

$i=1,2, \dots, N-1$ において, $(A_{i+1}-A_i)(B_{i+1}-B_i) \gt 0$ となる整数 $i$ の個数

制約

$1 \leq N \leq 100$
$0 \leq K \leq N-1$
$10^8 \leq P \leq 10^9$
$P$ は素数

解法

動的計画法で解く. $1 \leq i \leq N, 0 \leq k \leq K, 0 \leq s,t \leq N-i$ に対して, ${\rm DP}[i,k,s,t$ ] を以下で定義する.

$A,B$ の第 $i$ 項まで見たとき, $1$ 以上 $N$ 以下の整数で $A_1, \dots, A_i$ に登場せず, $A_i$ 未満の整数が $s$ 個, $1$ 以上 $N$ 以下の整数で $B_1, \dots, B_i$ に登場せず, $B_i$ 未満の整数が $t$ 個であるような組の個数

ベースケースは $i=1$ のときで, この時点での類似度は $0$ であり, また, $A_1, B_1$ としては $1$ 以上 $N$ 以下の整数をそれぞれ任意に指定できるので,

${\rm DP}[i,k,s,t]=\begin{cases} 1 & (k=0) \\ 0 & (k \neq 0) \end{cases}$

である.

更新式を考える. そもそも, $(A_{i+1}-A_i)(B_{i+1}-B_i) \gt 0$ であるための必要十分条件は, $A_i$ と $A_{i+1}$ , $B_i$ と $B_{i+1}$ の大小関係が一致していることである *1.

$A$ について着目する. $(i-1,s')$ から $(i, s')$ になったとき,

$s' \leq s$ ならば, $A_i \lt A_{i+1}$
$s' \gt s$ ならば, $A_i \gt A_{i+1}$

である. これにより, $s',s$ と $A_i, A_{i+1}$ の大小関係の関係性がわかった. 同様にして, $t',t$ と $B_i, B_{i+1}$ の大小関係の関係も分かる.

よって, 更新式は

$\displaystyle {\rm DP}[i,k,s,t]=\sum_{\substack{s' \leq s , t' \gt t \\ {\rm or} \\ s' \gt s , t' \leq t}} {\rm DP}[i-1,k-1,s',t']+\sum_{\substack{s' \leq s , t' \leq t \\ {\rm or} \\ s' \gt s , t' \gt t}} {\rm DP}[i-1,k-1,s',t']$

となる.

そして, 最終解答は ${\rm DP}[N,K,0,0$ ] である.

このとき, 要素数が $O(N^4)$ 個, 遷移が各要素について $O(N^2)$ 時間かかり, 全体で $O(N^6)$ 時間かかってしまい, 間に合わない.

しかし, 各シグマの取る範囲に着目してみると, $s,t$ に関するある区間の直積 (の直和) になっていることに着目すると, 各 ${\rm DP}[i,k, \bullet, \bullet$ ] について $2$ 次元の累積和を作成することで, 遷移の計算を $O(1)$ 時間に削減することができる. この工夫により, 計算時間を $O(N^4)$ 時間に削減することができた.