ARC081 E - Don't Be a Subsequence

問題

https://beta.atcoder.jp/contests/arc081/tasks/arc081_c

問題概要

• 英小文字のみからなる文字列が与えられる

• 文字列の部分文字列"でない"文字列のうち、

• 最小の長さのもの

• 最小の長さのものが複数ある場合は、辞書順最小のもの

を出力する。

考察

• 英小文字のみからなるので、結構なゴリ押しはできる
• 答えは必ず、0文字を含む部分文字列+一文字になる。
• 答えの部分文字列の最後の文字は、それ以降でa-zのうちどれかが出現していないような文字
• 答えの部分文字列の最後の文字に付け足す文字は、それ以降で出現していないアルファベットのうち、最も小さいもの
• それぞれの文字列の位置を始点とし、そこから文字X(a-zに関してすべて行う)が初めて出てくる場所に向けて辺を貼る。
• 最初にa-zが現れる場所を最初の探索点として、幅優先探索をし、「最後の文字」が現れたら探索終了。「追加する一文字」を追加してそれを出力する。
• 探索は必ずa-zの順番でqueueに入れていき、すでに訪れている位置に関しては無視して良い。(なぜならば、aから順番に探索しているので後から訪れるような状態は必ず先に訪れたものよりも辞書順が後になるから)

オーダーは文字種をMとすると、

実装

void solve() {
    string S; cin >> S;
    vector<int> A(S.size());
    for (int i = 0; i < S.size(); ++i) {
        A[i] = S[i] - 'a';
    }
    vector<bool> check('z' - 'a'+1);
    vector<vector<int> > G(A.size());
    vector<int> memo(check.size(), -1);
 
    RREP(i, A.size()) {
        REP(j, check.size()) {
            if (memo[j] == -1) {
                G[i].push_back(-j-1);
                break;
            }
        }
        if (G[i].size() == 0) {
            G[i].resize(memo.size());
            copy(ALL(memo), G[i].begin());
        }
        memo[A[i]] = i;
    }
 
    vector<bool> visited(A.size());
    queue<int> que;
    for (int i = 0; i < memo.size(); ++i) {
        if (memo[i] == -1) {
            cout << char(i + 'a') << endl;
            return;
        }
        que.push(memo[i]);
        visited[memo[i]] = true;
    }
 
    vector<int> rev(A.size(), -1);
    int last = -1;
    string res;
    while (not que.empty()) {
        int node = que.front(); que.pop();
        if (G[node].back() < 0) {
            res.push_back(-G[node].back()-1 + 'a');
            last = node;
            break;
        }
        for (auto &to : G[node]) if(not visited[to]) {
            que.push(to);
            visited[to] = true;
            rev[to] = node;
        }
    }
    while (true) {
        if (last == -1) break;
        res.push_back(S[last]);
        last = rev[last];
    }
    reverse(ALL(res));
    cout << res << endl;