問題
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; }