D. a-Good String (Codeforces Round #656 Div. 3)

個人的に超お気に入りの問題でした。（スター押した）

問題

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

問題概要

長さn=2^k (k >= 0)の文字列sについて、以下の条件を少なくとも一つでも満たすものをc-goodな文字列を呼ぶことにする。

• n=1のとき、それは文字cで構成される
  • つまりs = "c"である
• n > 1のとき、文字列の前半が全てcで、後半は(c+1)-goodな文字列である
• n > 1のとき、文字列の後半が全てcで、前半は(c+1)-goodな文字列である

例えば"aabc"はa-goodな文字列であるし、"ffgheeee"はe-goodな文字列である。

さて、長さが2^k (k >= 0)の文字列が与えられる。この文字列をできるだけ少ない数の文字を置き換えることでa-goodな文字列としたい。最小で何文字書き換えるとa-goodな文字列になるかを答えよ。

考察

c-goodな文字列は再帰的な構造をしています。それにそって、再帰によってaから順に全探索して最も置換する文字の少ないものを選べばそれが答えとなります。

計算量は、たとえばn=2^3=8のとき

• 前半がaaaaとしたとき
  • 後半の前半がbbとしたとき
    • 残りがcdのとき
    • 残りがdcのとき
  • 後半の後半がbbとしたとき
    • 残りがcdのとき
    • 残りがdcのとき
• 後半がaaaaとしたとき
  • 前半の前半がbbとしたとき
    • 残りがcdのとき
    • 残りがdcのとき
  • 前半の後半がbbとしたとき
    • 残りがcdのとき
    • 残りがdcのとき

となり、aについて8文字、bについて8文字、cについて8文字、dについて8文字という具合に、n * (k + 1)文字を検査すればすべてを検査することが可能で、これは親の顔よりよく見たO(NlogN)ですから、余裕で間に合います。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        function<int(string, char)> dfs = [&](string t, char c) {
            int m = t.size();
            if (m == 1) return c == t[0] ? 0 : 1;
            int a = 0;
            for (int i = 0; i < m / 2; i++) {
                if (t[i] != c) a++;
            }
            a += dfs(t.substr(m / 2, m / 2), c + 1);
            int b = 0;
            for (int i = m / 2; i < m; i++) {
                if (t[i] != c) b++;
            }
            b += dfs(t.substr(0, m / 2), c + 1);
            return min(a, b);
        };
        cout << dfs(s, 'a') << endl;
    }
}