オーダーに $2^N$ が含まれるbitDP解法なら、$N=22$ よりもうちょっと少なく設定されるだろうから別の解法かな?と変なメタ読みしたが、普通にbitDPだった。 いつもと違うメモリ制限も、想定解法が $O(N2^N)$ に対して $O(N^2 2^N)$ を落とすためらしい。
$DP[S]$ を以下で定義する。
配るDPで、$DP[S]$ からの遷移を考える。
$A_1,...,A_n$ は決定しているので、次の $A_{n+1}$ から連続する、 操作1の結果のブロック1単位の切り出し方・移動先を全て試す。
S={2,3,6,7,8,9} 1 2 3 4 5 6 7 8 9 A o o o o o o - - - o:決定済み -:未決定 B - o o - - o o o o
1ブロックの切り出しにつきコスト $C$ かかり、移した先では操作2によって各要素の差の絶対値だけのコストがかかる。
は $O(N^3)$ で事前計算でき、これを使うと遷移は(切り出し方・移動先)1箇所につき $O(1)$ となる。
$S$ をbitで表現して小さい方から計算していき、$DP[\{1,...,N\}]$ が答えとなる。
1つの $S$ に対する(切り出し方・移動先)の総数を考えると、
一見、ブロックの長さ $O(N)$、位置合わせ $O(N)$ の $O(N^2)$ に見える。
これだと、$S$ は $2^N$ 通りあるので $O(N^2 2^N)$ となり少し厳しい。
だが実際は、$S$ が大きくなる毎にブロック長の上限は狭まっていくし、長いブロックは位置合わせの回数も少なく済む。
公式Editorialによると、ブロックの長さに着目することで、 長さ $k$ のブロックが試されるような $S$ は $2^{N-k}$、 またそこからの位置合わせも $N-k+1$ 箇所だけ試せばよいので、
となるらしい。
公式のサンプルコードは $S$ の方から遷移先の $l,r$ を探索しているが、
以下の自分のコードは、$|S|$ を基準にまず遷移の長さ $k$ を決めて、それを1つずつずらしている。
そのため少し遷移に無駄があって、どちらかというと $O(N^2 2^N)$ を定数倍削減している感じだが、通った。
遷移回数も、$3 \times 10^8$ ほどある。