2016-08-25 Codeforces AIM Tech Round 3 (Div. 1) A. Letters Cyclic Shift 問題ページ 問題概要 文字列が与えられる。空でない連続する区間の文字を巡回シフト(z→y→x→…→b→a→z)して作れる辞書順最小の文字列を求めよ。 解法 a 以外の文字は巡回シフトをした方が得をするので、なるべく先頭に近い a 以外の文字だけを含む区間を巡回シフトすればいい。 たとえば aaabbbbaabba だったら aaabbbbaabba を巡回シフトする。 例外として、すべてが a のときはそのような区間が存在しないため、末尾の a を z に変える。 これは簡単。