AtCoder Beginner Contest 258 C問題 Rotation
問題
提出解答
問題の概要
長さ の英小文字列
が与えられる. 次の
個のクエリを順に処理せよ.
- Type 1: 次の操作を
回連続で行なう.
の末尾の文字を削除し, その文字を先頭に挿入する.
- Type 2: その時点での
の先頭から
番目の英小文字を出力する.
制約
は長さ
の英小文字列
解法
Type 1 を愚直にやっていては間に合わない. しかし, 今回 Type 1 の操作は 「cyclic させる」であることに着目すると, 何回 cyclic させたかという記録をつけることにより Type 1, Type 2 を共に 時間で処理できる. 具体的なアルゴリズムを以下に挙げる.
- クエリごとに以下のように処理する.
- Type 1:
に
を加算する.
- Type 2:
を出力する.
- Type 1:
従って, 計算量 時間で処理できた.