D. a-Good String

Codeforces Round #656 (Div. 3)

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

問題

長さの文字列が与えられるので、番目の文字を任意の文字に置き換える操作を何度か行うことでa-goodな文字列にできる最小の操作回数を求める。
ここで、c-goodであるとは次の条件の内どれかを満たす事である。

• 長さ1の文字列
• 前半部が文字cのみで構成され、後半部は(c + 1)-goodである。
• 後半部が文字cのみで構成され、前半部は(c + 1)-goodである。

解法

c-goodの条件を眺めると再帰的定義であることに気がつく。
これは、半分をaに統一すると、もう半分はb-goodにならなければならない。今度は、半分の半分をbに統一するともう半分は、c-goodに....という風に1文字になって分割できなくなるときまで続くことからわかる。
次に制約を眺めてみると再帰木の葉の総数は高々程度であることがわかるので、全探索をすれば良い事がわかる。

実装についてだが、葉に達したときにansをcostで更新するようにした。
再帰関数を呼び出すときは、左半分を文字cで統一したときにかかるコストをdiff1として、右半分に対して潜るような実装をしている。右半分を統一したときはその逆である。
また、文字cで統一したときのコストは、累積和を計算しておき、(区間の長さ)から(区間に存在するcの総数)の差をとることで高速に求めることが出来る。
今回、区間の分割の仕方は、(左半分) = [left, mid], (右半分) = [mid+1, right]のようにした。また、累積和は、左端が閉じていて、右端が開いているという実装にした。

コード

https://codeforces.com/contest/1385/submission/94952181

int n;
string s;
vector<vector<int>> c;
int ans = INF;

void rec(char x, int left, int right, int cost) {
    if (left == right) {
        chmin(ans, cost + (s[left] != x));
        return;
    }

    int mid = left + (right - left) / 2;
    
    int diff1 = (mid - left + 1) - (c[x - 'a'][mid + 1] - c[x - 'a'][left]);
    int diff2 = (right - mid) - (c[x - 'a'][right + 1] - c[x - 'a'][mid + 1]);

    
    rec(x+1, left, mid, cost + diff2);    
    rec(x+1, mid + 1, right, cost + diff1);
}



void solve() {
    cin >> n >> s;

    ans = INF;
    c = vector<vector<int>>(26, vector<int>(n+1));

    rep(i, n) {
        int t = s[i] - 'a';
        c[t][i + 1]++;
    }
    rep(i, 26) {
        rep(j, n) c[i][j + 1] += c[i][j];
    }

    rec('a', 0, n - 1, 0);

    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
}