D - a-Good String

問題

https://codeforces.com/contest/1385/problem/D (新しいタブで開く)

問題文

長さ $n = 2^k (k \le 0)$ の文字列 $s$ は、以下の 3 つのうち少なくとも 1 つの条件を満たすとき、 $c$-good とする。ただし $c$ は何かの文字。

• $n = 1$ なら $s = c$
• $n > 1$ なら $s$ を半分にして、前半が $c$-good かつ後半が $(c+1)$-good である。
• $n > 1$ なら $s$ を半分にして、前半が $(c + 1)$-good かつ後半が $c$-good である。

$s$ のどれか index を選んで、その文字を任意の文字に変えることを複数回行える。
このとき、 $s$ が $a$-good にするための操作回数の最小値は？

制約

• $1 \le t \le 2 \times 10^4$
• $1 \le n \le 131072 = 2^{17}$
• $n = 2^k$ と表せる
• $n$ の総和は $2 \times 10^5$ を超えない

サンプル

6
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z
2
ac

0
7
4
5
1
1

考察

その文字を $c$-good にするために、前半か後半のどちらを $(c+1)$-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;
}