【ABC409】D問題 - String Rotation 考察から実装(c++)まで

AtCoderBeginnerContest409の解説＆感想です。
コンテストリンク

問題一覧

• 【ABC409】A問題 - Conflict　考察から実装(c++)まで
• 【ABC409】B問題 - Citation　考察から実装(c++)まで
• 【ABC409】C問題 - Equilateral Triangle　考察から実装(c++)まで
• 【ABC409】D問題 - String Rotation　考察から実装(c++)まで <- イマココ
• 【ABC409】E問題 - Pair Annihilation　考察から実装(c++)まで
• 【ABC409】F問題 - Connecting Points　考察から実装(c++)まで

D問題 - String Rotation

問題リンク

問題概要

英小文字からなる長さ$N$の文字列$S$が与えられる。$S$に対して以下の操作を一回行う。

• 長さ$1$以上の連続部分列を選んで、それを左に$1$シフトする。

操作後の$S$としてあり得るもののうち、辞書順最小のものを求めよ。
$T$個のテストケースにそれぞれ答えよ。

制約

• $ 1 \le T \le 10^5 $
• $ 1 \le N \le 10^5 $
• $ Nの総和は10^5以下 $

考察

「辞書順最小を求めよ」と言われたら頭から貪欲に決めていくのは典型と言っても良さそう。
今回も先頭から一つずつ見ていって、最初に小さくできる（$S[i] > S[i+1]$となっている
）ところを見つけたらそこを小さくしていくのが答えになる。
あとは$S[i]$をどこに入れるかだけど、$S[i]$より大きいやつよりは手前に入れたいので、$i+1$番目以降で$S[i] < S[j]$となる最初のjを見つけて、その手前に入れればいい。
計算量は$O(N)$

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;

int solve(){
    //入力
    ll N;
    string S;
    cin>>N>>S;
    
    //最初にS[i] > S[i+1]となる場所を探す
    ll idx = adjacent_find(S.begin(), S.end(), [&](char c1, char c2){ return c1 > c2;  }) - S.begin();
    
    //S[i] > S[i+1]となる場所がなければ、どこをシフトさせても辞書順で大きくなってしまうので、そのままにしておく
    if(idx == N){
        cout<<S<<endl;
        return 0;
    }
    
    //idxより先で、S[idx]より大きくなるなる最初の場所をさがす
    ll nxtIdx = find_if(S.begin()+idx+1, S.end(), [&](char c){ return c > S[idx]; }) - S.begin();
    
    //idxまではそのまま表示
    for(int i=0;i<idx;i++) cout<<S[i];
    
    //idx番目は一旦抜かして、nxtIdxの手前まで表示
    for(int i=idx+1;i<nxtIdx;i++) cout<<S[i];
    
    //挿入したS[idx]を表示して、残りを表示
    cout<<S[idx];
    for(int i=nxtIdx;i<N;i++) cout<<S[i];
    
    cout<<endl;
    return 0;
}

int main(void){
    ll T;
    cin>>T;
    while(T--) solve();
    return 0;
}