[典型90] 006 - Smallest Subsequence（★5）

[Q] https://atcoder.jp/contests/typical90/tasks/typical90_f
セグ木で29ms。
1. できあがる辞書順最小文字列について。"baa"より"azz"のほうが若いので、先頭もじをできるだけ若いアルファベットに確定させていけばいい。
2. K文字作るので、K回探索すればいい。探索範囲は、
左側は、見つかった文字+1のindex
右側は、N-Kから+1ずつ

Q
. 入力例1
7 3
atcoder

・1文字目
少なくとも3文字とらないといけないので、うしろ2文字を残して
atcoder
-----
atcod の中から1文字を選ぶ必要がある。
探索範囲を変数にもって管理。

ll left = 0 index
ll right = 4 index

この中で最もアルファベットが早いのは 'a' なので、
string ans = "a"　確定。

'a' のindex は 0 なので、次のleftは
left = 0+1 = 1
次のrightは、1文字進めるので、
right = 4+1 = 5

・2文字目
atcoder
1-----
 tcode の中から1文字を選ぶ。

'c' が最も早いアルファベットなので、
ans = "ac"
S[2] = 'c'なので
left = 2+1 = 3 // 採用したアルファベットの次のindex
right = 5+1 = 6 // 1個進める

・3文字目
atcoder
1 2----
   oder の中から1文字を選ぶ。
'd'が最も早いアルファベット
ans = "acd"

解答は "acd"

Q. アルファベットが早い文字をどう探索するの？
A. セグ木で出したり、priority_queue<文字, index> で出したり、または26文字しかないから26文字全探索するなど。

1. priority_queue 19ms

using pcl=pair<char, ll>;

int main(){
 ll N, K;
 string S;
 cin >> N >> K >> S;
 priority_queue<pcl, vector<pcl>, greater<pcl>> Q;
 rep(i, N-K+1){ // "atcod" までいれる
   Q.push({S[i], i});
 }
 ll pos = -1; // 前にとったindex
 ll k = K;
 string ans;
 while (k > 0){
   auto p = Q.top();
   Q.pop();
   if (pos > p.second) continue; // 取り出した文字が、先頭より若いなら無効
   ans += p.first;
   pos = p.second;
   k--;
   if (k) Q.push({S[N-k], N-k}); // おしりの文字を追加
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/typical90/submissions/23298044

2. セグ木 29ms

int main(){
 cincout();

 ll N, K;
 string S;
 cin >> N >> K >> S;
 
 RangeMin Z;
 Z.init(N);
 rep(i, N){
   Z.update(i, S[i]); // {id, val}
 }
 string ans;
 ll L=0;
 ll R=N-K+1; // 5
 rep(i, K){
   char low = Z.query(L, R); // [0,5)文字目のうち、最も若いアルファベットを採用
   ans += low;
   while (L<N && S[L] != low) ++L; // 採用した文字まで先頭を進める
   ++L;
   ++R; // おしりの探索範囲を1個進める
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/typical90/submissions/27597397

3. 全探索 12ms

int main(){
 cincout();
 
 ll N, K;
 string S;
 
 cin >> N >> K >> S;
 ll L=0;
 ll R=N-K+1;
 string ans;
 rep(k, K){
   bool fin = false;
   for(char c='a'; c<='z'; ++c){ // 'a'~'z' まで全探索
     for(ll i=L; i<R; ++i){ // 探索範囲をぐるぐるまわる
       if (S[i] == c){ // 見つかったら1文字確定終了
         fin = true;
         ans += c;
         L=i+1; // 先頭の探索範囲を狭める
         ++R; // おしりを1文字伸ばす
         break;
       }
     }
     if (fin) break;
   }
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/typical90/submissions/27597645