問題
https://codeforces.com/contest/1385/problem/D (新しいタブで開く)
問題文
長さ の文字列 は、以下の 3 つのうち少なくとも 1 つの条件を満たすとき、 -good とする。ただし は何かの文字。
- なら
- なら を半分にして、前半が -good かつ後半が -good である。
- なら を半分にして、前半が -good かつ後半が -good である。
のどれか index を選んで、その文字を任意の文字に変えることを複数回行える。
このとき、 が -good にするための操作回数の最小値は?
制約
- と表せる
- の総和は を超えない
サンプル
6
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z
2
ac
0
7
4
5
1
1
考察
その文字を -good にするために、前半か後半のどちらを -good にしたほうがいいか最小回数を求めて、小さいほうを取ればいい。
構造的に再帰したほうが楽そう。
コード
https://codeforces.com/contest/1385/submission/126233908 (新しいタブで開く)
int n;
string s;
int toChange(int l, int r, char c) {
if (r - l == 1) return s[l] != c;
const int mid = (r + l) / 2;
const int len = (r - l) / 2;
int changeL = len;
int changeR = len;
rep(i, r - l) {
if (s[l + i] == c) {
if (i < len) {
changeL--;
}
else {
changeR--;
}
}
}
changeL += toChange(mid, r, c + 1);
changeR += toChange(l, mid, c + 1);
return min(changeL, changeR);
}
void solve() {
cin >> n;
cin >> s;
cout << toChange(0, n, 'a') << endl;
}