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