各種 DP を愚直な形で考えてみる

先日、下記の記事でナップサック問題の DP を愚直に眺めました。

rsk0315.hatenablog.com

今回は、ナップサック問題に限らず様々な DP を愚直に眺める回です。「○○（何らかの集合）の最大値」のように計算せず、○○の部分について考えていきます。もちろん DP をする際に○○をそのまま持つと空間計算量がめちゃくちゃになる（ことに伴って時間計算量もめちゃくちゃになる）のですが、典型 DP で暗に構築されている集合を考えておくことで、そうした構造を持つ DP を考える際に理解がスムーズになる気がします。「何々を全パターン考慮したい」となったときに「こういう漸化式を考えればよいはず」とできるレパートリーが増えそうです。

想定読者は競プロをしていて DP を学び中・苦戦中〜ある程度知っている人で、ある程度数式を読める人です。数式が苦手な人は、数式が得意な人に助けてもらうなどをしてもらえると助かります。具体例も交えつつ説明しているので雰囲気はわかってもらえるかもしれません？とはいえ目で読むだけではわからない部分もあると思うので、手を動かしつつ考えてもらえるとうれしい気がします。

軽い気持ちで書き始めたところ過去一のボリュームになってしまって困惑しています。各テーマは概ね難易度順で並んでいる気がしますが、あまり順序にこだわらず気になるところを読みたいときに読んでもらえればよさそうです。

導入
定義や記法など
- 集合の記法に関して
肩慣らし
- Fibonacci 数列
典型的な構造
実装例
関連資料
あとがき
おわり

導入

$\gdef\DP{\operatorname{dp}}$ 何らかの集合 $\mathcal{S}$ に対して $\bigodot_{S\in\mathcal{S}} f(S)$ を計算したい問題があったとします。このような問題で DP を行う場合、$\mathcal{S}$ を構築する漸化式をそのまま DP に流用できることがしばしばあります。そのため、$\mathcal{S}$ に関する漸化式を考えておくことが有用です。

ここで、$\mathcal{S}$ は一般には空間計算量がかさむもの（部分文字列や部分集合など）の集合で、$f$ はその要素を空間計算量のかさまないもの（整数や boolean など）に写す関数、$\bigodot$ は $f$ で写されたものたちを合わせる操作（$\min$ や $\sum$ など）です。個人的には $f$ を projection (project)、$\bigodot$ を folding (fold) と呼んでいます。

また、下記で挙げるような $\mathcal{S}$ に対して、「$\mathcal{S}$ の各要素を条件 $P$ を満たすかどうかで分類する」「$\mathcal{S}$ の各要素 $S$ を関数 $f(S)$ の値で分類する」などを考慮することで、条件の増えた DP を考えることが可能です。

先日の記事では配る・もらうに関して考えましたが、ここでは数式との相性がよい方法で考えたいので、基本的にはもらう形式での漸化式になっています。とはいえ、適切に考察することで実装上は配る形式にもできるテーマが多めになっています。

rsk0315.hatenablog.com

定義や記法など

おことわり：集合 (set) や列 (sequence)、順列 (permutation) や分割 (partition) や経路 (path) など、頭文字が共通の対象が複数出てきますが、それらごとに別々の文字を使おうとすると逆に混乱しそうでした。各節ごとにスコープが切られているとして、型を明示しつつ $S$ や $P$ などの文字を使うことにします。

$S\cap T=\emptyset$ を満たす集合 $S$ と $T$ に対して、$S\sqcup T=S\cup T$ とします。たとえば、漸化式を立てる際などに $S_i = S_{i-1}\sqcup S_{i-2}$ のように書き、$S_{i-1}$ と $S_{i-2}$ に重複する要素がないことを示すのに使ったりします。実際には $S_{i-1}\cap S_{i-2}=\emptyset$ であることを示す必要がありますが、適宜省略します。 $\sum_{x\in S\sqcup T} f(x) = \sum_{x\in S} f(x) + \sum_{x\in T} f(x)$ などが成り立って便利なので、$\cup$ ではなく $\sqcup$ で考えておいた方が使い勝手がよいことが多そうです。

文字集合 $\Sigma$ に対して、$\Sigma$ の要素を（重複してもよく）順に $n$ 個並べたもの $(\sigma_0, \sigma_1, \dots \sigma_{n-1})$ を $\Sigma$ 上の長さ $n$ の列 (sequence over $\Sigma$ of length $n$) といい、これら全体の集合を $\Sigma^n$ と書きます*1。$\Sigma^0 = \{\varepsilon\}$ となる $\varepsilon$ を空列 ((the) empty sequence) と呼びます*2。曖昧さがないときは $(\sigma_0, \sigma_1, \dots, \sigma_{n-1})$ の代わりに $\sigma_0\sigma_1\dots\sigma_{n-1}$ とも書きます。

また、$\Sigma$ 上の列全体の集合 $\Sigma^\star$ を $$\Sigma^\star \triangleq \Sigma^0 \sqcup \Sigma^1 \sqcup \dots \sqcup \Sigma^n \sqcup \dots $$ で定義します。$\Sigma^\star$ は無限集合ですが、$n$ を固定した $\Sigma^n$ は（$\Sigma$ が有限の前提であれば）有限集合であることに注意しましょう。 $S$ の長さを $|S|$ と書きます。$S\in\Sigma^n$ のとき $|S|=n$ です。

列 $S$ と $T$ を（この順に）連結させたものを $S\concat T$ と書くことにします*3。$|S\concat T| = |S|+|T|$ となります。

長さ $n$ の列 $S = (S_0, \dots, S_{n-1})$ と大きさ $k$ の非負整数の集合 $I=\{i_0, i_1, \dots, i_{k-1}\}$ ($i_0\lt i_1\lt\dots\lt i_{k-1}\lt n$) に対して、$S_I$ を長さ $k$ の列 $(S_{i_0}, S_{i_1}, \dots, S_{i_{k-1}})$ とします。特に、$S_{\emptyset} = \varepsilon$ です。

列 $P$ が集合 $S$ の順列 (permutation of $S$) であるとは、$|P| = |S|$ かつ、任意の $x\in S$ に対して $x$ が $P$ にちょうど一度現れることを言います。集合 $S$ の順列全体の集合を $S!$ と書くことにします*4。$S!\subseteq S^{|S|}$ です。たとえば $$ \begin{aligned} \{0, 1, 2\}! &= \{(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)\}, \\ \emptyset! &= \{\}! = \{()\} = \{\varepsilon\} \end{aligned} $$ です。$|\varepsilon| = |\emptyset| = 0$ であり、$\emptyset$ の任意の要素がちょうど一度現れている (vacuously true) ことに注意しましょう。

簡潔さのため、場合分けで定義する際に $$ \begin{aligned} \DP[\angled{i, 0}] &= x, \\ \DP[\angled{0, j}] &= y, \\ \DP[\angled{i, j}] &= z \end{aligned} $$ のように $i$ や $j$ の条件を明示せずに行います。よくあるプログラミング言語のパターンマッチのように上から順に適用されるとし、たとえば次の略記であると解釈されたいです。 $$ \DP[\angled{i, j}] = \begin{cases} x, & \text{if }j = 0; \\ y, & \text{if }j \ne 0 \wedge i = 0; \\ z, & \text{if }j \ne 0 \wedge i \ne 0. \end{cases} $$

その他、各トピックにおける限定的な定義に関しては、該当箇所で個別に記すことにします。

集合の記法に関して

いろいろ出てくるので書いておきます。

内包的記法においては、概ね次のような気持ちで記述しています（厳密に守られていることを保証するものではないです）。

記法	きもち
$\{x\in S\mid P(x)\}$	`s.filter(p)`
$\{f(x)\mid x\in S\}$	`s.map(f)`
$\{f(x)\mid x\in S, P(x)\}$	`s.filter(p).map(f)`

