桁DPを雰囲気で書くのをやめたい
この記事を読むのに必要な知識: ふつうの桁DPなら雰囲気で書ける程度の桁DPの理解、他
TL;DR
- 桁DPはひとまず制約 \(n \lt K\) を忘れると考えやすいよ
- 境界と内部のイメージを持っておくと考えやすいよ
桁DPとは何か
桁DPとは、自然数を \(10\) 進数展開して各桁ごとに決定していく形などの動的計画法のことである。 部分的に構成された列を適切な同一視によりまとめたものが状態となり、そのような状態に含まれる列の個数などが動的計画法をする関数の値となる。 主に「自然数 \(n\) に対する条件 \(\varphi(n)\) が与えられる。自然数 \(K \ge 0\) が与えられるので、自然数 \(n \lt K\) であって \(\varphi(n)\) を満たすものの数を求めよ」という形の数え上げ問題を解くために用いられる。 ただし、条件 \(\varphi(n)\) は「自然数 \(n\) を \(D\) 進数展開した結果の列 \(a\) の連続部分列 \(b\) であって長さ \(L\) なものすべてに対して \(\psi(b)\) が成り立つ」という形の条件であるいはとする。
数え上げの問題の場合が典型的だが、 「自然数 \(n\) に対する条件 \(\varphi(n)\) が与えられる。自然数 \(K \ge 0\) が与えられるので、自然数 \(n \lt K\) であって \(\varphi(n)\) を満たす最大の自然数を求めよ」という最大値の問題や、 「自然数 \(n\) に対する関数 \(f(n)\) が与えられる。自然数 \(K \ge 0\) が与えられるので、自然数 \(n \lt K\) のそれぞれに対し \(f(n)\) を考えその総和を求めよ」という総和の問題として現われる場合もある。
数え上げの問題の場合の説明
桁DPは次の \(2\) ステップに分かれている。
- 上限 \(K\) の制約を忘れて、勝手な自然数 \(l\) に対し、自然数 \(n \lt D^l\) であって (つまりその \(D\) 進数展開された列 \(a\) の長さが \(l\) 以下の自然数であって) 条件 \(\varphi(n)\) を満たすものを数える方法を準備する。
- 上限 \(K\) の制約を考慮に入れ、\(K\) の桁数を \(l = \lfloor \log_{10} K \rfloor + 1\) として (1.) を用いて答えを求める。
以下では自然数 \(n\) を扱っていることを忘れ、その \(D\) 進数展開された列 \(a\) のみを考える。 \(\varphi(n)\) によってはその他の変形を用いてさらに効率良く計算できる場合があるが、最も基本的な形のみを説明する。
(1.) 制約 \(n \lt K\) を忘れた場合について
要素が \(0, 1, 2, \dots, D - 1\) からなる長さ \(l\) の列を前の要素から順に構成していくことを考える。 その構成過程であるような、前から \(i \le l\) 個の要素を埋めた列 \(a\) のことを「長さ \(i\) の切片 1」と呼ぶことにする。 長さ \(k\) の切片は列の全体であるので長さ \(k\) の列そのものである 2。 数えたいのは \(\varphi(a)\) を満たすような列であるため、\(\varphi\) を切片にまで拡張しておく。 列でない切片 \(a\) に対して \(\varphi(a)\) と書いたときは「\(a\) のすべての連続部分列 \(b\) であって長さ \(L\) のものが \(\psi(b)\) を満たす」ことを意味するとする。
長さ \(i\) の切片 \(a = (a_0, a_1, \dots, a _ {i - 1})\) であって \(\varphi(a)\) を満たすようなもの \(a\) を数えていく。 これらを個別に数えるのは無駄であるので、\(\varphi(n)\) の性質を使って、末尾の \(L - 1\) 要素が一致する切片をまとめて扱う。 関数 \(f(i, c_0, c_1, \dots, c _ {L - 2})\) を「長さ \(i\) の切片 \(a\) であってその末尾が \((c_0, c_1, \dots, c _ {L - 2})\) であり \(\varphi(a)\) を満たすものの数」と定義する。 その漸化式の基本的な形は
\[f(i + 1, c_1, \dots, c _ {L - 2}, c _ {L - 1}) = \sum _ {c_0 \lt D ~ \land ~ \psi(c_0, \dots, c _ {L - 1})} f(i, c_0, c_1, \dots, c _ {L - 2})\]となる。 そして
\[\sum _ {c_0 \lt D} \sum _ {c_1 \lt D} \dots \sum _ {c_ {L - 2} \lt D} f(l, c_0, c_1, \dots, c _ {L - 2})\]は (1.) の問題に対する答えである。 これは $\psi(c)$ の計算が $O(T)$ であるときは $O(l D^L T)$ の計算量で求まる。
(2.) 制約 \(n \lt K\) を考慮する場合について
上限 $K$ の制約が加わった。 すると切片 \(a\) を、その対応する自然数 \(n\) と条件 \(K\) との関係で分類する必要が発生する。
- 「それ以降をどう埋めても \(K\) 未満であるような切片」を内部切片あるいは内部列2と呼び、
- 「それ以降の埋め方によっては \(K\) 未満にも \(K\) 以上にもなるような切片」を境界切片あるいは境界列3と呼び、
- 「それ以降をどう埋めても \(K\) 以上であるような切片」を外部切片あるいは外部列4と呼ぶことにする。
長さ $k$ の切片は \(L\) 未満か \(L\) 以上かが自明に確定しているため、必ず外部切片か内部切片のいずれかである。 境界切片は \(L\) の \(D\) 進数展開の (真の) prefix であるような列に他ならず、その長さ \(i\) が固定されれば境界切片は高々ひとつに定まる。
(1.) で考えた関数 \(f\) を上限 \(K\) の制約を加えて修正する。 内部切片のみを数えるようにして、 \(g(i, c_0, c_1, \dots, c _ {L - 2})\) を「長さ \(i\) の内部切片 \(a\) であってその末尾が \((c_0, c_1, \dots, c _ {L - 2})\) であり \(\varphi(a)\) を満たすものの数」と定義する。 問題の答えが
\[\sum _ {c_0 \lt D} \sum _ {c_1 \lt D} \dots \sum _ {c_ {L - 2} \lt D} g(l, c_0, c_1, \dots, c _ {L - 2})\]であるというのは (1.) における \(f\) と変わらない。 漸化式の基本的な形は、境界切片から内部切片へ移行してくる部分を考慮して
\[g(i + 1, c_1, \dots, c _ {L - 2}, c _ {L - 1}) = \left( \sum _ {c_0 \lt D ~ \land ~ \psi(c_0, \dots, c _ {L - 1})} g(i, c_0, c_1, \dots, c _ {L - 2}) \right) + p(i + 1, c_1, \dots, c _ {L - 2}, c _ {L - 1})\]となる。 ただし、上限 $K$ の $D$ 進数展開の上から $i \ge 0$ 桁目を $K_i$ と書くこととして、境界切片からの影響 \(p(i + 1, c_1, \dots, c _ {L - 2}, c _ {L - 1})\) は
\[c_1 = K _ {i - L + 2} ~ \land ~ c_2 = K _ {i - L + 3} ~ \land \dots \land ~ c _ {L - 2} = K _ {i - 2} ~ \land ~ c _ {L - 1} \lt K_i\]が真どうかに従って \(0\) か \(1\) をとる関数である。 計算量は (1.) において \(l = \log L\) としたものと等しく、 $O(D^L T \log K)$ である。
総和の問題の場合の説明
数え上げの問題の場合とほとんど同様である。
最大値の問題の場合の説明
\(\log K\) が小さい場合
答えを二分探索することにすると数え上げの問題に帰着される。
\(\log K\) が小さいとは限らない場合
補足
数え上げの問題の場合を基本とする。
区間 \([a \cdot 10^b, (a + 1) \cdot 10^b)\) の値が分かっている場合
\(\varphi(n)\) の性質がとてもよい場合は動的計画法は不要になる。 「区間 \([a \cdot 10^b, (a + 1) \cdot 10^b)\) に含まれる自然数 \(n\) であって \(\varphi(n)\) を満たすものの数」などが直接に計算できるとする。 すると制約 \(n \lt K\) を忘れた場合は自明になり、制約 \(n \lt K\) を考慮する場合も境界 \(K\) に沿って足し合わせるだけでよくなる。 最大値の問題の場合は貪欲法をすることになる。
境界列に関する表
内部列に関する関数 $g$ の漸化式中における、境界列からの影響 \(p(\dots)\) について考える。 この $p(\dots)$ はほとんどの場合に $0$ である。 実装においては直接 \(K\) に従って配るDPの形を用いるとよい。
「長さ \(i\) の境界切片 \(a\) であってその末尾が \((c_0, c_1, \dots, c _ {L - 2})\) であり \(\varphi(a)\) を満たすものの数」のような関数 \(h(i, c_0, c_1, \dots, c _ {L - 2})\) を考えてこれを管理するという実装方法も考えられる。 実装の際にはこちらを用いても問題はない。 しかし内部の場合 \(g\) と境界の場合 \(h\) は明確に異なる性質を持つ関数であるので、「\(K\) より小さいかどうかのフラグ」などとしてひとつの配列にまとめてしまうのはあまり行儀のよい実装とは言えないだろう。 加えて、考察の際はこの \(h\) を考える必要はほとんどないことにも注意したい。
制約 \(n \lt K\) と制約 \(n \le K\)
上記の説明では \(n \lt K\) という形の制約を考えていた。 これがもし \(n \le K\) という形であっても同様に扱えるだろうか？ その答えは「変わらず扱える」である。 制約を \(n \lt K\) だと思って解き、最後に \(\varphi(K)\) かどうか判定して真ならば \(1\) を足せばよい。
文字種 $D$
ここまで「自然数 $n$ を $D$ 進数展開した結果の列 $a$」と表現して話を進めてきた。 しかし $D = 10$ や $D = 2$ に限る必要はない。 文字列のために $D = 26$ を考えたり、一般の数列に対し $D = 1000$ を考えたりしてよい。
そのような問題の例として「小文字 alphabet からなる文字列であって、辞書順で \(S\) より小さく、部分文字列として \(T_0, T_1, \dots, T _ {k - 1}\) を含まないようなものの数を求めよ」などが考えられる。 \(L = \max \{ \lvert T_i \rvert \mid i \lt k \}\) とおいて計算量 \(O(26^L \lvert S \rvert)\) で解ける。
履歴長 $L$
履歴長 \(L\) は条件 \(\varphi(n)\) から定まる数値で、どれくらいの長さの列を記憶しておけばよいかを表す。
\(L = 3\) な問題の例として、たとえば「自然数 \(n \lt K\) であって、その \(10\) 進数展開を考えたときどの連続する長さ \(3\) の区間も重複した数字を含まない (ただし \(0\) の重複は許す) ようなものの数を求めよ」という問題がある。 \(n = 12321\) は連続部分列 \(232\) 内に \(2\) が重複しているので数える対象でないが、\(n = 12314\) は数える対象とする。 計算量は \(O(D^L \log K)\) である。
列に計算量は必ずしも \(D^L\) かかるとは限らない。 たとえば「自然数 \(n \lt K\) であってその \(10\) 進数展開に同じ数字が \(L\) 個連続するような箇所がないものの数を求めよ」のような問題を考える。 これは履歴長が \(L\) であるが、最後の数字 \(d \lt D\) とそれが何回繰り返されたか \(l \lt L\) のみを持っての DP が可能で、その計算量は \(O(DL \log K)\) に落とせる。
境界列の唯一性
境界列は長さ \(i\) を固定すると高々ひとつであった。 しかし応用的な桁DPの場合は必ずしもそうでない。 たとえば「自然数の対 \((a, b)\) であって \(a ~ \mathrm{bitor} ~ b \lt K\) を満たしかつ \(\mathrm{popcount}(a) = \mathrm{popcount}(b)\) なものの数を求めよ」などがその例である。 この場合は境界列の個数を内部列と同様に管理する必要がある。
下限の制約
上限のみでなく下限の制約も付いた「$\dots$ 自然数 \(n\) であって \(A \le n \lt B\) かつ \(\varphi(n)\) を満たすものの数を求めよ」という形の問題も考えられる。 これを求めるには制約 \(n \lt B\) のみで解いた結果の個数から、\(n \lt A\) という制約で解いた結果の個数を引けばよい。