ABC410 C – Rotatable Array

C - Rotatable Array

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

この問題はクエリのタイプに従って処理を行う問題です。

この問題ではクエリのタイプ3の処理を高速化しないとTLEになってしまいます。

初期状態が以下だとします。

タイプ3のクエリで「 A の先頭の要素を末尾にする」という操作を2回行うと以下のようになります。

ここで offset を考えます。offset は「位置を基準点からの距離で表したもの」です。

最初は offset=0 です。上記の例で基準を 1,2,3,4,5 とすると、3,4,5,1,2 は2ずれているため offset=2 になります。

ここで注意点は操作がN以上の場合です。（入力例1では5）

例えば「 A の先頭の要素を末尾にする」という操作を7回する場合も2回の場合と同じ状態になります。

これはNのあまりを求めれば良いです。

つまり（offset + 操作の回数）% N が次の offset になります。

クエリのタイプ1と2もこの offset を使って算出します。

この状態で offset=2 としたとき、タイプ1のクエリが来たとします。

p=3 とすると 0スタートなので p は -1 して offset+p=4 、A[4] に変更する数xを代入します。

ただしここでも offset+p がN以上にならないよう、A[(offset+p)%N]にxを代入することになります。

タイプ2も同じ要領で求められます。

以下のコードでACできました。

def i_map():
    return map(int, input().split())


def i_list():
    return list(map(int, input().split()))


n, q = i_map()
a = list(range(1, n + 1))
flag = False
offset = 0

for i in range(q):
    query = input().split()
    if query[0] == "1":
        a[(int(query[1]) - 1 + offset) % n] = int(query[2])
    if query[0] == "2":
        print(a[(int(query[1]) - 1 + offset) % n])
        flag = True
    if query[0] == "3":
        offset = (int(query[1]) + offset) % n

if not flag:
    print()

def i_map():
    return map(int, input().split())


def i_list():
    return list(map(int, input().split()))


n, q = i_map()
a = list(range(1, n + 1))
flag = False
offset = 0

for i in range(q):
    query = input().split()
    if query[0] == "1":
        a[(int(query[1]) - 1 + offset) % n] = int(query[2])
    if query[0] == "2":
        print(a[(int(query[1]) - 1 + offset) % n])
        flag = True
    if query[0] == "3":
        offset = (int(query[1]) + offset) % n

if not flag:
    print()