AtCoder Grand Contest 024 E - Sequence Growing Hard

公式解説とだいたい同じ考察を辿ったんですが、最後の計算で違うことをしたので書いておきます。

解法

要素を挿入して、辞書順でより大きくなる条件は

長さ $i$ の数列に1つ要素を挿入して、辞書順でより大きい長さ $i+1$ の数列を作る方法は、ある要素の手前に、その要素より大きな要素を挿入することです。末尾に追加する場合もありますが、数列の末尾には常に $0$ があるという風に思っておけば統一的に扱えます。

例えば使える数字が $1, 2, 3$ であり、 $\lbrace 2, 2, 1\rbrace$ という長さ3の数列から条件を満たす長さ4の数列を作るには

1番目の要素である $2$ の前に $3$ を挿入する（ $\lbrace 3, 2, 2, 1\rbrace$ ）
2番目の要素である $2$ の前に $3$ を挿入する（ $\lbrace 2, 3, 2, 1\rbrace$ ）
3番目の要素である $1$ の前に $2$ または $3$ を挿入する（ $\lbrace 2, 2, 2, 1\rbrace, \lbrace 2, 2, 3, 1\rbrace$ ）
擬似的な4番目の要素である $0$ の前に $1, 2, 3$ のいずれかを挿入する（ $\lbrace 2, 2, 1, 1\rbrace, \lbrace 2, 2, 1, 2\rbrace, \lbrace 2, 2, 1, 3\rbrace$ ）

とすることで漏れなくダブりなく列挙することができます。この作り方だと、 $\lbrace 2, 2, 2, 1\rbrace$ のように同じ値が連続しているところにさらに同じ値を足すような場合でも正しく扱えるのがポイントです。

以降は $0$ も数列の要素として数えることにします。つまり $\lbrace 2, 2, 1\rbrace$ という長さ3の数列は、 $\lbrace 2, 2, 1, 0\rbrace$ という長さ4の数列として扱います。

位置関係を無視して挿入要素だけの列に

先ほど見た条件から、数列のある位置にある値を挿入できるかどうかはその直後の値との前後関係のみによって決まり、数列の中での位置や他の要素とは全く関係がないことが分かります。このことから数列の位置関係は無視してよくて、例えば

$\lbrace 0\rbrace \to \lbrace 1, 0 \rbrace \to \lbrace 2, 1, 0\rbrace \to \lbrace 2, 1, 2, 0\rbrace \to \lbrace 2, 3, 1, 2, 0\rbrace$

という数列の組は、単に各操作で挿入された要素だけを並べて

$0 \to 1 \to 2 \to 2 \to 3$

として考えても構いません。これらの要素が数列内でどう並んでいようと、このように作られた数列に例えば要素 $2$ を挿入するときには、入れられる場所は $0$ の直前と $1$ の直前の2箇所です。

これまで「数列」と呼んできたものと混ざらないように、この挿入された要素を並べたものは「操作列」と呼ぶことにします。

実際にこの操作列によって実現できる数列の組がいくつあるかは、各操作での挿入箇所の候補数（つまり既に追加されている自分より小さい要素の個数）を全て掛け合わせることで求められます。上記の例では $1\times 2\times 2\times 4 = 16$ 通りあります。

挿入DPっぽい何か

次のステップですが、挿入DPっぽいことをします。つまり先程の操作列を数えていくにあたって、整数を $1$ から $K$ まで順番に入れていきます。その過程で、挿入箇所の候補数による係数も処理していきます。

次のようなDPを考えます。

$dp\lbrack i \rbrack\lbrack j\rbrack =$ 整数を $1$ から $i$ まで入れ終わって、現時点での長さが $j$ であるような操作列の通り数。ただしそれまでに発生した挿入箇所の候補数による係数は既に掛けられているものとする。

$dp\lbrack i-1 \rbrack\lbrack j\rbrack$ から $dp\lbrack i \rbrack\lbrack j+k\rbrack$ へ遷移するときの係数を考えます。つまり $i-1$ 以下の数からなる長さ $j$ の操作列に、整数 $i$ を $k$ 個挿入することを考えます。

操作列に挿入できる箇所は $j$ 個の各操作の後ろなので、まず「操作列における挿入箇所の選び方」が重複組合せ $_{j}H_{k}$ 通りあります。そしてそれぞれに対して「そのように操作列に $i$ を挿入した時に、数列への挿入箇所の候補数によって係数が何倍されるか」が求められ、それらを全て合計したものがDPの遷移の係数になります。

具体例で確認します。 $i=3, j=3, k=2$ として、 $2$ 以下の整数でできた長さ3の操作列（例えば、 $0\to 2\to 1$ ）が既にできているとします。この操作列に $3$ を2個挿入するとき、その挿入箇所の選び方は $_{3}H_{2} = 6$ 通り考えられます。

例えばその中で、2操作目と3操作目の後にそれぞれ挿入した $0\to 2\to 3\to 1\to 3$ という操作列を考えましょう。このとき前のほうの $3$ について、数列の中での挿入箇所の候補は2箇所あります。同様に後ろのほうの $3$ の挿入箇所の候補は3箇所あります。つまり係数が6倍されたことになります。

このような係数を $_{3}H_{2}$ 通り全て計算して足すと、 $1\times 1 + 2\times 2 + 3\times 3 + 1\times 2 + 1\times 3 + 2\times 3$ になります。つまり重複組合せとして選んだ挿入箇所の選び方それぞれについて積を計算し、全て足したものです。これがDPの遷移の係数として採用すべき値です。