ARC081 E - Don't Be a Subsequence

問題文

http://arc081.contest.atcoder.jp/tasks/arc081_c

解法

今見ている位置から後ろの，各アルファベットの最も近い位置を持っておく．
すると，今見ている頂点から始めた時，以降の部分列で現れない最小のものを求めることができる．
各アルファベットで以降に現れないものがあれば，求める答えは「今出来ている文字列 + 現れない中で最小のもの」となる．
これを先頭（空文字の状態）からはじめて，幅優先探索で求めていって，はじめて以降に現れない文字が現れたタイミングでできた文字を出力すればよい．

ソースコード（通るけどヤバイ方）

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


constexpr int INF = 1e9;


int main() {
    string A;
    cin >> A;
    int const n = A.size();
    vector<vector<int>> pos(n + 1, vector<int>(26, INF));
    for(int i = n; i >= 0; --i) {
        if(i - 1 >= 0) {
            pos[i - 1] = pos[i];
            pos[i - 1][A[i - 1] - 'a'] = i;
        }
    }
    vector<bool> visited(n + 1);
    queue<pair<int, string>> que;
    que.push(make_pair(0, ""));
    string res;
    visited[0] = true;
    while(!que.empty()) {
        auto p = que.front();
        int v = p.first;
        que.pop();
        for(int i = 0; i < 26; ++i) {
            if(pos[v][i] == INF) {
                res = p.second + char('a' + i);
                cout << res << endl;
                return 0;
            }
        }
        for(int i = 0; i < 26; ++i) {
            int next_p = pos[v][i];
            if(visited[next_p]) {
                continue;
            }
            que.push(make_pair(next_p, p.second + char('a' + i)));
            visited[next_p] = true;
        }
    }
    cout << res << endl;
}

感想

本番でバグが取れなくて通せなかった．
あと幅優先でやる必要ない気がする．想定解は貪欲だったし．
そもそも文字列のコピーが走るのでTLEしてほしい気がするんですけど，なんで通るんだこれ？

ソースコード2

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

constexpr int INF = 1e9;

int main() {
    string A;
    cin >> A;
    int const n = A.size();
    vector<vector<int>> next_pos(n + 1, vector<int>(26, n));
    for(int i = n - 1; i >= 0; --i) {
        next_pos[i] = next_pos[i + 1];
        next_pos[i][A[i] - 'a'] = i;
    }

    vector<int> max_len(n + 2);
    max_len[n] = 1;
    for(int i = n - 1; i >= 0; --i) {
        int t = INF;
        for(int j = 0; j < 26; ++j) {
            t = min(t, max_len[next_pos[i][j] + 1] + 1);
        }
        max_len[i] = t;
    }
   
    string res;
    int p = 0;
    for(int i = max_len[0] - 1; i >= 0; --i) {
        for(int j = 0; j < 26; ++j) {
            if(max_len[next_pos[p][j] + 1] == i) {
                res += char('a' + j);
                p = next_pos[p][j] + 1;
                break;
            }
        }
    }
    cout << res << endl;
}

想定解で書き直した．