競技プログラミング用 知識集積所
ABC409D - String Rotation
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
辞書順最小は、とにかく前の文字を優先する貪欲法（アルゴリズム系）（未作成）で考えればよい。
つまり、前から順に見ていって、初めて「1つ後ろの方がアルファベット前じゃね？」となったところがl。
その文字を1つずつ順に後ろに移動する。
その文字を1つずつ順に後ろに移動する。
どこまで移動するかだが、動かしている文字よりもアルファベット順が後ろの文字に当たるまで。
同じ文字だった場合は入れ替える扱いにして損することはないので、入れ替えを続行しておく。
同じ文字だった場合は入れ替える扱いにして損することはないので、入れ替えを続行しておく。
いずれの探索も、もし該当する場所がなかった場合は文字列終端を該当箇所とすればよい。
コンテスト中に「操作をちょうど1回行わなければならない」と補足されたが、実はl=rの場合は何も起きないので、1回も行わない場合が許可されていてもそうでなくても実は関係ない。