ここで .filter(p) は p を満たすものに絞る操作で、.map(f) は各要素に f を適用する操作です。 $x, x'\in S$ ($x\ne x'$) に対して $f(x) \ne f(x')$ と限らない場合、$\{f(x)\mid x\in S\}$ の要素数が $S$ より減りうることには注意しましょう（ここではあまりそういう例は出ないですが）。

複数の集合の $\sqcup$ を考えるときの記法です。 $$ \bigsqcup_{i=0}^{n-1} S_i = S_0\sqcup S_1 \sqcup \dots \sqcup S_{n-1} $$ です。下記では集合の集合などを考えたりするので、ややこしくなりますが落ちついて考えましょう。 $$ \begin{aligned} \bigsqcup_{i=0}^{n-1} {\{S_i\}} &= \{S_0\}\sqcup \{S_1\} \sqcup \dots \sqcup \{S_{n-1}\} \\ &= \{S_0, S_1, \dots, S_{n-1}\} \\ &= \{S_i\mid i\in\{0, 1, \dots, n-1\}\}. \end{aligned} $$

集合 $S = \{a_0, \dots, a_{n-1}\}$ に新しく要素 $a_n$ を加えた集合を考えたいときは、$S\sqcup \{a_n\}$ のように書きます。

$S$ の部分集合 $T$ を考えたいとき、「$T\subseteq S$ を考える」ではなく「$T\in 2^S$ を考える」のような記法を使うことが多いです。集合から選んでくることを意識しようとしてこういう書き方をしていますが、意味合いとしては同じです。

肩慣らし

一般的に使えるような構造の話をする前に、単純な DP を考えてみましょう。愚直に考える練習です。

Fibonacci 数列

列 $S=(S_0, S_1, \dots, S_{|S|-1})$ に対して、簡潔さのため $\sum S = \sum_{i=0}^{|S|-1} S_i$ と定義しておきます。

$\Sigma = \{1, 2\}$ 上の列を考え、$S\in\Sigma^{\star}$ であって $\sum S = k$ なるもの全体からなる集合を $\Phi_k$ とおきます。小さい方から挙げると次のようになります。 $$ \begin{aligned} \Phi_0 &= \{\varepsilon\}, \\ \Phi_1 &= \{(1)\}, \\ \Phi_2 &= \{(1, 1), (2)\}, \\ \Phi_3 &= \{(1, 1, 1), (1, 2), (2, 1)\}, \\ \Phi_4 &= \{(1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2)\}. \end{aligned} $$

$n\gt 0$ のとき、先頭の要素が $1$ か $2$ かで分類することができ、 $$ \Phi_n = \{(1)\concat\phi\mid\phi\in\Phi_{n-1}\}\sqcup\{(2)\concat\phi\mid\phi\in\Phi_{n-2}\} $$ と書くことができます。両辺の要素数を考えれば $|\Phi_n| = |\Phi_{n-1}| + |\Phi_{n-2}|$ となりますね。

Fibonacci 数列を $(1, 1, 2, 3, 5, \dots)$ とだけ考えるよりも、「$3$ と言っているのは $\{(1, 1, 1), (1, 2), (2, 1)\}$ に対応しているんだ」と思える方がイメージの幅が広がるのではないでしょうか。もちろん、イメージの仕方は他にもいろいろあるとは思います。

さて、陽に列を書き出してみると、「$\Phi_n$ に含まれる列の長さの合計はいくつ？」のような疑問も自然に湧いてくるのではないでしょうか。ちょっとやってみましょう。 $$ \begin{aligned} \sum_{\phi\in\Phi_n} |\phi| &= \sum_{\phi\in\Phi_{n-1}} |(1)\concat\phi| + \sum_{\phi\in\Phi_{n-2}} |(2)\concat\phi| \\ &= \sum_{\phi\in\Phi_{n-1}} (1 + |\phi|) + \sum_{\phi\in\Phi_{n-2}} (1 + |\phi|) \\ &= \sum_{\phi\in\Phi_{n-1}} 1 + \sum_{\phi\in\Phi_{n-1}} |\phi| + \sum_{\phi\in\Phi_{n-2}} 1 + \sum_{\phi\in\Phi_{n-2}} |\phi| \\ &= |\Phi_{n-1}| + \sum_{\phi\in\Phi_{n-1}} |\phi| + |\Phi_{n-2}| + \sum_{\phi\in\Phi_{n-2}} |\phi| \end{aligned} $$ 漸化式が立ったので $|\Phi_n|$ の方と合わせて計算することができますね。$(0, 1, 3, 7, 15, 30, 58, \dots)$ と続くようです。

別の解法（おまけ）

形式的冪級数を考えます。 $$ A(x, y) = \sum_{S\in\{1, 2\}^{\star}} x^{\sum S}y^{|S|} $$ とおくと、 $$ \begin{aligned} A(x, y) &= x^{\sum \varepsilon}y^{|\varepsilon|} + \sum_{S\in\{1, 2\}^{\star}} x^{\sum (1)\concat S}y^{|(1)\concat S|} + \sum_{S\in\{1, 2\}^{\star}} x^{\sum (2)\concat S}y^{|(2)\concat S|} \\ &= x^0y^0 + \sum_{S\in\{1, 2\}^{\star}} x^{1 + \sum S}y^{1+|S|} + \sum_{S\in\{1, 2\}^{\star}} x^{2 + \sum S}y^{1+|S|} \\ &= 1 + xy\cdot A(x, y) + x^2 y\cdot A(x, y) \\ &= (1-xy-x^2 y)^{-1} \end{aligned} $$ です。求めたいものは $$ [x^k] \frac{\partial}{\partial y} A(x, 1) = [x^k] \sum_{S\in\{1, 2\}^{\star}} x^{\sum S} \cdot |S|\,1^{|S|-1} $$ なので、 $$ \frac{\partial}{\partial y} A(x, 1) = \frac{x+x^2}{(1-x-x^2)^2} $$ を用いて計算すればよいでしょう。

典型的な構造

下記では、$n$ 未満の非負整数全体からなる集合をよく考えます。そこで $\Lambda_n = \{0, 1, \dots, n-1\}$ とおいておきます。特に $\Lambda_0 = \{\} = \emptyset$ です。

$\Lambda_n$ から作られるいろいろな構造を考えていきます。難しそうな場合でも闇雲に漸化式を立てようとするのではなく、まずは構造について考えたり、DP の定義を決めるところから始めましょう。

部分集合

$\Lambda_n$ に対して $2^{\Lambda_n}$ を得る方法を考えてみましょう。

簡単に思いつくものとして、 $$\DP[i] = 2^{\Lambda_i}$$ として、次の漸化式を立てられそうです。 $$ \begin{aligned} \DP[0] &= \{\emptyset\}, \\ \DP[i] &= \big\{S\sqcup\{\}\mid S\in\DP[i-1]\big\} \sqcup \big\{S\sqcup\{i-1\}\mid S\in\DP[i-1]\big\} \\ &= \DP[i-1] \sqcup \big\{S\sqcup\{i-1\}\mid S\in\DP[i-1]\big\} \end{aligned} $$ があります。

二項係数の文脈で、$(1+x)(1+x)(1+x)\cdots$ を展開しようとして順に $( (1+x)\cdot 1 + (1+x)\cdot x)(1+x)\cdots$ とするのと似ていそうです。

$\mathcal{S} = \DP[i]$ の各要素（であるところの集合）$S$ を $\sum_{i\in S} w_i$ ごとに分類して、$f(S) = \sum_{i\in S} v_i$、$\bigodot = \max$ とすることで、ナップサック問題の DP になります。あるいは、$f(S) = 1$、$\bigodot = \sum$ とすることで、部分和問題の数え上げの DP になります。

ここでは簡単のため $\{0, 1, \dots, n-1\}$ について考えましたが、状況に応じて $\{\sigma_0, \sigma_1, \dots, \sigma_{n-1}\}$ を考えた方がよいケースもあるでしょう。状況に応じて適切にやってください。以下の構造についても同じです。

また、集合を考える代わりに、適当な順で固定した列を考えていると見なすこともできそうです。$S$ の代わりに $x\in S!$ なるいずれかの $x$ を考えているということです。

順列 (exponential)

$\Lambda_n$ に対して $\Lambda_n!$ を得る方法を考えてみましょう。

$T\subseteq S$ に対して $\DP[T] = T!$ とすることで次のような漸化式を立てられそうです。 $$ \begin{aligned} \DP[\emptyset] &= \{\varepsilon\}, \\ \DP[T] &= \bigsqcup_{x\in T} \big\{P \concat (x) \mid P\in \DP[T\smallsetminus\{x\}]\big\}. \end{aligned} $$ 気持ちとしては、「集合 $T$ の順列全体を考えたい。まず末尾に来る要素 $x\in T$ を固定する。列の末尾を取り除いたものは $T\smallsetminus\{x\}$ の順列である。$T\smallsetminus\{x\}$ の順列全体の集合というのは、いま考えたい問題と同様の形式であり、より自明なケースになっている」という感じです。実際には、漏れや重複がないことを示す必要がありそうです。

任意の $T\subseteq S$ について $\DP[T]$ を考えるので、$\DP$ の添字の個数としては $2^{|S|}$ になります。$2^{|S|} = o(|S|!)$ であることに一応注意しておきましょう。

実装する上では、$\DP[T]$ の部分について少し考慮する必要があります。素朴には連想配列を用いることになりそうですが、要素数が $2^{|S|}$ かつ比較に最悪 $\Theta(|S|)$ 時間かかることから、 $$\Theta(2^{|S|}\log(2^{|S|})\cdot |S|) = \Theta(|S|^2\, 2^{|S|})$$ 程度の時間を使ってしまいそうです*5。今々は $T!$ の各要素を陽に持っているので、それにかかる時間・空間の方が膨大ではあるのですが、project・fold した場合は各要素のコストが無視できるため、こちらが無視できなくなってしまいます。

よくある実装として、集合を整数にエンコードする方法があり、bit DP などと呼ばれています。 $$\angled{T} = \sum_{x\in T} 2^x$$ で定義します。たとえば $\angled{\emptyset} = 0$、$\angled{\{0, 1, 3\}} = 2^0+2^1+2^3=11$ です。 $\DP[\angled{T}]$ が $O(1)$ 時間でアクセスできるようになる上、連想配列のときのように $T$ を陽に持つ必要がなくなるため、空間も全体で $O(2^{|S|})$ words になります。

ここは気になる読者向けです。「$|S|$ が大きくなったら多倍長整数が必要になるのでは？」という風なことを言う人がいるかもしれませんが、そもそも $2^{64}$ 個のエントリを埋めるの自体が（時間的に）現実的でないため、そうした心配は不要そうです。あるいは、時間は適当に解決することにして $2^{1024}$ 個のエントリを埋めることになったとします。こうなったとき、メモリ空間上の $2^{1024}$ 個の位置にランダムアクセスできる必要があるため、word 一つあたりのビット数も $1024$ 程度は最低限必要になります。そういうわけで、「集合サイズが大きくなるなら多倍長整数が必要になる」というのは必ずしも「そうですね」とは言えないです。ランダムアクセスの要件がなければ word の下限を保証できないので困りますが、考えている計算モデルによるわけですね。詳しくは transdichotomous model とか word RAM とかで調べるとよさそうです。

さて、よくある例としては巡回セールスマン問題などがあります。順列 $P$ のコストを $f(P)$、辺 $(u, v)$ の重みを $w(u, v)$ とすると、 $$ f(P' \concat (u, v)) = f(P'\concat(u)) + w(u, v) $$ のように計算できるため、$P$ の末尾の要素で分類することで漸化式を立てられます。末尾の要素を明示するため、先の漸化式で $P$ としていた部分を $P'\concat(u)$ のようにしています。実装上は $\DP[\angled{T}][v]$ のようなイメージでしょうか。 $\varepsilon = P'\concat(u)$ となるような $P'$ は存在しないので、ベースケースには注意が必要です。

組合せ

集合 $S$ の部分集合のうち要素数が $k$ のものを $(S)_k$ と書くことにします。$|(S)_k| = \binom{|S|}{k}$ に由来する記法です（他ではあまり見ない気がします）。さて、数式で書けば次の通りです。 $$ (S)_k = \{x\in 2^S\mid |x| = k\}. $$

さて、$(\Lambda_n)_k$ について漸化式を考えます。 $$ \begin{aligned} (\Lambda_n)_0 &= \{\emptyset\}, \\ (\Lambda_0)_k &= \emptyset, \\ % (\Lambda_n)_k &= \big( (\Lambda_{n-1})_{k-1}\sqcup\{k-1\}\big)\sqcup(\Lambda_{n-1})_k. (\Lambda_n)_k &= \big( \{T\sqcup\{n-1\}\mid T\in(\Lambda_{n-1})_{k-1}\}\big)\sqcup(\Lambda_{n-1})_k. \end{aligned} $$

いわゆる Pascal の三角形の漸化式に相当します。 $n$ が小さいときは bit DP でもできます。bit DP の基礎練習としてやってみるのもよいでしょう。

また、$\bigsqcup_{k=0}^n (\Lambda_n)_k = 2^{\Lambda_n}$ となるので、部分集合に関する何らかの DP にも使えるかもしれません。

部分列 (1)

$\Sigma$ 上の長さ $n$ の列 $S\in\Sigma^n$ が与えられます。

$S$ の部分列全体の集合 $\gdef\subseq#1{\mathop{\operatorname{subseq}} #1}$ $$ % \subseq{S} = \bigcup \big\{S_I \mid I\in 2^{\Lambda_n}\big\} \subseq{S} = \bigcup_{I\in 2^{\Lambda_n}} \{S_I\} = \{S_I \mid I\in 2^{\Lambda_n}\} $$ を考えます。$\subseq{\varepsilon} = \{\varepsilon\}$ です。

なお、$\bigsqcup$ ではなく $\bigcup$ であることに注意しましょう。たとえば $\Sigma=\{\mathtt{a}, \mathtt{b}\}$ 上の列 $S = \mathtt{aab}$ に対して $S_{\{0, 2\}} = S_{\{1, 2\}} = \mathtt{ab}$ となります。 $$ \subseq{\mathtt{aab}} = \{\varepsilon, \mathtt{a}, \mathtt{aa}, \mathtt{aab}, \mathtt{ab}, \mathtt{b}\} $$ です。（こうした理由から、部分集合全体の集合のときとは違って $2^S$ のような記法は適さなさそうです。）

そこで、$S_I = S_J$ となるような $I$, $J$ は、これから定める順序 $\preceq$ で最小のものについてのみ考えることにしてみます。すなわち、任意の $J\ne I$ に対して $I\preceq J$ となるような $I$ を考えるということです。気持ちとしては、“辞書順最小” 的なものを集合に対して考えたいです。 $$ % I\preceq J \stackrel{\vartriangle}{\iff} I = J \vee \min\, (I\smallsetminus J) \lt \min\, (J\smallsetminus I) I\preceq J \stackrel{\vartriangle}{\iff} (I\smallsetminus J) = \emptyset \vee \min\, (I\smallsetminus J) \lt \min\, (J\smallsetminus I). $$ ただし、$\min\emptyset = \infty$ としておきます。

部分列を列挙する代わりに、“辞書順最小” の添字の方を列挙することにします。$\subseq{S}$ も定義し直して、添字たちの集合であるところの $$ \subseq S \triangleq \{ I\in 2^{\Lambda_n}\mid \ForallL{J\in 2^{\Lambda_n}}{S_I=S_J\implies I\preceq J} \} $$ とします。

まず、ある添字 $I\in 2^{\Lambda_n}$ が $I\in\subseq{S}$ であることの必要十分条件を考えてみましょう。 $$ \begin{aligned} % I\notin\subseq{S} \iff \ExistsL{J\in 2^{\Lambda_n}}{S_I=S_J \wedge J \prec I} I\in\subseq{S} \iff \ForallL{J\in 2^{\Lambda_n}}{S_I=S_J\implies I\preceq J} \end{aligned} $$ です。 $\emptyset\in\subseq{S}$ は自明なので、以下では $I = \{i_0, i_1, \dots, i_{k-1}\}$ とします。ある $0\le j\lt i_0$ が存在して $S_{i_0} = S_j$ のとき、$J = \{j, i_1, \dots, i_{k-1}\}$ に対して $S_I = S_J \wedge I\succ J$ となります。よって、$i_0 = \min{\{i\in\Lambda_n\mid S_i = S_{i_0}\}}$ が必要です。同様にして、$i_j = \min{\{i\in\Lambda_n\mid i\gt i_{j-1}\wedge S_i = S_{i_j}\}}$ ($0\lt j\lt k$) が必要です。逆に、これで十分であることもわかります。

$I = \{i_0, i_1, \dots, i_{k-1}\}$ とし、$I \in\subseq{S}$ とします。このとき、$i_k\gt i_{k-1}$ なる $i_k$ に対して $I\cup\{i_k\}\in\subseq{S}$ となる条件を考えます。前述の議論と同様にして、 $$\ForallL{i\in\Lambda_n}{i_{k-1}\lt i\lt i_k \implies S_i\ne S_{i_k}}$$ と同値になります。

よって、これを元にして DP を考えます。 $$ \begin{aligned} \DP[0] &= \{\emptyset\}, \\ \DP[i] &= \{I\in\subseq{S}\mid I\ne\emptyset\wedge\max I=i-1\} \end{aligned} $$ を考えます。$\subseq{S} = \bigsqcup_{i=0}^n\DP[i]$ です。

漸化式は、次のようになります。 $\gdef\last{\operatorname{last}}$ $$ \DP[i] = \bigsqcup_{j=\last(i)}^{i-1} \big\{ I \sqcup \{i-1\} \mid I\in\DP[j] \big\} $$ ここで $\last(i)$ は以下で定義される関数です。$S_{i-1}$ と同じ文字が前に現れた位置まで $\sqcup$ をしたいということです。 $$ \last(i) = \max\big(\{j\mid {1\le j \lt i} \wedge {S_{j-1}=S_{i-1}}\}\sqcup\{0\}\big) $$ これは $i$ の昇順に $\DP[i]$ を更新していく過程で、連想配列などを用いて $S_{i-1}\mapsto i$ を管理すれば $O(\log(|\Sigma|))$ 時間などで可能です。

note: $i'\lt \last(i)$ なる $i'$ に対して $I\in\DP[i']$ を考えたとき、 $$ S_{I\sqcup\{i-1\}} = S_{I\sqcup\{\last(i)\}}, \quad I\sqcup\{i-1\}\succ I\sqcup\{\last(i)\} $$ なので、$I\sqcup\{i-1\}\notin\subseq S$です。

実装の際、$i-1$ から降順に $S_{j-1}=S_{i-1}$ になるまでループをしたとしても、各 $j$ は各文字に対して一度ずつしか走査されないため、全体では $O(|S|\cdot|\Sigma|)$ 回程度のループとなります*6。$|\Sigma| = 26 = O(1)$ などのよくある問題設定であれば、$\Theta(|S|^2)$ 時間にはならないので安心できそうです*7。 $|S|\ll|\Sigma|$ のような問題設定だとそうはいきませんが、imos 法を on-the-fly で行ったりセグ木を用いたりすることで高速化することも可能そうです。

また、ここでは辞書順最小を考えましたが、末尾から見ていったりすることで、辞書順最大のものを求めることも可能そうです。

部分列 (2)

部分列 (1) とは別の方針で考えます。

$\gdef\suffix#1#2{#1[#2\ldots]}$ $0\le i\le n$ に対して $\suffix{S}{i} = (S_i, \dots, S_{n-1})$ とします。特に $\suffix{S}{0} = S$, $\suffix{S}{n} = \varepsilon$ です。

$\DP[i] = \subseq \suffix{S}{i}$ ($0\le i\lt n$) としてみましょう。漸化式は次のようになります。 $\gdef\next{\operatorname{next}}$ $$ \begin{aligned} \DP[\infty] &= \emptyset, \\ \DP[i] &= \{\{i\}\}\sqcup\bigsqcup_{\sigma\in\Sigma} {\{\{i\}\sqcup I\mid I\in \DP[\next_{\sigma}(i+1)]\}}. \end{aligned} $$ ここで、$\next_{\sigma}(i) = \min{\{j\mid S_j = \sigma\wedge j\ge i\}}$ です。ただし $\min\emptyset=\infty$ としておきます。

$i'\gt\next_{\sigma}(i+1)$ かつ $S_{i'} = S_i$ なる $i'$ に対して $I\in\DP[i']$ を考えると、先ほど同様の論法で $\{i\}\sqcup I\notin\subseq \suffix{S}{i}$ となることがわかります。逆に、$I\in\DP[\next_{\sigma}(i+1)]$ に対して $\{i\}\sqcup I\in\subseq\suffix{S}{i}$ となることもわかります。

