Codeforces Round #311 (Div. 2) E. Ann and Half-Palindrome

問題

codeforces.com

解法

まず dp[i][j] = (i 文字目からの j 文字が半回文になっているかどうか)を適当に求めます。
で, sum[i][j] = (i 文字目から j 文字以上使う文字列の中で 半回文になっているものの数)

とします。これを前準備してから, 答えとなる文字列を構成していきます。
そのために, 「今の文字列の状態から, 次の i 文字目が 空文字になるか, a になるか, b になるか」を求めていきます。例えば問題文のひとつ目のサンプルで考えてみます。

abbabaab
7

まず最初の文字列の状態は ""(空文字)です。
a から始まるものの文字数は 9, b から始まるものの文字数は 9 です(ここらへんは sum を使って求める)。求めたいものは 7 番目の半回文なので, 今回は最初の文字が a であるとわかります。

よって文字列の状態は "a" になりました。
文字列が "a" 単品で終わる文字列の数は 4 つ, aa〜 と続いていく文字列は 1 つ, ab〜 と続いていく文字列は 4 つあります。 a 単品で終わらせると 4 番目までの半回文までしかカバーしておらず, aa〜 と続けると 4+1 = 5 番目の半回文までしかカバーしていないので, 次の文字は b です。

よって文字列の状態は "ab" になりました。
文字列が "ab" 単品で終わる文字列の数は なし, aba〜 と続いていく文字列は 1 つ, abb〜 と続いていく文字列は 2 つあります。
よって次の文字は b ですね。(6 番目から先をカバー)

そんな感じでほげほげやります。実装に微妙に工夫が必要なのでそこはソースコードで見て欲しいです。

const int MAXN = 5050;
bool dp[MAXN][MAXN];
int sum[MAXN][MAXN];
string s;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s;
    int k;
    cin >> k;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        dp[i][0] = dp[i][1] = true;
    }
    for (int L = 2; L <= n; L++) {
        for (int i = 0; i < n; i++) {
            if (i+L-1 >= n) break;
            if (s[i] == s[i+L-1]) {
                if (L <= 4) dp[i][L] = true;
                else dp[i][L] |= dp[i+2][L-4];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = n; j >= 0; j--) {
            sum[i][j] = sum[i][j+1] + dp[i][j];
        }
    }
    string ans;
    vector<int> cand;
    for (int i = 0; i < n; i++) cand.push_back(i);
    for (int i = 1; i <= n; i++) {
        if (k == 0) break;
        int empty = 0, a = 0, b = 0;
        vector<int> A, B;
        for (int el : cand) {
            if (i > 1) {
                if (dp[el][i-1]) empty++;
            }
            if (el+i-1 < n) {
                if (s[el+i-1] == 'a') {
                    A.push_back(el);
                    a += sum[el][i];
                }
                else {
                    B.push_back(el);
                    b += sum[el][i];
                }
            }
        }
        if (k <= empty) break;
        else if (k <= a+empty) {
            k -= empty;
            cand = A;
            ans += "a";
        } else {
            k -= empty+a;
            cand = B;
            ans += "b";
        }
    }
    cout << ans << endl;
    return 0;
}