typical90f

6問目！！

5問目はムズすぎて飛ばしました.

社内コンテストに向けてだから…ね

一周したらまた戻ります

パッと見でDPかなーって思ったけどO(NK)とか10^10だしなぁ

辞書順だから貪欲か？でも選び方分かんねぇーって事で解説へ

後ろから精査して前から何番目に出てくるかの表を作れば良いのかなるほど

いやー難しい…

#include<bits/stdc++.h>

using namespace std;

int n, k;

string s;

int a[100009][26];

int main(){

    cin >> n >> k;

    cin >> s;

    for(int i=0;i<26;i++) a[n][i] = n;

    for(int i=n-1;i>=0;i--){

        for(int j=0;j<26;j++){

            if( ('a'+j) == s[i]) a[i][j] = i;

            else a[i][j] = a[i+1][j];

        }

    }

    int pos = 0;

    string ans = "";

    for(int i=0;i<k;i++){

        for(int j=0;j<26;j++){

            int nxt = a[pos][j];

           

            if(n-nxt >= k-i){

                ans += ('a' + j);

                pos = a[pos][j] + 1;

                break;

            }

           

        }

    }

   

    cout << ans << endl;

}