求めたかったものは $\subseq S = {\{\emptyset\}}\sqcup{\bigsqcup_{\sigma\in\Sigma} \DP[\next_{\sigma}(0)]}$ です。

部分列を前から順に決めたい文脈で便利そうです。たとえば、$\Sigma$ に関する辞書順に関する問題と相性がよさそうです。

atcoder.jp

非負整数 (1)

非負整数 $A$ が与えられるので、$A$ 以下の非負整数全体の集合 $\{0, 1, \dots, A-1, A\}$ を得る方法を考えます。ループすればいいというのはそうなんですが、今まで同様に漸化式を立てましょう。集合を得ること自体ではなく projection や folding をしやすい形式で考えられるようになることが目的なので。

$A$ との大小関係を管理したい関係で、上の桁から決めていくのが自然そうです。 $A$ は $n$ 桁であるとして次のような DP を考えてみます*8。 $$ \DP[i] = \{x\in\N\mid x\cdot 10^{n-i}\le A\}. \qquad (???) $$ しかし、これは厳しいです。例として $A = 271$ で考えてみましょう。$n=3$ です。 $$ \begin{aligned} \DP[0] &= \{x\in\N\mid x\cdot 10^{3-0}\le 271\} = \{0\}, \\ \DP[1] &= \{x\in\N\mid x\cdot 10^{3-1}\le 271\} = \{0, 1, 2\}, \\ \DP[2] &= \{x\in\N\mid x\cdot 10^{3-2}\le 271\} \\ &= \{0, 1, 2, 3, \dots, 9, 10, 11, \dots, 19, 20, 21, \dots, 26, 27\}, \end{aligned} $$ $\DP[2]$ に関して、$10^1$ の位が $0$, $1$ のものは $10^0$ の位が $9$ までありますが、$10^1$ の位が $2$ のものは $7$ までしかありません。これは、漸化式を立てる上であまりうれしくありません。下位桁をどう決めても $A$ より小さいことが確定しているかどうかで分類したいです。

そこで、$\DP_{\lt}$ と $\DP_{=}$ に分けて考えます。 $$ \begin{aligned} \DP_{\lt}[i] &= \{x\in\N\mid x\cdot 10^{n-i}\lt A\}, \\ \DP_{=}[i] &= \{x\in\N\mid x\cdot 10^{n-i}=A\}. \end{aligned} $$

$A$ の上から $i$ 桁目 (0-indexed) を得る関数を定義しておきます。 $$d(A, i) \triangleq \floor{A/10^{n-i-1}}\bmod 10.$$

