pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces AIM Tech Round 3 (Div. 1) A. Letters Cyclic Shift

問題ページ

問題概要

文字列が与えられる。空でない連続する区間の文字を巡回シフト(z→y→x→…→b→a→z)して作れる辞書順最小の文字列を求めよ。

解法

a 以外の文字は巡回シフトをした方が得をするので、なるべく先頭に近い a 以外の文字だけを含む区間を巡回シフトすればいい。

たとえば aaabbbbaabba だったら aaabbbbaabba を巡回シフトする。

例外として、すべてが a のときはそのような区間が存在しないため、末尾の a を z に変える。

これは簡単。