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