Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 223 B 問題 String Shifting

AtCoder ABC ABC223 B問題 200 pts

問題

提出解答

問題の概要

文字列 $S$ に対して, 右シフト, 左シフトを何回か施してできる文字列のうち, 辞書式最小と最大を求めよ.

制約

$1 \leq |S| \leq 1000$

解法

操作の結果, 出来上がる文字列は以下のような文字列はすべてでき, 以下のような文字列しかできない. ただし, 文字列 $S_i$ で $S$ の左から $i$ 文字目を表すとする.

$S_k S_{k+1} \cdots S_N S_1 \cdots S_{k-1}~(k=1,2, \dots, N)$

よって, $k=1,2, \dots, N$ に対する文字列をすべて生成し, そのまま辞書式最小と最大を求めることができる.