問題リンク
問題概要
\(0\)と\(1\)からなる文字列\(S\)が与えられる。
「\(1 \leqq i < j \leqq|S|\)かつ\(S_i=0,S_j=1\)となる\(i\)と\(j\)の組を選び、\(S_j\)を削除して\(S_i\)の直前に挿入する」という操作を考える。
この操作を0回以上\(K\)回以下繰り返して得られる文字列の総数は何通りか。
解法
操作で文字列がどのように変化するかを考える。
たとえば
0000011111
↓
0000101111
↓
0000110111
↓
1000011011
のように変化する。
この時「選んだ0の直前に挿入する」という条件は、「選んだ0より前の任意の位置に挿入する」としてよい。
これは1が連続している場所にはそのどこに挿入しても結果が変わらないことから成立する。
111101
↓
111110 or 111110
そこで、1の連続した区間をまとめてしまうと、与えられた操作は
「ある区間の長さを1減らして、それより左のある区間の長さを1増やす」
と言い換えられることがわかる。
以上より、文字列を「0で区切られた1が連続する区間の長さの列」と見なして数列に対応させる(これは文字列と1対1に対応する)。
たとえば
10110111→{\(1,2,3\)}
0101→{\( 0,1,1\)}
01100110→{\(0,2,0,2,0\)}
となる。最初の時点で得られる数列をAと置く。
この時操作は「\(i < j\)かつ\(A_j \geqq 1\)となる\((i,j)\)の組を選び\(A_i\)を1増やし\(A_j\)を1減らす」となる。
最終的に得られる数列をBとおくと、Bが満たすべき条件は
- (Bの総和) = (Aの総和)、すなわち\(\sum_{i=1}^{M}B_i = \sum_{i=1}^{M}A_i\)
- k=1,2,..M-1に対して(\(B_k\)までの総和) \(\geqq\) (\(A_k\)までの総和)、すなわち\(\sum_{i=1}^{k}B_i \geqq \sum_{i=1}^{k}A_i\)
- \(\max(B_i-A_i,0)\)の総和が\(K\)以下
となる。(Mは数列の長さ)
最後の条件は操作の回数が\(K\)回以下という条件に対応する。(なお、最適に操作を行えば操作回数は\(|S|\)で抑えられる)
このままDPをしても良いが、自分は本番ではさらに次のように条件を言い換えた。
\(C_k = \sum_{i=1}^{k}B_i - \sum_{i=1}^{k}A_i\)とおくと、数列Cが満たすべき条件は
- \(C_M = 0\)
- k=1,2,...,M-1に対して\(C_k \geqq 0\)
- \(\max(C_i-C_{i-1}, 0)\)の総和が\(K\)以下(ここで\(C_0=0\)とする)
となる。3番目の条件に出てくる和を「増分の和」と呼ぶことにする。
\(dp[i][j][k] = {i番目の要素まで見てC_i=j、増分の和がkである数列の個数}\)
とおく。
この時
\(dp[i][j][k] = \)
\( (dp[i-1][j-1][k - 1] + dp[i-1][j-2][k-2]+dp[i-1][j-3][k-3]+...)\)
\( + \)
\( (dp[i-1][j][k]+dp[i-1][j+1][k]+dp[i-1][j+2][k]+...+dp[i-1][j+A_i][k])\)
となる。
下の部分が\(j+A_i\)で打ち切られているのは、もともとBのprefixの総和とAのprefixの総和の差を考えていたため、もし差が\(A_i\)より大きく縮むことがあれば、Bに負の要素が出てきてしまうからである。
この遷移は累積和を取ることで一回のiに対し\(O(|S|^2)\)で行うことができ、
全体で\(O(|S|^3)\)になる。
答えは\(\sum_{k=0}^{K}dp[M][0][k]\)である。
提出
https://atcoder.jp/contests/agc046/submissions/14500284
(方針変更によって不必要な配列などが残っています)
感想
累積和とかがいっぱい出てきて混乱しやすいし、実際した。
