Typical DP Contest G - 辞書順

問題文 : 辞書順

解法 :

前段階として$dp[i][j]:=$ $i$ 番目までで文字$j$ を先頭とする部分列の総数, としてDP をするが, 部分列は指数関数的に増加するので注意する. (abc...z という文字列だけで$2^26$ 通りある...)

復元は, 先頭から部分列の総数を文字ごとに見ていって, 自分の位置より大きくなる文字があればその文字を出力していけば良い. このとき, 実際にその文字がある位置まで遡っていくことに注意する.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>

using namespace std;

const long long int INF = 1000000000000001000ll;

char s[1000001];
long long int K;
long long int dp[1000001][26];
int L;

int main()
{
	scanf("%s", s);
	scanf("%lld", &K);
	
	L = strlen(s);
	
	for (int i = L - 1; i >= 0; i--){
		dp[i][s[i] - 'a']++;
		for (int j = 0; j < 26; j++){
			dp[i][s[i] - 'a'] = min(INF, dp[i][s[i] - 'a'] + dp[i + 1][j]);
		}
		for (int j = 0; j < 26; j++){
			if (j != s[i] - 'a') dp[i][j] = dp[i + 1][j];
		}
	}
	
	long long int sum = 0;
	for (int i = 0; i < 26; i++){
		sum = min(INF, sum + dp[0][i]);
	}
	
	if (sum < K) return (!printf("Eel\n"));
	
	for (int i = 0; i < L; i++){
		if (K == 0) break;
		for (int j = 0; j < 26; j++){
			if (dp[i][j] < K) K -= dp[i][j];
			else {
				char c = j + 'a';
				while (s[i] != c) i++;
				printf("%c", c);
				K--;
				break;
			}
		}
	}
	printf("\n");
	
	return (0);
}