[Python] 計算量 ABC199C

ABC199C

１文字を入れ替える操作の計算量は$O(1)$である。$T=2$のとき、前半と後半を１文字ずつ入れ替える操作は$O(N)$となり、合計$O(QN)$で間に合わない。この操作処理を単純化すると、indexにnを加え2nのmodを取ることで実装できる。
合計計算量は$O(N+Q)$となり十分である。本番ではほぼ同様の設計まではしたのだが、計算量の評価に自信が持てずパスしてしまった。当投稿は、計算量の見積もりを正確にしなくてはならないという反省によるものである。

蛇足かもしれないが、Atcoderで公式にユーザー解説が付くようになった結果、多様な解説が投稿されなくなっている状況であるようだ。公式解説はともかく、ユーザー解説は載せなくて良いのではないかと個人的には思う。

サンプルコード

n=int(input())
S=list(input())
Q=int(input())

ind=0
for i in range(Q):
    t,a,b=map(int,input().split())
    a=a-1
    b=b-1
    if (t==1): # T=1
        S[(ind+a)%(2*n)],S[(ind+b)%(2*n)]=S[(ind+b)%(2*n)],S[(ind+a)%(2*n)]

    else: # T=2
        ind=(ind+n)%(2*n)


S=S[ind:]+S[:ind]
print(*S,sep="")