問題文: ARC024 E Sequence Growing Hard
問題概要
0要素の数列がある。この数列に、以下の条件を満たすように、1要素ずつ挿入することをN回繰り返す。
- 挿入後の数列は、挿入前より辞書順で大きい。
挿入の過程で同じ数列ができる操作は同じとみなす。操作の方法は何通りあるか。
自分の誤答
操作を逆から見ると、長さNの数列から要素を除去していく方法の総数を数えればよいことがわかる。除去できるのは、「広義単調増加のstreakの最後だけ」であることがわかる。しかしstreakの個数を状態として持つDPだと失敗する (除去した後のstreakの個数は同じか1個減るかだが、どちらかわからない)。
正解
挿入DPを行う。k=k'の結果が全てのnについて分かっている時、k=k'+1の時の結果を求めることを考える。k=k'の時の操作列にk'+1を挿入する操作を0個以上入れれば良いことがわかるが、うまく解析すると、k'+1を挿入する操作を入れる時刻を決めると、何個挿入しても場合分けの分岐の個数が一定であることがわかる (元の操作列における時刻にのみ依存する)。これを使って区間DPする。
感想
知識がなかった。挿入DPは1回だけ解いたことがあったので、それを活かしたかった。
