Typical DP Contest G : 辞書順

問題リンク : G: 辞書順 - Typical DP Contest | AtCoder
問題概要 :
文字列sと自然数Kが与えられる
sから得られる連続でない部分文字列のうち、辞書順でK番目のものを求めよ

解法 :
他の人のブログを参考に解いたので、
コードにある通り

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;



ll K,dp[1000100][30]; // dp[i][j] := 場所iで文字jを使う数
string s;

int compute() {
  for(int i=(int)s.size()-1;i>=0;i--) {
    for(char c='a';c<='z';++c) {
      if( s[i] == c ) {
	dp[i][c-'a'] = 1; // c単体
	for(char h='a';h<='z';h++) { // 既にi番目にcを置いたので後に何が来ても良い
	  dp[i][c-'a'] += dp[i+1][h-'a'];
	  if( dp[i][c-'a'] > K ) { // 愚直に計算するとlong longでも計算できないのでK以上はK+1にまとめる
	    dp[i][c-'a'] = K + 1LL;
	    break;
	  }
	}
      } else {
	dp[i][c-'a'] = dp[i+1][c-'a']; // s[i]はcではないためiより前に置いたものを使う
      }
    }
  }
  {
    ll sum = 0;
    rep(i,26) {
      sum += dp[0][i];
      if( sum >= K ) break;
    }
    if( sum < K ) return puts("Eel");
  }

  string answer = "";
  rep(i,(int)s.size()) {
    for(char c='a';c<='z';c++) {
      if( dp[i][c-'a'] == 0 ) continue;
      if( K > dp[i][c-'a'] ) { // i番目にcを置いてもKには到達しないので使わない
	K -= dp[i][c-'a'];
      } else { // 初めて K <= dp[i][c-'a'] となった場所なのでcを使う必要がある
	answer += string(1,c);
	while( s[i++] != c ); --i; // s[i] != c なら s[i] == c であるような場所まで進まなければいけない
	--K; 
	break;
      }
    }
    if( !K ) break;
  }
  cout << answer << endl;
}

int main() {
  cin >> s >> K;
  compute();
  return 0;
}