Typical DP Contest G-辞書順

http://tdpc.contest.atcoder.jp/tasks/tdpc_lexicographical
一時間くらいでできたと思ったらそこから一時間以上デバッグしてやっと通しました。
　
　文字列 s の空でない部分列のうち、辞書順で K 番目のものを求めよ。そのようなものが存在しない場合は "Eel" (quotes for clarity) と出力せよ。

　という問題です。このコンテスト、典型問題を扱っているということもあるんでしょうが問題文が簡潔でわかりやすくてとても取り組みやすいです。某Jamとか、英語コンテストで問題文が長ったらしいと読解だけで15分かかったりしますからね……（英語勉強しろ）。
　dp[i][j] := i文字目以降の部分列で文字cから始まるものの個数
　とします。このdpは比較的簡単に解くことができます。
　例えば文字列abbcaがあったとします。
　このとき、三文字目のb以降を使ってできる部分文字列は、四文字目以降でできる部分文字列{c, a, ca}にbをくっつけた{bc, ba, bca}と{b}です。
　ですから、
　dp[i][s[i]] = dp[i + 1][a] + ... dp[i + 1][z] + 1
となります。
　これを前計算としてやっておいてからk番目の文字列を復元します。これはまあ実装ゲーとしか言いようがないです。

for(; a != s[i]; i++);

としているところを

for(int it = i; it < n; it++)
  if(s[it] == a){
      i = it;
      break;
  }

としないのが強いて言えばコツでしょうか。

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
ll dp[1000001][26];//i文字目以降の部分列で文字cから始まるものの個数
const ll LL_INF = 2000000000000000000;
void calc(int n, const string& s){
    ll sum = 1;
    int temp = s[n - 1] - 'a';
    dp[n - 1][temp] = 1;
    for(int i = n - 2; i >= 0; --i){
        int k = s[i] - 'a';
        rep(j, 26) dp[i][j] = dp[i + 1][j];
        dp[i][k] = 1;
        rep(j, 26){
            dp[i][k] += dp[i + 1][j];
            dp[i][k] = min(dp[i][k], LL_INF);
        }
    }
    return;
}
string rec(int n, ll k, const string& s){
    string res = "";
    rep(i, n){
        if(k == 0) return res;
        k--;
        rep(j, 26){
            if(k < dp[i][j]){
                char a = 'a' + j; res += a;
                for(; a != s[i]; i++);
                break;
            }
            k -= dp[i][j];
            if(j == 25) return "Eel";
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    string s;
    ll k;
    cin >> s >> k;
    int n = s.size();
    calc(n, s);
    cout << rec(n, k, s) << endl;
    return 0;
}

このくらいはもっとスムーズに解けるようにしておきたいものですがまだまだですね……。