Typical DP Contest - G 辞書順

G: 辞書順 - Typical DP Contest | AtCoder

class g_lexicographical_order {
public:
    void solve(void) {
            string S;
            ll     K;
            cin>>S>>K;

            // dp[i] := i 文字目の文字をつかい、i 文字以降の文字を使うまたはつかわないときのユニークな文字列総数
            //
            // 012345
            // abcdad
            // dp[3] = #{d,da,dad,dd} = 4
            // dp[4] = #{a,ad} = 2
            // dp[2] = #{c, ca, cad,cd, cda, cdd, cdad} = 7    (<- cd は一つだけ)
            //       = dp[3]+dp[4]
            vector<ll> dp(S.length(), 0);

            // find_first_of は最大 O(|S|) になってしまうので、出現した文字のインデックスを
            // メモしてそれを使うようにする。
            // next[i][c] := index i 以降で c 番目のアルファベットが初めて出現するインデックス(ないときは -1)
            // とする。
            vector<vector<int>> next(S.length()+1, vector<int>(26,-1));

            // O(|S|*26)
            dp[S.length()-1] = 1; // 末尾の文字は自身のみなので 1
            for (int i = S.length()-1; i >= 0; --i)
            {
                copy(RANGE(next[i+1]), next[i].begin());
                next[i][S[i]-'a'] = i;

               // S[i] の文字は必ず使う
               dp[i] = 1;
               for (int c = 0; c < 26; ++c)
               {
                   // S.find_first_of(c+'a') のかわりに next を参照する
                   // overflow するので判定に必要な最大値 K+1 で clip する
                   if (next[i+1][c] >= 0)
                       dp[i] = min(dp[i]+dp[next[i+1][c]], K+1);
               }
            }

           // dp table から復元する
           int pos = 0;
           string ans = "";
           while ( K > 0 )
           {
               int c = 0;
               for (; c < 26; ++c)
               {
                   if (next[pos][c] < 0)
                       continue;
                   if ( dp[next[pos][c]] < K ) // K 番目は (c+1)+'a' 以降の文字列から始まるケース
                       K -= dp[next[pos][c]];
                   else
                   {
                       ans += (c+'a');
                       pos = next[pos][c]+1;
                       --K;     // #{(c+'a')} 分引く
                       break;
                   }
               }
               if (c == 26)
                   break;
           }
           if ( ans.empty() )
               ans = "Eel";
           cout<<ans<<endl;
    }
};