CF Round #656 D - a-Good String


Tags:cpcodeforcesdiv3divide_and_conquergreedystring

問題

https://codeforces.com/contest/1385/problem/A

問題文

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

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

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

制約

  • 1t2×1041 \le t \le 2 \times 10^4
  • 1n131072=2171 \le n \le 131072 = 2^{17}
  • n=2kn = 2^k と表せる
  • nn の総和は 2×1052 \times 10^5 を超えない

サンプル

6
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z
2
ac
0
7
4
5
1
1

考察

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