[AtCoder] ABC 009 C – 辞書式順序ふたたび

2020年12月11日2020年12月12日

問題

方針

\( T_i \) の先頭から貪欲に辞書順の最小の文字から構成できるかを調べます。これは文字の頻度を管理することで、高速に計算することができます。文字列 \( S \) の \( i \) 文字目から \( j \) 文字目までの部分文字列を \( S(i, j) \) とします。

\( T(1, i) \) までの部分文字列を決めた時、\( S(1, i ) \) と異なる文字の数は愚直に計算できます。このとき、\( T(i + 1, N) \) と \( S(i + 1, N) \) の異なる文字の数の最小値は、文字の頻度を比べることで求めることができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int diff(int *a, int *b) {
    int ret = 0;
    for (int i = 0; i < 26; i++) {
        ret += max(0, a[i] - b[i]);
    }
    return ret;
}

int main() {
    int N, K;
    string S;
    cin >> N >> K >> S;
    if (K == 0 || K == 1) {
        cout << S << "\n";
        return 0;
    }
    int a[26]{}, b[26]{};
    for (int i = 0; i < N; i++) {
        a[S[i] - 'a']++;
        b[S[i] - 'a']++;
    }
    string T(N, '?');
    int d = 0;
    for (int i = 0; i < N; i++) {
        a[S[i] - 'a']--;
        if (d == K) {
            T[i] = S[i];
            continue;
        }
        for (int j = 0; j < 26; j++) {
            if (b[j] == 0) continue;
            if (S[i] - 'a' == j) {
                b[j]--;
                T[i] = S[i];
                break;
            }
            // T_i = j とできるか？
            b[j]--;
            if (d + 1 + diff(a, b) <= K) {
                d++;
                T[i] = (char)(j + 'a');
                break;
            }
            b[j]++;
        }
    }
    cout << T << "\n";
    return 0;
}