オーダーに 2N が含まれるbitDP解法なら、N=22 よりもうちょっと少なく設定されるだろうから別の解法かな?と変なメタ読みしたが、普通にbitDPだった。 いつもと違うメモリ制限も、想定解法が O(N2N) に対して O(N22N) を落とすためらしい。
DP[S] を以下で定義する。
配るDPで、DP[S] からの遷移を考える。
A1,...,An は決定しているので、次の An+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(N3) で事前計算でき、これを使うと遷移は(切り出し方・移動先)1箇所につき O(1) となる。
S をbitで表現して小さい方から計算していき、DP[{1,...,N}] が答えとなる。
1つの S に対する(切り出し方・移動先)の総数を考えると、
一見、ブロックの長さ O(N)、位置合わせ O(N) の O(N2) に見える。
これだと、S は 2N 通りあるので O(N22N) となり少し厳しい。
だが実際は、S が大きくなる毎にブロック長の上限は狭まっていくし、長いブロックは位置合わせの回数も少なく済む。
公式Editorialによると、ブロックの長さに着目することで、 長さ k のブロックが試されるような S は 2N−k、 またそこからの位置合わせも N−k+1 箇所だけ試せばよいので、
となるらしい。
公式のサンプルコードは S の方から遷移先の l,r を探索しているが、
以下の自分のコードは、|S| を基準にまず遷移の長さ k を決めて、それを1つずつずらしている。
そのため少し遷移に無駄があって、どちらかというと O(N22N) を定数倍削減している感じだが、通った。
遷移回数も、3×108 ほどある。