ABC462 F - More ABC

考え方

$S$ の長さを $N$ として、まずは $O(N^2)$ でもいい場合の解法を考える。

動的計画法で求める。
dp[i][j] を「$i+2$ 文字目までに "ABC" を $j$ 個作る最小コスト」とする。
dp[i][j] の値は以下の $2$ つの値の小さい方である。（ただし後者はテーブルからはみ出ない場合に限る）

• $i+2$ 文字目を使わない場合のコスト、つまり dp[i-1][j]
• $i+2$ 文字目を使う場合のコスト、つまり dp[i-3][j-1]+そこに"ABC"を作るコスト

それとは別に、元々の文字列に "ABC" が何個あったかも計上しておく。
最後の文字までで、$K$ 個追加した個数を作る最小コストが答え。
これで、 $O(N^2)$ でもいい場合の答えは出せる。

そして、$K$ が最大 $10$ と小さいことを利用してこれを高速化する。
元の文字列と、それに最適な置換を行って "ABC" を $K$ 個増やした文字列を比較することを考える。
各文字列の $m$ 文字目までを見たときに、そこまでの "ABC" の個数が減っていることは絶対にない。
なぜなら、$m$ 文字目までをそのままにする、より低コストな解が存在するため。
境界で "ABC" が $1$ つ破壊されることを考慮に入れても、後半で作る "ABC" の個数は同じか減る。
同じであれば後半は同じ置換を採用すればいいし、減るなら "ABC" を $1$ つ選んで作るのをやめればよい。

同じように、$m$ 文字目までで $K+1$ 個以上増えることはない。
これは $m+1$ 文字目以降の "ABC" の個数が減っていることが、上の議論と同様の理由でないため。

ということは、「"ABC" を $j$ 個作る」ではなく、「"ABC" を $j$ 個追加で作る」にすれば、高速化できる。
つまり、 $j$ の値が $0 \leq j \leq N$ ではなく $0 \leq j \leq K$ で済むため、$O(NK)$ となる。

しかし、これでは今度は、元から "ABC" だったところを通過する更新が難しくなる。
そこで、DPテーブルを $3$ 個ずつ $K+2$ ブロック作ることにする。
そして、$3$ 文字前のデータを見ることをやめ、代わりに直前何文字以上 "ABC" を作っていないかを持つ。
$2$ 文字以上新しく "ABC" を作っていない場合のみ、次の "ABC" を作ることができるとする。
$3$ 個ずつなのは、「直前何文字分以上」を $0$、 $1$、 $2$、と $3$ つもつため。
$K+2$ ブロックなのは、追加で作った個数が $0$ から $K$ 個までの $K+1$ 個と、余剰 $1$ 個。

こういうデータの持ち方をすると、元々 "ABC" だったところを通過した場合の処理が簡単になる。
つまり、新たに "ABC" を作るかどうかの処理をしたのち、全データを $1$ ブロック分前に移動すればよい。
ブロック数の余剰は、このとき $K$ 回のデータが一時的に $K+1$ 回相当のブロックにはみ出るためのケア。

最後の文字まで処理が終わったら、全文字使って $K$ 回追加で作るコストを答えればよい。
あるいは、不可能だったら $-1$ を答える。

入力例1での動作

入力例1の $1$ つめのテストケースで動作を確認する。

入力を受け取る。

s: "ATCABC"
k: 1

各位置から始まる長さ $3$ の部分文字列を "ABC" にするために必要な置換数を求める。

動的計画法では、追加した "ABC" の個数ごとに $3$ つの値を持つ。
左から順に、以下の場合の最小置換数を表す。

• 間隔について制約なし
• 直前 $1$ つの開始位置では新しく "ABC" を作っていない
• 直前 $2$ つの開始位置では新しく "ABC" を作っていない

新しく "ABC" を作れるのは、直前 $2$ つの開始位置で作っていない状態からだけである。

最初はまだ何も処理していないので、追加個数 $0$ の $3$ 状態を $0$ とする。

追加0個: {0, 0, 0}
追加1個: {∞, ∞, ∞}
追加2個: {∞, ∞, ∞}

開始位置 $0$ の "ATC" を処理する。
ここに "ABC" を作るなら $1$ 回の置換が必要になる。

追加0個: {0, 0, 0}
追加1個: {1, ∞, ∞}
追加2個: {∞, ∞, ∞}

開始位置 $1$ の "TCA" を処理する。

追加0個: {0, 0, 0}
追加1個: {1, 1, ∞}
追加2個: {∞, ∞, ∞}

開始位置 $2$ の "CAB" を処理する。

追加0個: {0, 0, 0}
追加1個: {1, 1, 1}
追加2個: {∞, ∞, ∞}

開始位置 $3$ は元から "ABC" であり、置換数 $0$ で "ABC" を作れる。
通常の更新をすると、一時的に次の状態になる。

追加0個: {0, 0, 0}
追加1個: {0, 1, 1}
追加2個: {1, ∞, ∞}

ただし、この "ABC" は元から存在していた $1$ 個であり、「追加した個数」には数えない。
そこで、追加個数の基準を $1$ 個分ずらす。

追加0個: {0, 1, 1}
追加1個: {1, ∞, ∞}
追加2個: {∞, ∞, ∞}

全ての開始位置を処理した。
"ABC" をちょうど $1$ 個追加する状態の最小置換数は $1$ なので、答えは $1$ となる。

注意点

特になし。

別解

特になし。