挿入 DP の二つの型について
問題のネタバレを多く含みます
挿入 DP
隣り合う項の大小関係に条件がついた順列を数え上げるときに使われることが多い。
$\mathrm{dp}(i, S) := $ $(1, 2, \dots, i$ からなる順列のうち、$S$ をみたすものの個数$)$
という状態を考えるのだが、遷移の考え方によって二種類の型に分けられる（と考えている）ので、それぞれについて説明する。
その①「割り込み」型
前から作っていくのではなく、遷移の際に「$1, 2, \dots, i - 1$ からなる順列のどこに $i$ を挿入するか」を考える。
DEGwer さんの数え上げ PDF で紹介されているのはこっち。
超簡単な例題
概要
$1$ 以上 $N$ 以下の整数からなる順列の個数を求めよ。
制約
$ 1 \leq N \leq 10 ^ 5 $
解法
答えが $N!$ になることは知らないとして、DP を考える。
$\mathrm{dp}(i) := $ $(1, 2, \dots, i$ を並べた順列の個数$)$ と定める。
$1, 2, \dots, i$ からなる順列において $i + 1$ を挿入できる箇所は $i + 1$ 通りあるので、
$$ \mathrm{dp}(i + 1) = \mathrm{dp}(i) \times (i + 1) $$
となる。よって、$O(N)$ 時間の DP で答えが求まる。
ABC 267 G - Increasing K Times
概要
与えられた数列 $A$ を並べ替えて得られる数列 $B$ であって、$B_i < B_{i + 1}$ を満たす $i$ が $K$ 個あるようなものの個数を求めよ。（ただし、$A$ に含まれる数は値が同じであっても区別する）
制約
$2 \leq N \leq 5000$
解法
値の小さい順に、値が同じものはまとめて、列に挿入していくことを考える。 列を構成している数たちは、今挿入しようとしている数よりも小さいため、
$\mathrm{dp}(i, j) := $ 小さい方から $i$ 種類の数を挿入したとき、$B_k < B_{k + 1}$ なる $k$ が $j$ 個あるような列 $B$ の個数
という DP が回る。
数え上げ PDF 3.2 節
概要
高さ $1$ から $N$ までのビルを横一列に並べる。左からは $K$ 個、右からは $L$ 個のビルが見えるような並べ方は何通りあるか求めよ。
簡単な解説
さっきとは逆に、大きい方（高い方）から順に挿入していくと見通しがよい。
その②「過去改変」型
前から順に列を作っていく。ただし、$p_i$ までを作る際に使えるのは $1, 2, \dots, i$ のみであるとする。
$p_{i + 1} = x$ なる $x$ を $1, 2, \dots, i+1$ から選びたいのだが、このままでは列に $x$ が $2$ つ出現してしまう。そこで、さっきまでの列における $x, x + 1, \dots, i$ は $1$ つずつ後ろにずらして、$x + 1, x + 2, \dots, i + 1$ だったことにする。
例えば、$p_6$ までを $1$ 〜 $6$ で作った列が $(3, 2, 4, 1, 5, 6)$ だったとする。ここで $p_7 = 4$ と決めると、新しい数列は $(3, 2, 5, 1, 6, 7, 4)$ となる。$p_3 = 4, p_6 = 5, p_7 = 6$ が $1$ つずつ後ろにずれて、$p_3 = 5, p_6 = 6, p_7 = 7$ だったことになっている。
型①とは異なり今作っている列に挿入するわけではないので分かりにくいが、使った数の集合 $1, 2, \dots, i$ に $k$ を挿入して $x\in \lbrace 1, \dots, k-1, k, k + 1, \dots, i + 1 \rbrace$ としていると思えるので、「挿入 DP」と呼ばれるのも納得できる。
超簡単な例題
概要
$1$ 以上 $N$ 以下の整数からなる順列の個数を求めよ。
制約
$ 1 \leq N \leq 10 ^ 5 $
解法
$\mathrm{dp}(i) := (i $ 項目までに $1, 2, \dots, i$ を並べた順列の個数$)$ と定める。
$i + 1$ 項目としてありうる値は $1, 2, \dots, i + 1$ の $i + 1$ 通りあるので、
$$ \mathrm{dp}(i + 1) = \mathrm{dp}(i) \times (i + 1) $$
となる。よって、$O(N)$ 時間の DP で答えが求まる。
EDPC T - Permutation
概要
<, >, ? からなる長さ $N - 1$ の文字列 $s$ が与えられる。
$1$ 以上 $N$ 以下の整数からなる順列 $p$ であって、
- $s_i = $
<ならば $p_i < p_ {i + 1}$ - $s_i = $
>ならば $p_i > p_ {i + 1}$
を満たすものの個数を求めよ。
制約
$2 \leq N \leq 3000$
解法
$\mathrm{dp}(i, j) := $ $( i$ 項目までに $1, 2, \dots, i$ を並べた順列であって、$p_i = j$ であり、不等号の制約を満たすものの個数$)$ と定める。
$p_{i + 1}$ に何を置けるかは、$j$ と $s_i$ を見れば分かる。
- $s_i =$
<のときは $p_{i + 1}$ として $j, j+1, \dots, i+1$ を選べる。 - $s_i$ =
>のときは $p_{i + 1}$ として $1, 2, \dots, j$ を選べる。$j$ が被っているのが不思議だが、元あった $j$ は $j+1$ だったことになるので問題ない。
ABC 282 G - Similar Permutation
概要
$1$ 以上 $N$ 以下の整数からなる順列 $A, B$ であって、隣接する項の大小が $K$ 箇所で一致しているようなものの個数を求めよ。
簡単な解説
列を $2$ つ作る必要があるが、EDPC T - Permutation とほぼ同じ考え方で解ける。詳細は公式解説を参照。
数え上げ PDF 第 5 章 - 問題 1
概要
$1$ 以上 $N$ 以下の整数からなる順列であって、単調増加な $2$ つの列のマージとして書けるものの個数を求めよ。
簡単な解説
「greedy からの帰着」を行ったあとの数え上げパートで、型②の挿入 DP をする。
$\mathrm{dp}(i, j) := $ $( i$ 項目までに $1, 2, \dots, i$ を並べた順列であって、$B$ の列の末尾が $j$ であるようなものの個数$)$
とすると解ける。
