Kazun の競プロ記録

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

AtCoder Beginner Contest 258 C問題 Rotation

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

長さ  N の英小文字列  S が与えられる. 次の  Q 個のクエリを順に処理せよ.

  • Type 1: 次の操作を  x 回連続で行なう.
    •  S の末尾の文字を削除し, その文字を先頭に挿入する.
  • Type 2: その時点での  S の先頭から  x 番目の英小文字を出力する.

制約

  •  2 \leq N \leq 5 \times 10^5
  •  1 \leq Q \leq 5 \times 10^5
  •  S は長さ  N の英小文字列
  •  1 \leq x \leq N

解法

Type 1 を愚直にやっていては間に合わない. しかし, 今回 Type 1 の操作は 「cyclic させる」であることに着目すると, 何回 cyclic させたかという記録をつけることにより Type 1, Type 2 を共に  O(1) 時間で処理できる. 具体的なアルゴリズムを以下に挙げる.

  •  C \gets 0
  • クエリごとに以下のように処理する.
    • Type 1:  C x を加算する.
    • Type 2:  S_{(x-C) \pmod N+1} を出力する.

従って, 計算量  O(N+Q) 時間で処理できた.