Typical DP Contest G - 辞書順

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_lexicographical

解法

まず，
next_pos[i][c] := i番目以降で，文字 c があらわれる一番前の位置
とします．
ここで，dp[i] を
dp[i] := i 番目の文字を「使った上で」，i 番目以降のユニークな文字列は何通りか
と定義します．
すると，
$dp[i] = 1 + \displaystyle \sum_{c = 'a'} dp[next\_pos[i + 1][c]]$
と表せます．
1 を加えているのは i 文字目の1文字からなる文字列の分です．

あとは K 番目の文字を復元するだけです．
これは，p = 0 (先頭の位置) からはじめて，aからzまで順番に np := next_pos[p][c] をみていって，dp[np] が K を超えるまで飛ばして，超えた段階で遷移（その文字 c を使うことが確定し，p を np + 1に更新する）していくことで復元できます．これはオートマトン（next_pos がオートマトンになっている）の上を辿っていくということです．各ノード i は dp[i] を持っています．

と，色々書いたけどわかりにくい解説だな…．
自分もかなり苦手な問題なので…．

ソースコード

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

constexpr ll INF = 1e18 + 1;

int main() {
    string s;
    ll K;
    cin >> s >> K;

    int const n = s.size();
    vector<ll> dp(n + 2);
    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];
        dp[i] = 1;
        for(int j = 0; j < 26; ++j) {
            dp[i] += dp[next_pos[i][j]];
            dp[i] = min(dp[i], INF);
        }
        next_pos[i][s[i] - 'a'] = i;
    }

    string res;
    int p = 0;
    while(K > 0) {
        int i = 0;
        for(i = 0; i < 26; ++i) {
            if(dp[next_pos[p][i]] < K) {
                K -= dp[next_pos[p][i]];
            } else {
                K--; // c 単体を使う分を減らしている
                p = next_pos[p][i] + 1;
                res += char('a' + i);
                break;
            }
        }
        if(i == 26) {
            break;
        }
    }
    if(res.empty()) {
        res = "Eel";
    }

    cout << res << endl;
}

感想

こういう問題はかなり苦手でつらい．
以下は参考問題です．
http://arc081.contest.atcoder.jp/tasks/arc081_c