Processing math: 100%

目次

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

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

G - Cut and Reorder

G - Cut and Reorder

問題

解法

オーダーに 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) に見える。
これだと、S2N 通りあるので O(N22N) となり少し厳しい。

だが実際は、S が大きくなる毎にブロック長の上限は狭まっていくし、長いブロックは位置合わせの回数も少なく済む。

公式Editorialによると、ブロックの長さに着目することで、 長さ k のブロックが試されるような S2Nk、 またそこからの位置合わせも Nk+1 箇所だけ試せばよいので、

となるらしい。

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

Python3