読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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);
}