Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 237 F問題 |LIS|=3

AtCoder ABC ABC237 F問題 500 pts

問題

提出解答

問題の概要

以下を全て満たす整数列の個数を求めよ.

長さ $N$
各項は $1$ 以上 $M$ 以下
最長増加部分列の長さがちょうど $3$

ただし, 最長増加部分列は狭義単調増加な部分列に対して適用される.

制約

$3 \leq N \leq 1000$
$3 \leq M \leq 10$

解法

LIS を求める方法はいくつかあるが, ここでは二分探索を用いる方法を考える.

動的計画法で求める. ${\rm DP}[i,p,q,r]$ を第 $i$ 項まで確定させたとき, LIS を求めるための配列 (二分探索の対象) が $[p,q,r]$ であるような列の数とする.

ベースケースは

${\rm DP}[0,p,q,r]=\begin{cases} 1 & (p=\infty_1, q=\infty_2, r=\infty_3) \\ 0 & ({\rm otherwise}) \end{cases}$

である.

更新式について, 第 $i-1$ 項までみて, 二分探索の対象が $[p,q,r]$ であるとき, 第 $i$ 項目が $s$ である場合を考える. 今回は狭義単調増加列であることに注意すると,

$s \leq p$ ならば, ${\rm DP}[i,s,q,r ]$ に ${\rm DP}[i-1, p,q,r]$ を加算する.
$p \lt s \leq q$ ならば, ${\rm DP}[i,p,s,r ]$ に ${\rm DP}[i-1, p,q,r]$ を加算する.
$q \lt s \leq r$ ならば, ${\rm DP}[i,p,q,s ]$ に ${\rm DP}[i-1, p,q,r]$ を加算する.
$r \lt s$ ならば, LIS の長さが $4$ 以上で確定するので, 加算はない.

この更新式によって, 動的計画法の要素の数が $O(N M^3)$ で各 $i$ ごとに更新のために $O(M^4)$ 時間かかるので, 全体では $O(NM^4)$ となる, この問題の制約下では, 十分高速である.