トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328) G問題メモ

トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)

G - Cut and Reorder

• 長さ $N$ の数列を、以下の操作を好きに繰り返して $A_1,...,A_N$ から $B_1,...,B_N$ にする
• 操作1: 数列を好きな位置で切り刻んで好きな順で並べなおす。1箇所切り刻むのにコスト $C$
• 操作2: 好きな $i,k$ を選んで、$A_i$ に $k$ を加算する。コスト $|k|$
• 最小コストを求めよ
• $1 \le N \le 22$
• $1 \le A_i,B_i,C \le 10^{15}$
• 実行制限時間 2.8秒
• メモリ制限 512MB

オーダーに $2^N$ が含まれるbitDP解法なら、$N=22$ よりもうちょっと少なく設定されるだろうから別の解法かな？と変なメタ読みしたが、普通にbitDPだった。 いつもと違うメモリ制限も、想定解法が $O(N2^N)$ に対して $O(N^2 2^N)$ を落とすためらしい。

$DP[S]$ を以下で定義する。

• $S=\{S_1,S_2,...,S_n\}$ として、$A_1,...,A_n$ を、$B_{S1},B_{S2},...,B_{Sn}$ にするのにかかる最小コスト

配る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のブロック $A_7$ は、$B_1,B_4,B_5$ に移せる
• 長さ2のブロック $[A_7,A_8]$ は、$[B_4,B_5]$ に移せる
• 長さ3のブロック $[A_7,A_9]$ は、この $S$ ではどこにも移せない

1ブロックの切り出しにつきコスト $C$ かかり、移した先では操作2によって各要素の差の絶対値だけのコストがかかる。

• $pre[k,l_a,l_b] =$ 長さ $k$ のブロックで、それぞれ $A_{la}$ と $B_{lb}$ が左端であるもの同士を、操作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$ 箇所だけ試せばよいので、

• $\displaystyle \sum_{k=1}^{N}2^{N-k}(N-k+1)$ → $O(N 2^N)$

となるらしい。

公式のサンプルコードは $S$ の方から遷移先の $l,r$ を探索しているが、 以下の自分のコードは、$|S|$ を基準にまず遷移の長さ $k$ を決めて、それを1つずつずらしている。
そのため少し遷移に無駄があって、どちらかというと $O(N^2 2^N)$ を定数倍削減している感じだが、通った。
遷移回数も、$3 \times 10^8$ ほどある。

Python3