ABC462F - 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$ つめのテストケースのみ。
入力を受け取る。
s: "ATCABC"
k: 1s の後ろ $2$ 文字以外について、そこから始まる "ABC" を作るのに必要な置換数を求める。
vec: {1, 3, 3, 0} $3$ 個セットを $(k+2)$ ブロック、DPテーブルとして用意する。
最初のブロックを 0 で初期化、残りは INF にする。
縦棒はブロック境を見やすくするために入れてある。
dp: {0, 0, 0, |INF, INF, INF, |INF, INF, INF} vec[0] = 1 を見て、データを更新する。
自身と $1$ つ前の小さい方を新しい値とするが、ブロック境を超えて移動する数には 1 を足す。
dp: {0, 0, 0, |1, INF, INF, |INF, INF, INF} vec[1] = 3 を見て、データを更新する。
自身と $1$ つ前の小さい方を新しい値とするが、ブロック境を超えて移動する数には 3 を足す。
dp: {0, 0, 0, |1, 1, INF, |INF, INF, INF} vec[2] = 3 を見て、データを更新する。
自身と $1$ つ前の小さい方を新しい値とするが、ブロック境を超えて移動する数には 3 を足す。
dp: {0, 0, 0, |1, 1, 1, |INF, INF, INF} vec[3] = 0 を見て、データを更新する。
自身と $1$ つ前の小さい方を新しい値とするが、ブロック境を超えて移動する数には 0 を足す。
0 ということは元から "ABC" だったということなので、その後 $1$ ブロック分前に移動する。
（先頭はこれ以上左にいかないので 0 のまま、末尾ブロックは INF を入れる）
dp: {0, 0, 0, |0, 1, 1, |1, INF, INF} dp: {0, 1, 1, |1, INF, INF, |INF, INF, INF} （0-indexed で）$k$ 番目のブロックの先頭の値が答え。
注意点
特になし。
別解
特になし。