漸化式は次のようになります。 $$ \begin{aligned} \DP_{\lt}[0] &= \{\}, \\ \DP_{=}[0] &= \{0\}, \\ \DP_{\lt}[i] &= \{10x+y \mid x \in\DP_{\lt}[i-1], 0\le y\le 9\} \sqcup {} \\ &\phantom{{}={}}\quad \{10x+y\mid x\in\DP_{=}[i-1], 0\le y\lt d(A, i-1)\}, \\ \DP_{=}[i] &= \{10x+y \mid x\in\DP_{=}[i-1], y = d(A, i-1)\}. \end{aligned} $$ 求めたいものは $\DP_{\lt}[n]\sqcup\DP_{=}[n]$ です。$\DP_{=}[n] = \{A\}$ なので、$A$ 未満の非負整数全体の集合を考えたいときは $\DP_{\lt}[n]$ を使えばよいです（わざわざ $A-1$ を計算して上記に帰着させなくてよいということ）。

いわゆる桁 DP です。 $10$ 進法ではなく一般に $b$ 進法の場合はそれに応じて変えましょう。なにかしらのあまりで分類したい場合や、なにかしらの値の総和を管理したい場合にも便利です。適切に漸化式を立てましょう。

なお、$\sqcup$ の引数の順序に注意することで、非負整数を昇順に列挙することが可能なことから、folding が可換でない場合にも対応することが可能そうに見えます。あまり役立つ状況は思いつきません。

ここは少し発展的な内容かもしれません。ところで、この DP ではオートマトンを暗に考えています。読んだ数字（上記の $0\le y\le 9$）に応じて、$(=)$ の状態からは $(=)$ または $(\lt)$ の状態に遷移することができ、$(\lt)$ の状態からは $(\lt)$ にのみ遷移することができます。より一般に、「こうした条件を満たす集合からはこの集合に遷移できる」といったことを考えて漸化式を立てる場合、オートマトンを考えていることに相当しそうです。遷移の方向は一方通行とは限りません。たとえば値を $m$ で割ったあまりなどの分類もオートマトンと見なせます。例として $2$ 進法として解釈して $5$ で割ったあまりで分類すると、状態が $5$ つのオートマトン上の遷移になります。

$x\bmod 5$	$(2x+0)\bmod 5$	$(2x+1)\bmod 5$
$0$	$0$	$1$
$1$	$2$	$3$
$2$	$4$	$0$
$3$	$1$	$2$
$4$	$3$	$4$

別の話題として、総和 $\sum_{x\in \DP_{\lt}[i] } x$ を考えてみましょう。 $$ \begin{aligned} \sum_{x\in\DP_{\lt}[i]} x &= \sum_{x\in\DP_{\lt}[i-1], 0\le y\le 9} (10x+y) + \sum_{x\in\DP_{=}[i-1], 0\le y\lt d(A, i-1)} (10x+y) \\ &= 10 \sum_{x\in\DP_{\lt}[i-1]} x \sum_{0\le y\le 9} 1 + \sum_{x\in\DP_{\lt}[i-1]} \sum_{0\le y\le 9} y + {} \\ &\phantom{{}={}} \quad 10 \sum_{x\in\DP_{=}[i-1]} x \sum_{0\le y\lt d(A, i-1)} 1 + \sum_{x\in\DP_{=}[i-1]} \sum_{0\le y\lt d(A, i-1)} y \\ &= 10^2 \sum_{x\in\DP_{\lt}[i-1]} x + |{\DP_{\lt}[i-1]}| \sum_{0\le y\le 9} y + 10d(A, i-1)\sum_{\DP_{=}[i-1]} x + |{\DP_{=}[i-1]}| \sum_{0\le y\lt d(A, i-1)} y \end{aligned} $$

よって、 $$ \begin{aligned} S_{\lt}^0(i) &= \sum_{x\in\DP_{\lt}[i]} x^0 = |{\DP_{\lt}[i]}|, \\ S_{\lt}^1(i) &= \sum_{x\in\DP_{\lt}[i]} x^1 = \sum_{x\in\DP_{\lt}[i]} x, \\ S_{=}^0(i) &= \sum_{x\in\DP_{=}[i]} x^0 = |{\DP_{=}[i]}|, \\ S_{=}^1(i) &= \sum_{x\in\DP_{=}[i]} x^1 = \sum_{x\in\DP_{=}[i]} x \end{aligned} $$ とおくと、 $$ S_{\lt}^1(i) = 10^2\, S_{\lt}^1(i-1) + S_{\lt}^0(i-1)\sum_{y=0}^9 y + 10d(A, i-1)\cdot S_{=}^1(i-1) + S_{=}^0(i-1)\sum_{y=0}^{d(A, i-1)-1} y $$ のような漸化式が立ちます。$S_{=}^1(i)$ についても同様にできます。 $S_{\lt}^0(i)$ については前述の DP から自然に計算できるので、総和についても求めることができました。

$S_{\lt}^2(i) = \sum_{x\in\DP_{\lt}[i]} x^2$ などについても（読者各々が式変形をして）考えてみると、個数・総和ではなく $0$ 乗和・$1$ 乗和・$2$ 乗和のように考える方が自然だと思えるでしょう。

atcoder.jp

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3110judge.u-aizu.ac.jp

非負整数 (2)

非負整数 (1) では上の桁から見ていきましたが、下の桁から見ていくことも考えてみましょう。

下位桁が決まっても $A$ との大小関係は定まらないので少し大変そうです。

今回は、$\DP_{\lt}$ と $\DP_{=}$ と $\DP_{\gt}$ に分けて考えます。 $$ \begin{aligned} \DP_{\lt}[i] &= \{x\in\N\mid x\lt A\bmod 10^i\}, \\ \DP_{=}[i] &= \{x\in\N\mid x=A\bmod 10^i\}, \\ \DP_{\gt}[i] &= \{x\in\N\mid x\gt A\bmod 10^i\}. \end{aligned} $$

$A$ の下から $i$ 桁目 (0-indexed) を得る関数を定義しておきます。 $$d(A, i) \triangleq \floor{A/10^{i}}\bmod 10.$$

漸化式は次の通りです。便宜的に、$\DP_{\lesseqgtr}[i] = \DP_{\lt}[i]\sqcup\DP_{=}[i]\sqcup\DP_{\gt}[i]$ とします。 $$ \begin{aligned} \DP_{\lt}[0] &= \DP_{\gt}[0] = \{\}, \\ \DP_{=}[0] &= \{0\}, \\ \DP_{\lt}[i] &= \{10^{i-1}x+y\mid 0\le x\lt d(A, i-1), y\in\DP_{\lesseqgtr}[i-1]\} \sqcup {} \\ &\phantom{{}={}} \quad \{10^{i-1}\cdot d(A, i-1)+y\mid y\in\DP_{\lt}[i-1]\}, \\ \DP_{=}[i] &= \{10^{i-1}\cdot d(A, i-1)+y\mid y\in\DP_{=}[i-1]\}, \\ \DP_{\gt}[i] &= \{10^{i-1}\cdot d(A, i-1)+y\mid y\in\DP_{\gt}[i-1]\} \sqcup {} \\ &\phantom{{}={}} \quad \{10^{i-1}x+y\mid d(A, i-1)\lt x\le 9, y\in\DP_{\lesseqgtr}[i-1]\}. \end{aligned} $$

求めたいものは $\DP_{\lt}[n]\sqcup\DP_{=}[n]$ です。昇順の話や未満の話、総和の話などは非負整数 (1) の節と同じです。繰り上がりや leading zero などの関係で下の桁から見ていきたいときにはこちらが便利かもしれません。

Excel 進法

Excel の列番号は A, B, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA, ..., AAAA, ... のように続いていきます。「与えられた列番号より左の列番号は？」というのも同様の DP で列挙できます。

$\Sigma = \{\text{\texttt{A}}, \text{\texttt{B}}, \dots, \text{\texttt{Z}}\}$ とし、$S, T\in\Sigma^{\star}$ に対して順序 $\preceq$ を Excel の列番号としての前後で定めます。次のように表すことができます。ただし、$\le$ は辞書順とします。 $$ S\preceq T \iff |S| \lt |T| \vee (|S| = |T| \wedge S\le T). $$

与えられた列番号 $A$ に対して DP を以下で定義します。 $$ \begin{aligned} \DP_{\lt}[i] &= \{S\in\Sigma^{|A|-i}\mid S\prec\suffix{A}{i}\}, \\ \DP_{=}[i] &= \{S\in\Sigma^{|A|-i}\mid S=\suffix{A}{i}\}, \\ \DP_{\gt}[i] &= \{S\in\Sigma^{|A|-i}\mid S\succ\suffix{A}{i}\}. \end{aligned} $$ 長さを固定しているので $\prec$ は $\lt$ と同じですね。

$\DP_{\lesseqgtr}[i] = \DP_{\lt}[i]\sqcup\DP_{=}[i]\sqcup\DP_{\gt}[i]$ とします。求めたいものは $$ \left(\bigsqcup_{1\le i\lt |A|}\DP_{\lesseqgtr}[i]\right)\sqcup \DP_{\lt}[|A|]\sqcup\DP_{=}[|A|] $$ です。

便宜上 $A[|A|-i] = a_{-i}$ として、漸化式は次のように書けます。 $$ \begin{aligned} \DP_{\lt}[0] &= \DP_{\gt}[0] = \{\}, \\ \DP_{=}[0] &= \{\varepsilon\}, \\ \DP_{\lt}[i] &= \{(x)\concat S\mid \text{\texttt{A}}\le x\lt a_{-i}, S\in\DP_{\lesseqgtr}[i-1]\} \sqcup {} \\ &\phantom{{}={}} \quad \{(a_{-i})\concat S\mid S\in\DP_{\lt}[i-1]\}, \\ \DP_{=}[i] &= \{(a_{-i})\concat S\mid S\in\DP_{=}[i-1]\}, \\ \DP_{\gt}[i] &= \{(a_{-i})\concat S\mid S\in\DP_{\gt}[i-1]\} \sqcup {} \\ &\phantom{{}={}} \quad \{(a_{-i})\concat S\mid a_{-i}\lt x\le \text{\texttt{Z}}, S\in\DP_{\lesseqgtr}[i-1]\}. \end{aligned} $$

Excel 進法で列番号が与えられて、それより左に条件を満たす列がいくつありますか、という問題はあまり出なさそうですね（かなしい）。にぶたんと組み合わせることで逆変換などもできますね。

