Arithmetic Right Shift

2 secs 1024 MB

まず、 $S$ の先頭に $S$ の $1$ 文字目の文字を結合し、 $S$ の末尾の文字を削除する処理を実装しましょう。
C++ では std::string 、Python では str に対する文字列操作を行えば良いです。

ただし、このような算術右シフトを愚直に $K$ 回繰り返すと、 $1$ テストケースごとに最大 $10^9$ 回の繰り返し処理を行うことになり、実行時間制限に間に合いません。

そこで、 $K \ge |S|$ となる場合に $S$ の $1$ 文字目の文字が $|S|$ 個連続する文字列になることを利用し、繰り返し処理の回数を高々 $|S|$ 回に抑えると良いです。

繰り返し処理の回数を $\min (K, |S|)$ 回にしたり、 $K \ge |S|$ の場合を分ける位方針を取ることで、十分高速に動作します。

解説