公式
B - XYYYX 解説
by
B - XYYYX 解説
by 
ygussany
\(S\) 中の X の個数を \(x\) とします．
\(x = N\) の場合，\(K \le 1\) であれば \(0\)，\(K > 1\) であれば \(K - 1\) が答えです．
以下では \(x < N\) の場合を考えます．
\(K \le x\) の場合，Y を選んで X に変えるのは明らかに損なので，\(K\) 個の X を選んで Y に変える問題だと考えてよいです．
直観的には，
Yに隣接するXを選んでYに変えることでYYの数を \(1\) 個増やせる，- 「両端が
Yであり間が \(1\) 個以上のXからなる区間YXX…XY」内のXを全て選ぶことでYYを \(1\) 個余分に増やせる，
と考えられるので，そのような区間 YXX…XY を短い順に貪欲に選んでいけばよいです．
そのような区間が長さごとにいくつあるかを素朴に数えるなどの前計算をしておくことで，全体として \(\mathrm{O}(N)\) 時間でこの問題を解くことができます．
貪欲法の正当性
$0$ 文字目と $(N + 1)$ 文字目に仮想的にX を追加して，文字が隣り合う $(N + 1)$ 箇所のうち YY となる箇所の個数を最大化する問題だと考えてみましょう．
このとき，結果として得られる文字列 $S'$ における X の個数は $x + 2 - K$ で固定であり，$S'$ が X で始まり X で終わることも変わりません．
したがって，$S'$ において X のみで構成される極大な区間（上での「」と両端に対応）の個数を $z$ とすると，$S'$ 中の XX, XY, YX, YY の個数はそれぞれ
$$x + 2 - K - z, \ \ z - 1,\ \ z - 1, \ \ N + 1 - x + K - z$$
と計算できます．
$N, K, x$ は入力時点で決まった値なので，YY の個数を最大にすることは，$z$ を最小にすることと等しいです．
両端の区間を消すことは不可能なので，間にある（ Y で挟まれた）区間をできる限り多く消す問題となり，これは区間を短い順に選ぶことで達成できます．
\(K > x\) の場合，選ばない X があるのは明らかに損なので，全ての X を選ぶと仮定してよいです．
このとき，残り \((K - x)\) 個の Y を選んで X に変える必要がありますが，視点を変えると，\((N - x)\) 個ある Y のうち \((N - K)\) 個を選ばずに Y のままにすると見なせます．
このとき，入力文字列の X, Y を反転してみると，\((N - x)\) 個の X から \((N - K)\) 個を選んで Y に変える問題と見なせ，そのように変換することで前者の場合に帰着できます．
投稿日時:
最終更新: