Typical DP Contest G - 辞書順

問題

tdpc.contest.atcoder.jp

解法

まず少し小さい問題として, 「答えが Eel になるかどうか」というのを考えてみます。これは, 「部分文字列は何種類考えられるか」という問題が解ければ良いです。

文字列の各位置を頂点とみなします。
各頂点から, 'a', 'b', ..., 'z' に到達する, 最も index の近い頂点をメモしておきます(出来たグラフを G とする)。
G を求めておけば, dp[i] = (i 番目の頂点から始まる部分文字列の数) が求まります。i = 0 を root のような感じにすると書きやすいです。これで dp[0] < K なら答えは Eel です。

そうでない場合は, 1 文字目から順に文字を決めていきます。'a' から始まる文字列が a( < K ) 個あって, 'b' から始まる文字列が b 個あった時, a+b >= K なら, 1 文字目は 'b' に決まって, さらに 2 文字目は…と続けていきます。

typedef unsigned long long ull;
const int MAXN = 1000100;
vector<int> G[MAXN];
ull dp[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    ull K;
    cin >> s;
    cin >> K;
    vector<int> edge(26, -1);
    int N = s.size();
    for (int i = N; i > 0; i--) {
        G[i] = edge;
        edge[s[i-1]-'a'] = i;
    }
    G[0] = edge;
    for (int i = N; i >= 0; i--) {
        dp[i] = (i>0);
        for (int j = 0; j < 26; j++) {
            int to = G[i][j];
            if (to != -1) {
                dp[i] += dp[to];
                if (dp[i] > K) dp[i] = K+1;
            }
        }
    }
    if (dp[0] < K) cout << "Eel" << endl;
    else {
        string ans;
        int now = 0;
        ull k = 0;
        while (k < K) {
            for (int j = 0; j < 26; j++) {
                int to = G[now][j];
                if (to == -1) continue;
                if (k+dp[to] < K) {
                    k += dp[to];
                } else {
                    k++;
                    now = to;
                    ans += (char)('a'+j);
                    break;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}