dpは苦手。 解説を見た。

G - 辞書順

解法

DP + 復元。$O(|s|)$。

まず、$i$文字目を先頭とする部分列の数${\rm dp}_i$を求める。 $i$文字目より後に初めて文字$c$が出現する位置を$j_{i,c}$とすると、${\rm dp}_i = 1 + \Sigma_{c \in ``abcde \dots z”} {\rm dp}_{j_{i,c}}$となる。 普通に計算すると明かにoverflowするが、$k$より大きい値は区別する必要がないので適当にminを取ればよい。

次に、これの経路復元をする。 $i$文字目が使われることが分かっていて、${\rm dp}_i = 1 + a + b + c + \dots + z$としたとき、$i$文字目を先頭とする$k$番目の部分列を考える。 $s_i$が使われるのは当然として、それ以降の文字列は、

  • $k = 1$なら、空文字列
  • $1 \lt k \le 1+a$なら、$j_{i,a}$番目の文字を先頭とする部分列で$k-1$番目のもの
  • $1+a \lt k \le 1+a+b$なら、`$j_{i,b}$番目の文字を先頭とする部分列で$k-1-a$番目のもの
  • $\dots$
  • $1+a+b+c+\dots+z \lt k$なら、存在しない

となる。

実装

#include <iostream>
#include <vector>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
typedef long long ll;
using namespace std;
int main() {
    string s; ll k; cin >> s >> k;
    int n = s.size();
    vector<array<ll,26> > next(n+1);
    repeat (j,26) next[n][j] = n;
    repeat_reverse (i,n) repeat (j,26) next[i][j] = s[i]-'a' == j ? i : next[i+1][j];
    // dp
    vector<ll> dp(n+1);
    repeat_reverse (i,n) {
        dp[i] = 1;
        repeat (j,26) {
            dp[i] = min(k+1, dp[i] + dp[next[i+1][j]]);
        }
    }
    // reconstruct
    string t;
    int i = -1;
    while (k > 0) {
        k -= 1;
        int j = 0;
        for (; j < 26; ++j) {
            int l = next[i+1][j];
            if (k >= dp[l]) {
                k -= dp[l];
            } else {
                t += 'a'+j;
                i = l;
                break;
            }
        }
        if (j == 26) break;
    }
    // output
    if (t.empty()) t = "Eel";
    cout << t << endl;
    return 0;
}