AtCoder AGC046-C : Shift 解説

備忘録として
概ね公式解説の通りです　丁寧目に書きました atcoder.jp

問題概要

$S$ に対して、以下の操作を $K$ 回まで行う。

$1\le i\lt j\le |S|$ 、 $S_i =$ 0、 $S_j =$ 1 であるものを選んで、 $S_j$ を取り除いて $S_i$ の直前に挿入する。

最終的な $S$ は何通り考えられるか？

$1\le |S|\le 300$
$0\le K\le 10^{9}$

考察

まず、操作は以下のように言い換えられます。

$S$ を[ 11 ] 0 [ ] 0 [ 1 ] 0 [ 111 ] 0 [ ]のように 0 で区切り、0個以上の 1 からなるいくつかの区間と見る。すると、操作は「ある区間の 1 を１つ選んで、その区間より左の区間に移す」操作とみなせる。

すると、まず以下のことが言えます。

$K\rightarrow \min (K,\ |S|)$ としても、答えは変わらない。

これは、ある1を左に移す操作を2回行うならば、1回目の時点で2回目で挿入する箇所に置いておけば良いことから、11つあたり1回だけ操作をすれば良いことから言えます。

あとはこれを数えれば良いですが、注意点として1 1つ1つは区別がありません。

例えば、

0101 -> 1001 -> 1100
0101 -> 1010 -> 1100

のように、移動方法が違っても同じ文字列ができてしまう可能性があります。

そこで、1 同士の相対的な順序は変えない、というルールをつけて移動する事にします。こうする事で、最終的な文字列に対してどの 1 がどこから来たのかはただ 1 通り定まります。また、これによって生成不能になる文字列が存在しないことはすぐわかります（仮に順序が入れ替わる2つの 1 があるなら、それぞれを最終位置を逆にするような操作もできることから言えます）。

よって、これによって操作と最終的な文字列が 1 対 1 に対応しました。あとは、これに従って dp を行うだけです。

数え上げ

予め、 $S$ は上記のようにいくつかの区間 $a_1,\ a_2,\ \cdots ,a_M$ （ $M$ は区間の数、 $a_i$ は $i$ 番目の区間に含まれる 1 の数）として表現しておきます。

dpテーブルを、以下のように定義します。

$dp[ i] [ j] [ k] :=$ $i$ 番目の区間までは操作（その区間への 1 の挿入、その区間からの 1 の移動）を終えていて、左の区間への移動を確定させた 1 は $j$ 個で、「移動することを確定させたが、まだどの区間に挿入するか決めていない」ような 1 は $k$ 個、となるような、操作方法の数（＝文字列の個数）。

$i$ 番目の区間に対する操作は、以下の２種類です。

$i$ 番目の区間の 1 を $\min (K-j,\ a_i)$ 個まで選んで、移動を確定させる（それより左に移動させる事にする）。
移動先の決まっていない $k$ 個の 1 からいくつか選んで、 $i$ 番目の区間に挿入する。

ここで、両方の操作をすることは明らかに操作回数の無駄なので考える必要はありません。
また、考察で述べた通り、1 同士の相対順序は決めてあるので、1を上記の操作で選ぶ際には個数のみ決めれば良いです。

この遷移について、

については、 $1$ 個以上 $\min (K-j,\ a_i)$ 個以下選ぶので、 $\sum a_i\le |S|$ であることを考えると愚直に遷移しても全体で $O(|S|)$ で済みます。
については、愚直に遷移すると毎回 $O(|S|)$ かかってしまうので、工夫します。
$dp[ i] [ j] [ k] \rightarrow dp[ i+1] [ j] [ k-1],\ dp[ i+1] [ j] [ k-2],\ \cdots ,dp[ i+1] [ j] [ 0]$ というように遷移する必要がある訳ですが、これは $k$ の降順に遷移する 事にすれば以下のような遷移としても同じです。
$dp[ i] [ j] [ m]\rightarrow dp[ i+1] [ j] [ k-1],\ dp[ i] [ j] [ k-1]$