atcoder.jp

→ 提出 #45508879

分割 (exponential)

$\Lambda_n$ の分割 (partition) を考えます。集合 $S$ の部分集合族 $P\in 2^{2^S}$ が $S$ の分割であるとは、次の 3 つの条件すべてが成り立つことを言います。

$\emptyset\notin P,$
$\bigcup P = S,$
$\ForallL{A\in P}{\ForallL{B\in P}{A\ne B\implies A\cap B=\emptyset}}.$

$\gdef\partition#1{\mathop{\operatorname{ptn}}{#1}}$ $S$ の分割全体からなる集合を $\partition{S}$ と書くことにします。

小さいケースの例を示します（左半分が $\Lambda_0$ から $\Lambda_3$ の分割で、右半分が $\Lambda_4$ の分割です）。 $$ \begin{aligned} &\partition{\emptyset} = \{ && {} && \partition{\{0, 1, 2, 3\}} = \{ \\ & \qquad \{\}, && {} && \qquad \{\{0, 1, 2, 3\}\}, \\ & \}, && {} && \qquad \{\{0, 2, 3\}, \{1\}\}, \\ &\partition{\{0\}} = \{ && {} && \qquad \{\{0, 1, 3\}, \{2\}\}, \\ & \qquad \{\{0\}\}, && {} && \qquad \{\{0, 3\}, \{1, 2\}\}, \\ & \}, && {} && \qquad \{\{0, 3\}, \{1\}, \{2\}\}, \\ &\partition{\{0, 1\}} = \{ && {} && \qquad \{\{0, 1, 2\}, \{3\}\}, \\ & \qquad \{\{0, 1\}\}, && {} && \qquad \{\{0, 2\}, \{1, 3\}\}, \\ & \qquad \{\{0\}, \{1\}\}, && {} && \qquad \{\{0, 2\}, \{1\}, \{3\}\}, \\ & \}, && {} && \qquad \{\{0, 1\}, \{2, 3\}\}, \\ &\partition{\{0, 1, 2\}} = \{ && {} && \qquad \{\{0, 1\}, \{2\}, \{3\}\}, \\ & \qquad \{\{0, 1, 2\}\}, && {} && \qquad \{\{0\}, \{1, 2, 3\}\}, \\ & \qquad \{\{0, 2\}, \{1\}\}, && {} && \qquad \{\{0\}, \{1, 3\}, \{2\}\}, \\ & \qquad \{\{0, 1\}, \{2\}\}, && {} && \qquad \{\{0\}, \{1, 2\}, \{3\}\}, \\ & \qquad \{\{0\}, \{1, 2\}\}, && {} && \qquad \{\{0\}, \{1\}, \{2, 3\}\}, \\ & \qquad \{\{0\}, \{1\}, \{2\}\}, && {} && \qquad \{\{0\}, \{1\}, \{2\}, \{3\}\}, \\ & \}, && {} && \}. \end{aligned} $$ $\partition{\emptyset} = \{\emptyset\}$ に注意しましょう。$\emptyset\in\emptyset$ ではないので、$\emptyset\notin P$ に反していません。分割でない例としては、$\{\{0\}, \{0, 1\}\}\notin\partition{\{0, 1\}}$ や $\{\{0, 1\}, \{2\}, \{\}\} \notin \partition{\{0, 1, 2\}}$ などがあります。

