クエリ問題を解いてみた
今日解いてた問題で自分が苦手だったのでメモ程度にまとめまふ
問題のURL
#ソースコード
N,Q = map(int,input().split())
A = list(map(int,input().split()))
rotate_cnt = 0
for _ in range(Q):
t,x,y = map(int,input().split())
x -= 1
y -= 1
if t == 1:
A[x-rotate_cnt],A[y-rotate_cnt] = A[y-rotate_cnt],A[x-rotate_cnt]
elif t == 2:
rotate_cnt += 1
if rotate_cnt > N:
rotate_cnt =0
elif t == 3:
print(A[x-rotate_cnt])
まずこの問題、愚直にやろうと思えばすごく簡単なんですがおそらく問題文をそのまま
やってしまうとTLEになると思います、、
てことで、どうやって計算量を減らしつつ解くかなんですけど
この問題Tが1,3のときはO(1)なので特に気にしなくて愚直にやればいいと思います。
問題は右にシフトするのを愚直にやってしまうと以下のようになります、、。
まずリストの要素数をN、そしてシフトする回数をKとおきます。
そうするとシフト1回にたいしてO(N)行われるので結果として
O(NxK)になってしまいます。要素数とクエリ回数の最大値を取って当てはめてみると
O(4x10^10)となってしまい、間に合いません。
なので何回シフトしたかを記録する変数rotate_cntを作ります。
Tが２のときrotate_cntを1つ足して行きます。そしてTが1,3のとき
与えられたx,yからrotate_cntを引いてあげれば右にシフトした挙動と同じになります。
どうしてかというと、、
(例)
あるリスト[1,2,3,4,5]が与えられたとします。(0-indexed)
そしてrotate_cnt=1、つまり右にシフトが1回行われたとします。
なので右に1回しふとしたときのリストが[5,1,2,3,4]となります。
まずT=1の時を説明します。
ここではインデックス番号2,3のときを説明します。
右に1回シフトした時のリストでの挙動は[5,1,3,2,4]となります。
次にrotate_cntを使ってやってみます。
右にシフトってことはインデックス番号が1つずつずれるという感じです。
つまり、今回は2,3をしたいのですが、ひとつ右にずれているので1つインデックスを戻すイメージで
2-rotate,3-rotateをしてあげることで挙動が同じになります。
Tが３のときも同様にずれている分戻してあげるイメージで大丈夫です。
またrotate_cntがNよりも大きくなったとき、それは
1,2,3,4,5
5,1,2,3,4
4,5,1,2,3
3,4,5,1,2
2,3,4,5,1
1,2,3,4,5
というふうに一周してるのでrotate_cntを０にしてあげます。
最後に
こういう問題はわかれば簡単なので5分から10分程度で解きたいですね。