通せず。通せていればonsite獲得だったようであるし通せてもおかしくない問題だったのでけっこうくやしい。

C - アメージングな文字列は、きみが作る！

解法

丁寧にやる。

基本的には先頭に文字aを追加しまくればよい。 ただし、削除によって文字aのみからなる文字列を作れるならそうすべきである。 また、文字列の先頭にaを追加するのでなくて、先頭の連続するaに後続する文字列の先頭をaに置き換えるほうが有利な場合もある。 これらを丁寧に処理すればよい。

特に後者に関して、先頭に追加するaの数$a$と置き換えあるいは元々含まれていたaの数$b$を持ちながら前から舐めればよい。 また、s.substr(i) < s.substr(j)を高速に実行するためにsuffix arrayを使う必要がある。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
vector<int> suffix_rank(string const & s) { // O(nloglogn)
    int n = s.length();
    vector<int> sa(n+1);
    vector<int> rank(n+1);
    repeat (i,n+1) {
        sa[i] = i;
        rank[i] = i < n ? s[i] : -1;
    }
    for (int k = 1; k <= n; k *= 2) {
        auto compare = [&](int i, int j) {
            int ri = i + k <= n ? rank[i + k] : -1;
            int rj = j + k <= n ? rank[j + k] : -1;
            return make_pair(rank[i], ri) < make_pair(rank[j], rj);
        };
        sort(sa.begin(), sa.end(), compare);
        vector<int> dp(n+1);
        dp[sa[0]] = 0;
        repeat (i,n) dp[sa[i+1]] = dp[sa[i]] + compare(sa[i], sa[i+1]);
        rank = dp;
    }
    return rank;
}

int main() {
    string s; int k; cin >> s >> k;
    int n = s.size();
    if (n - count(s.begin(), s.end(), 'a') <= k) {
        cout << string(n-k, 'a') << endl;
    } else {
        vector<int> rank = suffix_rank(s);
        int a = k, b = 0;
        int x = k, y = 0;
        repeat (i,n) {
            if (s[i] == 'a') {
                ++ b;
            } else {
                -- a;
                ++ b;
                if (a < 0) break;
            }
            if (x < a+b) {
                x = a+b;
                y = i+1;
            } else if (x == a+b and rank[i+1] < rank[y]) {
                y = i+1;
            }
        }
        cout << string(x, 'a') << s.substr(y) << endl;
    }
    return 0;
}