$\emptyset\subseteq T\subseteq S=\Lambda_n$ に対して $\DP[T] = \partition{T}$ とすると、漸化式は次のようになります。 $$ \begin{aligned} \DP[\emptyset] &= \{\emptyset\}, \\ \DP[T] &= \bigsqcup_{\emptyset\subseteq T'\subseteq(T\smallsetminus\{\min T\})} \{ P\sqcup (T\smallsetminus T') \mid P\in\DP[T'] \}. \end{aligned} $$

実装に関して、$\emptyset\subseteq T'\subseteq(T\smallsetminus\{\min T\})$ の列挙の際に、「$T'\subseteq S$ を列挙して $T'\subseteq(T\smallsetminus\{\min T\})$ のもののみ使う」のではなく直接 $T\smallsetminus\{\min T\}$ の部分集合を列挙することで、$\Theta(4^{|S|})$ 回ではなく $\Theta(3^{|S|})$ 回のループに減らすことができます。

概略

ここでは $T\smallsetminus \{\min T\}$ ではなく $S$ としていますが定数倍の違いしかないので問題ないでしょう（気になる読者は自分で手を動かしてみよう！）。 $$ \begin{aligned} \sum_{\emptyset\subseteq T\subseteq S} 2^{|T|} &= \sum_{i=0}^{|S|} \sum_{|T|=i, T\subseteq S} 2^{|T|} \\ &= \sum_{i=0}^{|S|} 2^i \cdot |\{T\in 2^S\mid |T| = i\}| \\ &= \sum_{i=0}^{|S|} 2^i \cdot \textstyle\binom{|S|}{i} \\ &= \sum_{i=0}^{|S|} \textstyle\binom{|S|}{i} \cdot 2^i \cdot 1^{|S|-i} \\ &= (2+1)^{|S|} = 3^{|S|}. \qquad\qed \end{aligned} $$ 実装例に関する詳細な説明はここではしません。

ところで、$B_n = |{\partition{\{0, 1, \dots, n-1\}}}|$ で定義される数列は Bell 数と呼ばれています。上記の DP の漸化式における各 $T'$ のサイズと選び方の通り数を考えることで、Bell 数に関する漸化式が導かれます。 $$ \begin{aligned} B_0 &= 1, \\ B_n &= \sum_{i=0}^{n-1} \textstyle\binom{n}{i} B_i. \end{aligned} $$

分割に関する例題としては次のようなものがあります。この問題は数え上げではなく最適化なので、実装上 $\sqcup$ を気にするのが面倒であれば、$\cup$ になるような実装をしても大丈夫でしょう。

atcoder.jp

正規括弧列

この節では、簡潔さのため $S\concat T$ や $(x)\concat S\concat (y)$ を単に $ST$、$xSy$ などと書くことにします。

$\gdef\openp{\text{\texttt{(}}}$ $\gdef\closep{\text{\texttt{)}}}$ サイズ $n$ の正規括弧列とは、$n$ 個の $\openp$ と $n$ 個の $\closep$ からなる列であって、次のいずれかの条件を満たすものを言います。

空列である
ある $0\lt k\lt n$ に対し、サイズ $k$ の正規括弧列 $S$ とサイズ $n-k$ の正規括弧列 $T$ が存在して $ST$ と書ける
ある $0\le k\lt n$ に対し、サイズ $k$ の正規括弧列 $S$ が存在して $\openp S \closep$ と書ける

いわゆる「バランスの取れた括弧列」「対応の取れた括弧列」「balanced parentheses」「regular parentheses」「well-formed parentheses」とか呼ばれるものです。短めのよい訳語があれば知りたいです。

サイズ $n$ の正規括弧列全体からなる集合を $P_n$ とすると、次の式が成り立ちます。 $$ \begin{aligned} P_0 &= \{\varepsilon\}, \\ P_n &= \bigsqcup_{i=0}^{n-1} {\{ \openp S \closep T \mid (S, T)\in P_i\times P_{n-i-1} \}}. \end{aligned} $$ 空でないとき先頭の文字は必ず $\openp$ になることに注意します。それに対応する $\closep$ の位置が各 $i$ ごとに異なることから、$\sqcup$ を使って問題ありません。

小さいケースの例は次の通りです。 $$ \begin{aligned} P_0 &= \{\varepsilon\}, \\ P_1 &= \{\openp\closep\}, \\ P_2 &= \{\openp\closep\openp\closep, \openp\openp\closep\closep\}, \\ P_3 &= \{\openp\closep\openp\closep\openp\closep, \openp\closep\openp\openp\closep\closep, \openp\openp\closep\closep\openp\closep, \openp\openp\closep\openp\closep\closep, \openp\openp\openp\closep\closep\closep\}, \\ \end{aligned} $$

さて、それはそれとして、長さ $n$ の列 $a = (a_0, a_1, \dots, a_{n-1})$ と（結合則を満たすとは限らない）適当な二項演算 $\odot$ を考えます。 $a$ の各要素への $\odot$ の適用させ方を列挙してみましょう。$n=4$ とします。

$(a_0\odot (a_1\odot (a_2\odot a_3)))$,
$(a_0\odot ( (a_1\odot a_2)\odot a_3))$,
$( (a_0\odot a_1)\odot (a_2\odot a_3))$,
$( (a_0\odot (a_1\odot a_2))\odot a_3)$,
$( ( (a_0\odot a_1)\odot a_2)\odot a_3)$.

$($ を $\openp$ に、$\odot$ を $\closep$ に置き換え、それ以外の文字を消すことで $P_3$ の各要素と対応づけられることがわかります*9。 $\odot$ はあくまで形式的な演算子であり、「その計算結果がたまたま同じになったら同一視する」といったようなことは考えないことにします。

$\gdef\paren#1{\mathop{\operatorname{paren}}{#1}}$ というわけで、この括弧のつけ方全体からなる集合を考えます。$a$ への括弧のつけ方全体からなる集合を $\paren{a}$ と書くことにします。次のことが成り立ちます。 $$ \begin{aligned} \paren{(x, y)} &= \{(x\odot y)\}, \\ \paren{a} &= \{(S\odot T)\mid ST = a\}. \end{aligned} $$ $\DP[\angled{l, r}] = \paren{(a_l, a_{l+1}, \dots, a_{r-1})}$ とすると、次のようにできます。 $$ \begin{aligned} \DP[\angled{i, i+1}] &= \{a_i\}, \\ \DP[\angled{l, r}] &= \bigcup_{i=l+1}^{r-1} \big\{ (S\odot T)\mid (S, T)\in \DP[\angled{l, i}]\times\DP[\angled{i, r}] \big\}. \end{aligned} $$

note: $(S\odot T)$ は $\openp S\closep T$ に対応しています。$\paren{a} = \DP[\angled{0, n}]$ です。

いわゆる区間 DP です。括弧列との対応づけを意識せずに覚えている人もいるのかもしれません？と思ったものの、連鎖行列積問題だったりスライムをくっつけるやつだったりが有名問題であることを考えると、全員がそういう認識を持っている気もしてきました。実際のところどうなのでしょうか。

サイズ $n$ の正規括弧列の個数は Catalan 数と呼ばれ、よく $C_n$ と書かれます。これは $C_n = \Theta(4^n/n^{1.5})$ であることが示せます。このことから、（要素数 $n$ の集合の部分集合が $\Theta(2^n)$ 個であることを考えると）最初に見たような先頭 $i$ 個目で 2 通りに分岐するような DP では全パターンを網羅できず、正規括弧列全体に関して考えたい問題では不適当であることがすぐにわかりそうです。あまりこうした指摘をしている解説は見ない気がしますね。

atcoder.jp

この問題は、実際には、固有の性質を用いることで区間 DP を使わず $O(n\log(n))$ 時間で解けることが知られています。

Catalan 数のオーダーについて

導出はここでは行いませんが、下記のように表せます。 $$ C_n = \frac{(2n)!}{n!\,(n+1)!}. $$ また、Stirling の近似公式から、下記が成り立ちます。 $$ n! = \Theta(\sqrt{n}\, (n/e)^n). $$ $(n+1)! = \Theta(n\cdot n!)$ であることに気をつけつつ、あとは手の運動です。 $$ \begin{aligned} C_n &= \Theta{\left(\frac{(2n)!}{n\cdot (n!)^2}\right)} \\ &= \Theta{\left(\frac{\sqrt{2n}\,(2n/e)^{2n}}{n\cdot (\sqrt{n}\,(n/e)^n)^2}\right)} \\ &= \Theta{\left(\frac{\sqrt{2n}\,(2n/e)^{2n}}{n^2 (n/e)^{2n}}\right)} \\ &= \Theta{\left(\frac{\sqrt{2n}\cdot 2^{2n}}{n^2}\right)} \\ &= \Theta(4^n/n^{1.5}). \end{aligned} $$

最後の行では定数倍の $\sqrt{2}$ を無視していることに注意してください。

順列 (polynomial-1)

順列について別のアプローチを考えてみます。 $\Lambda_n!$ について考えたいです。

順列 (exponential) の方では「順列を前から作っていき、どの要素を使ったかで分類する」という戦略に基づいており、集合を管理する必要がありました。ここでは、順列 $p$ を「$i$ や $p_i$ が小さい方から決めていく」という戦略を考えます。

$\{(0, p_0), (1, p_1), \dots, (n-1, p_{n-1})\}$ ($i\ne j\implies p_i\ne p_j$) なる集合は、$(p_0, p_1, \dots, p_{n-1})\in \Lambda_n!$ に対応します。よって、順列を直接考える代わりにこうした形式の集合を考えてもよいことになります。そこで、左右の要素が $i$ 未満かつ、左の要素が相異なり、右の要素も相異なる集合を考えます。 $$ S_i = \{S\in \Lambda_i^2\mid \ForallL{(k_l, k_r)\in S}{\ForallL{(k_l', k_r')\in S}{(k_l, k_r)\ne(k_l', k_r')\implies k_l\ne k_l'\wedge k_r\ne k_r'}}\}. $$ 小さい方から挙げると $$ \begin{aligned} S_0 &= \{\emptyset\}, \\ S_1 &= \{\emptyset, \{(0, 0)\}\}, \\ S_2 &= \{\emptyset, \{(0, 0)\}, \{(0, 1)\}, \{(1, 0)\}, \{(1, 1)\}, \{(0, 0), (1, 1)\}, \{(0, 1), (1, 0)\}\} \end{aligned} $$ などです。実際に手で書いてみると「結構すぐ大きくなりそうだな」という感覚を得やすいのでおすすめです。

さて、$\Lambda_n = \{S\in S_n\mid |S| = n\}$ なので、次のような DP を考えてみます。 $$ \DP[\angled{i, j}] = \{S\in S_i\mid |S| = j\}. $$

漸化式は次のようになります。 $$ \begin{aligned} \DP[\angled{i, 0}] &= \{\emptyset\}, \\ \DP[\angled{0, j}] &= \emptyset, \\ \DP[\angled{i, -1}] &= \emptyset, \\ \DP[\angled{i, j}] &= \DP[\angled{i-1, j}] \sqcup {} \\ % &\phantom{{}={}}\quad \bigsqcup_{S\in\DP[\angled{i-1, j-1}]} f_{=}(S, i) \sqcup {} \\ % &\phantom{{}={}}\quad \bigsqcup_{S\in\DP[\angled{i-1, j-1}]} f_{\lt}(S, i) \sqcup {} \\ % &\phantom{{}={}}\quad \bigsqcup_{S\in\DP[\angled{i-1, j-1}]} f_{\gt}(S, i) \sqcup {} \\ &\phantom{{}={}}\quad \bigsqcup_{S\in\DP[\angled{i-1, j-1}]} \big(f_{=}(S, i)\sqcup f_{\lt}(S, i)\sqcup f_{\gt}(S, i)\big) \sqcup {} \\ &\phantom{{}={}}\quad \bigsqcup_{S\in\DP[\angled{i-1, j-2}]} f_{\lessgtr}(S, i) \end{aligned} $$ ここで、各 $f_{\ast}(S, i)$ は次のもの全体からなる集合を返す関数です（数式での定義は後述します）。

$f_{=}(S, i)$：集合 $S$ に $(i-1, i-1)$ を追加してできる集合
$f_{\lt}(S, i)$：集合 $S$ に $(j, i-1)$ ($j\lt i-1$) を追加してできる集合
- ただし、左の要素が $j$ である要素は $S$ に含まれていないとする
$f_{\gt}(S, i)$：集合 $S$ に $(i-1, j)$ ($j\lt i-1$) を追加してできる集合
- ただし、右の要素が $j$ である要素は $S$ に含まれていないとする
$f_{\lessgtr}(S, i)$：集合 $S$ に $(j_l, i-1)$ と $(i-1, j_r)$ ($j_l, j_r\lt i-1$) を追加してできる集合
- ただし、左の要素が $j_l$ である要素、右の要素が $j_r$ である要素は $S$ に含まれていないとする

すなわち、次のように書けます。 $$ \begin{aligned} f_{=}(S, i) &= \big\{S\sqcup \{(i-1, i-1)\}\big\}, \\ f_{\lt}(S, i) &= \big\{S\sqcup \{(j, i-1)\}\mid j\in \Lambda_{i-1}, \ForallL{i'\in\Lambda_{i-1}}{(j, i')\notin S}\big\}, \\ f_{\gt}(S, i) &= \big\{S\sqcup \{(i-1, j)\}\mid j\in \Lambda_{i-1}, \ForallL{i'\in\Lambda_{i-1}}{(i', j)\notin S}\big\}, \\ f_{\lessgtr}(S, i) &= \big\{S\sqcup \{(j_l, i-1), (i-1, j_r)\}\\ &\phantom{{}={}} \qquad \mid (j_l, j_r)\in \Lambda_{i-1}^2, \ForallL{i'\in\Lambda_{i-1}}{(i', j_r)\notin S\wedge (j_l, i')\notin S}\big\}. \end{aligned} $$

求めるものは $$ % \Lambda_n! = \bigsqcup_{S\in\DP[\angled{n, n}]}{\{(p_0, p_1, \dots, p_{n-1})\mid \{(i, p_i)\}_{i=0}^{n-1}\in S\}} \Lambda_n! = \big\{(p_0, p_1, \dots, p_{n-1})\mid \{(i, p_i)\}_{i=0}^{n-1}\in \DP[\angled{n, n}]\big\} $$ です。

さて、$f_{\lt}(S, i)$ などの計算に関して補足です。各順列を陽に列挙したい（つまり、実質的に計算量を度外視できる）文脈であれば愚直にやればいいのですが、計算量を改善するために DP したい文脈ではそうはいきません。これに関しては projection や folding の性質との兼ね合いになりますが、たとえば要素数に関してであれば次のようにうまくいきます。 $$ \begin{aligned} |f_{=}(S, i)| &= 1, \\ |f_{\lt}(S, i)| &= i-1-|S|, \\ |f_{\gt}(S, i)| &= i-1-|S|, \\ |f_{\lessgtr}(S, i)| &= (i-1-|S|)^2. \end{aligned} $$ ここで $S\in\DP[\angled{i, j}]$ のとき $|S|=j$ であることに注意しましょう。つまり下記のようになります。 $$ \begin{aligned} |{\DP[\angled{i, 0}]}| &= 1, \\ |{\DP[\angled{0, j}]}| &= 0, \\ |{\DP[\angled{j, -1}]}| &= 0, \\ |{\DP[\angled{i, j}]}| &= |{\DP[\angled{i-1, j}]}| + {} \\ &\phantom{{}={}} \quad |{\DP[\angled{i-1, j-1}]}|\cdot(1 + 2\cdot(i-j)) + {} \\ &\phantom{{}={}} \quad |{\DP[\angled{i-1, j-2}]}|\cdot (i-j-1)^2. \end{aligned} $$

いわゆる箱根駅伝 DP と呼ばれているものになります。よくある「保留」という言い回しを意識しない形で定式化してみました。名前の由来は AOJ 2439 です。

atcoder.jp

順列 (polynomial-2)

他の方針で順列 $\Lambda_n!$ を列挙してみます。基本的な方針は「$i$ 回目の更新では $i$ 通りの要素を生成する」です。空列についてはいつも同じです。 $$\DP[0] = \{\varepsilon\}.$$ $i$ 回目の操作についてはいくつかの方法がありますが、概ね次の形式になるでしょう。 $$ \DP[i] = \bigsqcup_{P\in\DP[i-1]} f_i(P). $$

$f_i$ としては次のようなものが考えられます。$P = (p_0, p_1, \dots, p_{i-2})$ としておきます。 $$ \begin{aligned} % f_i^{\text{insert}}( (p_0, p_1, \dots, p_{i-2})) &= \{ f_i^{\text{insert-x}}(P) &= \{ (p_0, \dots, p_{j-1}, i-1, p_j, \dots, p_{i-2}) \mid j\in\Lambda_i \}, \\ f_i^{\text{swap}}(P) &= \{ (p_0, \dots, p_{j-1}, i-1, p_{j+1}, \dots, p_{i-2}, p_j) \mid j\in\Lambda_{i-1} \} \sqcup {} \\ &\phantom{{}={}}\quad\{P\concat (i-1)\}, \\ f_i^{\text{insert-y}}(P) &= \{ (p_0', \dots, p_{i-2}', i-1) \mid j\in\Lambda_i \}. \end{aligned} $$ ただし、$f_i^{\text{insert-y}}$ における $p_j'$ は次のように定義されるとします。 $$ p_j' = \begin{cases} p_j, & \text{if }p_j \lt i-1; \\ p_j + 1, & \text{if }p_j \ge i-1. \end{cases} $$ たとえば $$ \begin{aligned} &f_4^{\text{insert-x}}( (0, 2, 1)) = \{ \\ &\qquad (3, 0, 2, 1), \\ &\qquad (0, 3, 2, 1), \\ &\qquad (0, 2, 3, 1), \\ &\qquad (0, 2, 1, 3), \\ &\}, \\ &f_4^{\text{swap}}( (0, 2, 1)) = \{ \\ &\qquad (3, 2, 1, 0), \\ &\qquad (0, 3, 1, 2), \\ &\qquad (0, 2, 3, 1), \\ &\qquad (0, 2, 1, 3), \\ &\}, \\ &f_4^{\text{insert-y}}( (0, 2, 1)) = \{ \\ &\qquad (1, 3, 2, 0), \\ &\qquad (0, 3, 2, 1), \\ &\qquad (0, 3, 1, 2), \\ &\qquad (0, 2, 1, 3), \\ &\} \end{aligned} $$ です。

insert-x や insert-y の気持ちは、$(x, y) = (i, p_i)$ なる点をプロットするのに基づいています。よく挿入 DP などと呼ばれています。

何かしらの個数を固定したときの順列を数え上げたい文脈では、bit DP をせずに $n^{O(1)}$ 個に分類できないか考えてみましょう（bit DP を経由して考察するのも悪くはないと思います）。問題の条件や projection・folding との兼ね合いで、どのような $f_i$ と相性がよいかを考えるとよさそうです。

atcoder.jp

ricky-pon.hatenablog.com

階乗・分割 (polynomial)

集合 $S$ を $k$ 個の円順列に分けたもの全体からなる集合を $[S]_k$、$k$ 個の集合に分けたもの全体からなる集合を $\{S\}_k$ と書くことにしてみます。$|[S]_k| = {|S|\brack k}$, $|\{S\}_k| = {|S|\brace k}$ に由来する記法です。これもあまり見ない気がしますがよいでしょう。それぞれの要素数は、第一種 Stirling 数、第二種 Stirling 数と呼ばれています。

$a_0\stackrel{p}{\mapsto} a_1, \dots, a_{m-2}\stackrel{p}{\mapsto} a_{m-1}, a_{m-1}\stackrel{p}{\mapsto}a_0$ のような順列 $p$ を円順列といい、$[a_0, a_1, \dots, a_{m-1}]$ と書くことにします。特に、$[a_0]$ は $a_0\stackrel{p}{\mapsto} a_0$ を意味します。

$[S]_k$ や $\{S\}_k$ の例としては次のようになります。 $$ \begin{aligned} & [\Lambda_4]_2 = \{ \\ & \qquad \{[0, 3, 2], [1]\}, \\ & \qquad \{[0, 2, 3], [1]\}, \\ & \qquad \{[0, 2], [1, 3]\}, \\ & \qquad \{[0, 3], [1, 2]\}, \\ & \qquad \{[0], [1, 3, 2]\}, \\ & \qquad \{[0], [1, 2, 3]\}, \\ & \qquad \{[0, 3, 1], [2]\}, \\ & \qquad \{[0, 1, 3], [2]\}, \\ & \qquad \{[0, 1], [2, 3]\}, \\ & \qquad \{[0, 2, 1], [3]\}, \\ & \qquad \{[0, 1, 2], [3]\}, \\ & \}, \\ & \{\Lambda_4\}_2 = \{ \\ & \qquad \{\{0, 2, 3\}, \{1\}\}, \\ & \qquad \{\{0, 2\}, \{1, 3\}\}, \\ & \qquad \{\{0, 3\}, \{1, 2\}\}, \\ & \qquad \{\{0\}, \{1, 2, 3\}\}, \\ & \qquad \{\{0, 1, 3\}, \{2\}\}, \\ & \qquad \{\{0, 1\}, \{2, 3\}\}, \\ & \qquad \{\{0, 1, 2\}, \{3\}\}, \\ & \}. \end{aligned} $$

ここで考えている円順列の集合は、各々の要素に重複がないので、全体で一つの順列と見なすことができることに注意しておきます。たとえば、$\{[0, 3, 1], [2, 4]\}$ は $(3, 0, 4, 1, 2)$ に相当します。

漸化式を書くにあたって、順列に対する操作に関する記法を導入しておきます。 $p_x$ が定義された $x$ と $p_y$ が定義されていない $y$ に対して、$p\veebar (x\mapsto y)$ は次の対応づけからなる順列とします。

$x\mapsto y$,
$y\mapsto p_x$,
$z\mapsto p_z$ ($z\ne x\wedge z\ne y$).

また、$p_x$ が定義されていない $x$ に対して $p\sqcup [x]$ は次の対応づけからなる順列とします。

$x\mapsto x$,
$y\mapsto p_y$ ($y\ne x$).

この記法を用いて、漸化式は次のように書けます。 $$ \begin{aligned} [\Lambda_0]_0 &= \{\emptyset\}, \\ [\Lambda_0]_k &= \emptyset, \\ [\Lambda_n]_0 &= \emptyset, \\ [\Lambda_n]_k &= \{p\sqcup [n-1]\mid p\in[\Lambda_{n-1}]_{k-1}\} \sqcup {} \\ &\phantom{{}={}}\quad \bigsqcup_{p\in[\Lambda_{n-1}]_k} {\{ p\veebar (j\mapsto n-1) \mid j\in \Lambda_{n-1} \}}. \end{aligned} $$ 集合への分割の方は次の通りです。 $$ \begin{aligned} \{\Lambda_0\}_0 &= \{\emptyset\}, \\ \{\Lambda_0\}_k &= \emptyset, \\ \{\Lambda_n\}_0 &= \emptyset, \\ \{\Lambda_n\}_k &= \{p\sqcup \{n-1\}\mid p\in\{\Lambda_{n-1}\}_{k-1}\} \sqcup {} \\ &\phantom{{}={}}\quad \bigsqcup_{p\in\{\Lambda_{n-1}\}_k} {\{ (p\smallsetminus S)\sqcup(S\sqcup \{n-1\})\mid S\in p \}}. \end{aligned} $$

これらの漸化式から、Stirling 数に関する漸化式も導かれます。

$$ \begin{aligned} \textstyle{n\brack k} &= \textstyle{n-1\brack k-1} + (n-1)\,\textstyle{n-1\brack k}, \\ \textstyle{n\brace k} &= \textstyle{n-1\brace k-1} + k\,\textstyle{n-1\brace k}. \end{aligned} $$

また、$\bigsqcup_{k=0}^n {[\Lambda_n]_k} = \Lambda_n!$ や $\bigsqcup_{k=0}^n {\{\Lambda_n\}_k} = \partition{\Lambda_n}$ などが成り立ちます。

矩形領域

順列 $p\in\Lambda_n!$ に対して、点群 $S = \{(i, p_i) \mid i\in\Lambda_n\}$ を x-y 平面にプロットすることを考えます。このとき、ある点 $(x, y)\in \Lambda_n^2$ の左下領域 $$ T_{(x, y)} = \{(x', y')\in S \mid x'\le x\wedge y'\le y\} $$ を考えます。 $p_i = 0$ なる $i$ に対して $T_{(i, p_i)} = \{(i, p_i)\}$ となるのは明らかでしょう。そこで、$y$ 座標の昇順に漸化式を立てることを考えます*10。

便宜上、$q_{p_i} = i$ なる順列 $q$（すなわち $p$ の逆順列）を定義しておきます。上記のことは $T_{(q_0, 0)} = \{(q_0, 0)\}$ と言い換えられます。

さて、漸化式は次のようになります。 $$ \begin{aligned} T_{(x, 0)} &= \emptyset && (x\lt q_0), \\ T_{(x, 0)} &= \{(q_0, 0)\} && (x\ge q_0), \\ T_{(x, y)} &= T_{(x, y-1)} && (x\lt q_y), \\ T_{(x, y)} &= T_{(x, y-1)}\sqcup\{(q_y, y)\} && (x\ge q_y). \end{aligned} $$

$y$ を固定したときの処理としては、$q_y$ を境として左側は何もせず、右側は $(q_y, y)$ を追加するだけですので、区間に対する更新ができるデータ構造を用いることで高速に処理が可能です（$y$ ごとに $T$ を使い回すイメージです）。

あるいは、 $$ a_{(x, y)} = \begin{cases} \emptyset, & \text{if }p_x \lt y; \\ \{(x, p_x)\}, & \text{if }p_x \ge y \end{cases} $$ のような配列 $a_{(x, y)}$ を管理することで、区間 fold ができるデータ構造を用いることも可能です。 $T_{(x, y)} = \bigsqcup_{x'\le x} a_{(x', y)}$ ということです。

このように、いずれかの座標の昇順（や降順）に処理を進めることで、条件の不等式を処理順に言い換えるテクは平面走査と呼ばれています。元々は計算幾何学側の用語のはずで、英語だと sweeping と呼ばれていたと思います。処理順に沿って動く線（今回の例であれば、$x$ 座標に対して平行な、$y$ 軸正方向に動く線）を走査線と呼びます。走査線は座標軸に平行とは限らず、たとえば初めは半直線 $OX$ から開始して反時計回りに回転するようなケースもあります。また、今回は $x'\le x$ のように片側が閉じていない区間でしたが、$x_l\le x'\le x_r$ のような処理を行う問題も頻出です（DP だと認識することは少ないかもしれません）。

このテクで解ける頻出問題としては、LIS や転倒数などがあります。

atcoder.jp

部分集合 + 区間

$[0, n)$ に含まれる非空な区間全体からなる集合 $A_n$ を考えます（境界は整数とします）。 $$ A_n = \{[l, r) \mid (l, r)\in\Lambda_n, l\lt r\}. $$ これの部分集合 $S \in 2^{A_n}$ が与えられるとして、それに関する問題を考えます。

$I\in 2^{\Lambda_n}$ に対して以下のような集合を返す関数を考えます。 $$ f_S(I) = \{x\in S\mid \ExistsL{i\in I}{i\in x}\}. $$

直感的な説明としては、選んだいくつかの座標で区間を串刺しにするとき、実際に串が刺さる区間を返すものです。以下に図も示します。[---) が区間、^ が串です。

  0  1  2  3  4  5  6  7  8
  ^  ^                 ^         # S = {
  [--------)           ^         #   [0, 3),
  ^  ^  [--------------)         #   [2, 7),
  ^  [-----------)     ^         #   [1, 5),
  ^  ^              [-----)      #   [6, 8),
  ^  ^                 ^         # }
  ^  ^                 ^         # I = {0, 1, 7}

$S = \{[0, 3), [2, 7), [1, 5), [6, 8)\}$ と $I = \{0, 1, 7\}$ です。$f_S(I) = \{[0, 3), [1, 5), [6, 8)\}$ となります。

さて、次の集合を考えたいです。すなわち、全部の刺し方における区間の選ばれ方を列挙したいです。 $$ % \{ f_S(I) \mid I\in 2^{\Lambda_n} \}. \bigcup_{I\in 2^{\Lambda_n}} f_S(I). $$

次のような DP を考えてみましょう。 $$ \begin{aligned} % % \DP[\angled{i, j}] &= \big\{f_{\{[l, r)\in S\mid r\le i\}}(I) \\ % \DP[\angled{i, j}] &= \big\{f_{S\cap A_i}(I) \\ % &\phantom{{}={}} \qquad \mid I\in 2^{\Lambda_i}, \max {(\{i+1\mid i\in I\}\sqcup \{0\})} = j\big\}. \DP[\angled{i, j}] &= \big\{f_{S\cap A_i}(I) \mid I\in 2^{\Lambda_i}, \max {(\{i+1\mid i\in I\}\sqcup \{0\})} = j\big\}. \end{aligned} $$ 区間は右端が $i$ 以下のもの、刺し方は最大値が $j-1$（$j=0$ のときは刺さない）のもので絞っています*11。欲しいのは $\bigcup_{j=0}^n {\DP[\angled{n, j}]}$ です。$\sqcup$ は難しかったです。また、$j$ の範囲は $0\le j\le i$ とします。

さて、漸化式は次のようになります。簡潔さのため、$S_i = \{[l, r) \in S\mid r = i\}$ と定義しておきます。 $$ \begin{aligned} \DP[\angled{0, 0}] &= \{\emptyset\}, \\ \DP[\angled{i, i}] &= \bigcup_{j=0}^{i-1}{\{T\sqcup S_i\mid T\in\DP[\angled{i-1, j}]\}}, \\ \DP[\angled{i, j}] &= \{ T\sqcup\{[l, r)\in S_i\mid l\lt j\} \mid T\in\DP[\angled{i-1, j}] \}. \end{aligned} $$ $\DP[\angled{i, \ast}]$ では、$\DP[\angled{i-1, \ast}]$ と比べて「右端が $i$ の区間の集合」と「座標 $i-1$ で串を刺すかどうかの分岐」の考慮が増えます。 $i-1$ で串を刺す場合は、新しく増えた（右端が $i$ の）区間たちは選ばれます。一方、$i-1$ で串を刺さない場合は、新しく増えた区間のうち $j-1$ で刺されるもの（すなわち $l\lt j$ のもの）だけが選ばれます。

ここからは projection・folding を行うことを前提とした話になります。さらに、$\DP[\angled{i-1, \ast}]$ と $\DP[\angled{i, \ast}]$ の違いについて注目しましょう。まず、$\DP[\angled{i, i}]$ に関しては $\DP[\angled{i-1, 0}], \dots, \DP[\angled{i-1, i-1}]$ のそれぞれに $S_i$ を合わせたものになります。projection・folding の文脈で言えば、 $$ \bigodot_{j=0}^{i-1} {\{f(T\sqcup S_i)\mid T\in\DP[\angled{i-1, j}]\}} $$ を高速に計算できればうれしいです。 $\DP[\angled{i, j}]$ に関しては次の通りです。

$\DP[\angled{i, j}]$ に $\DP[\angled{i-1, j}]$ をコピーする。
$[l, r)\in S_i$ なる各区間に対して次の更新を行う。
- $l\lt j\lt i$ なる各 $\DP[\angled{i, j}]$ に対して、$[l, r)$ を追加したときの値で計算し直す。

これも projection・folding との兼ね合いですが、そういうデータ構造を用いることで可能な状況が多そうです。 $\DP[\angled{i, i}]$ の方の更新もまとめて $l\lt j\le i$ の区間を更新する方が実装が簡潔になるかもしれません。

ところで、$\DP[\angled{i-1, \ast}]$ を $\DP[\angled{i, \ast}]$ にコピーする部分に関しては、（後から $\DP[\angled{n, \ast}]$ 以外を使いたい状況でなければ）$\DP[\ast]$ だけの一次元の配列だということにして使い回すことで、何もせずに済みます。これにより、$O(n)$ 回の区間 fold と $O(|S|)$ 回の区間更新で達成できます。ただし、$\bigodot {\{f(T\sqcup S_i)\}} = (\bigodot f(T))\odot f(S_i)$ などのよい性質があって、$S_i$ を追加したときの値が容易に計算できることが前提となっています。

このような前提の下で、DP 配列を使い回して in-place に更新を行うテクは、インライン DP とか in-place DP とか実家とか呼ばれています。このテク自体はこの節で考えたようなテーマに固有のものではありません。平面走査のところでも使いましたね。

topcoder-g-hatena-ne-jp.jag-icpc.org

atcoder.jp

その他

グリッドの左上から右下に、右または下への移動を繰り返す経路の総数を考える問題があります。これは、各マスに到達する経路の集合を持っていると見なせます。

EDPC Z のような、いくつかのマスを経由してゴールに到達するまでのコストの最小値を求める問題があります。これは、経由するマスの部分集合を考えていると見なせます。マス $j$ から $i$ への移動のコストが $j$ 以前の経路によらないことから同一視して状態数を減らしています。EDPC Z ではさらに CHT などで高速化をします。

いくつか問題を挙げるので考えてみるとよいでしょう。解説をしながら挙げたものも含みます。

実装例

Rust での実装例です。計算量度外視の回なので、競プロ用に直接役立つことは少ないかもしれません。記事中の記述が正しいことの verify 用としての役割程度のものです。

あとがき

つかれました。

初心者の頃、数え上げ DP をするときに具体的な対象がイメージできておらずに MECE になっていない漸化式を立てたりしていた記憶が蘇ってきたので、陽に列挙することで意識してみようという企画でした。最近始めて DP に悩んでいる人たちはどのようにイメージして考察・実装しているのでしょうね。

正規括弧列の節でも述べましたが、考えようとしている対象の個数と DP で列挙できる個数に乖離がないかを意識してみるのも大事そうです。たとえば、Fibonacci 数列の節では $\{1, 2\}^{\star}$ の列で総和が $n$ のものを考えましたが、$\{1, 2, \dots, n\}^{\star}$ の列で総和が $n$ のものはどの程度の個数になるかイメージがつくでしょうか？

この記事の内容は、その手の構造で DP をしたいとき用の「ライブラリ」のような立ち位置であるものの直接 #include use import などで使い回しにくいような内容になっているような気がします（できなくもないものもあるかとは思いますが）。とはいえ考察の引き出しとしては有用だと思うので、何らかの方法で整理しておくといいのかなと思います。

また数式多めの記事になってしまった気がする（それ自体は別に悪いことではなくて、ある種当然だとも思います）ので、数式が苦手な人が数式を得意になってくれるような解説も書けたらいいなと思いつつ、えびちゃん向きではないという気もします。苦手な人というのはワンパターンではないと思うので、「この記事読んでね」でうまくいきにくいような気がしていて、一対多でやりにくい気がしているんですよね。競プロで出てくる文脈の数式っていわゆる中学・高校数学は必ずしも前提としないので、「数式多めの競プロ解説を読めるようになる」とかを目標にした教育コンテンツというのもありかもしれません？

当初の予定ではもっと軽く書く予定だったんですが、気づいたらボリューム多めになってしまいました。 $\KaTeX$ の数式の記述も含めると 5 万文字を超えてしまっています。ボリューム多めの記事がお好みの方は下記もおすすめです。

rsk0315.hatenablog.com

もうこれ 2 年前の記事らしいです。気が向いたらまたなにか書こうと思います。

おわり

おわりです。おつかれさまでした。

*1:文字集合はアルファベットとも呼ばれます。形式言語理論や文字列界隈の用語です。たまたま集合として一致することはありますが、いわゆる [A-Za-z] を指す用語ではないので注意しましょう。

*2:$\lambda$ で表す文献もあると思います。空集合を $\emptyset$ ではなく $\{\}$ と書くように、空列を $()$ で表す状況もありそうです。

*3:Haskell などの関数型言語だったり、純粋関数型データ構造界隈だったりで使われている記法という印象があります。

*4:たぶんこれは一般的な記法ではないですが、$2^{|S|}$ のような記法同様に $|S!| = |S|!$ が成り立つことから、あまり非直感的な記法でもないでしょう。

*5:最悪時 $\Theta(n^2)$ 時間になるハッシュテーブルではどうなるか？こちらは読者に任せます。

*6:実際には $|\Sigma|$ ではなく、$\Sigma$ のうち $S$ に含まれる要素の種類数で抑えられそうです。

*7:アルファベットサイズ $|\Sigma|$ は常に定数と見なせるわけではありません。「26 は比較的大きめだから定数ではない」のような主張はナンセンスで、値の大小自体は定数性とは無関係です。あくまで問題設定などによります。

*8:$A=0$ の場合は $n$ はどうしましょうか。$-\infty$ 桁と見なす宗派の人もおられそうです。

*9:逆向きの対応づけはちょっと考える必要がありますが、適切に行うことで可能です。

*10:$x$ 座標の昇順などでもよいです。好みの問題であることが多い気がします。

*11:$[0, i)$ に含まれているような区間だけを考えたいので右端を $i$ 以下としています。このような状況では、各区間を右端の昇順でソートしておくとよいことが多そうです。

えびちゃんの日記

えびちゃん（競プロ）の日記です。

各種 DP を愚直な形で考えてみる

導入

定義や記法など

集合の記法に関して

肩慣らし

Fibonacci 数列

典型的な構造

部分集合

順列 (exponential)

組合せ

部分列 (1)

部分列 (2)

非負整数 (1)

非負整数 (2)

Excel 進法

分割 (exponential)

正規括弧列

順列 (polynomial-1)

順列 (polynomial-2)

階乗・分割 (polynomial)

矩形領域

部分集合 + 区間

その他

実装例

関連資料

あとがき

おわり