D - a-Good String

cpcodeforcesdiv3divide and conquergreedystring

最終更新日

問題

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

問題文

長さ 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 にするための操作回数の最小値は?

制約

サンプル

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