この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/b301698295e6b6721b35
次：https://qiita.com/sano192/items/261790cbd90dbe6cf596
【目標】
・文字列の操作について、計算量を理解する
・反転、並び替えなどの操作について状態を管理する変数を使って計算量を減らす工夫を理解し、実装する
【概要】
一見「やるだけ」問題に見えるが問題文の通り実装するとT=2の入れ替えの処理がネックになり、TLE(実行時間制限超過)する。文字列の反転や並び替えをする問題は解き方のパターンが決まっている。この問題を通じてパターンを身に着けよう。
【方針】
T=2で行う文字列の並び替えは一見O(1)でできそうだが実際には文字列の長さをNとしてO(N)かかる。そのため問題文をそのまま実装するとN、Qが最大のケースでTLE(実行時間制限超過)する。
実際に入れ替え操作をする代わりに、今『通常状態』なのか『入替状態』なのかを変数で管理する、という方法を使う。
と言われてもよくわからないと思うので、例を見よう。
「例」
入力例
2
ABCD
2
2 0 0
1 1 4
N=2
S=ABCD
Q=2
最初は状態を『通常状態』としておく。
状態：『通常状態』
1番目のクエリ：2 0 0(T=2 入れ替え)
状態：『通常状態』→『入替状態』
に変更する。
(文字列には何もしない)
2番目のクエリ：1 1 4(T=1 1文字目と4文字目を入れ替え)
今、本来であれば1番目のクエリで
S=CDAB
となっているはずだから
1文字目と4文字目を入れ替える=CとBを入れ替える
ということになる。
しかし実際には文字の入れ替えを行っていないから、文字列は「ABCD」のままだ。
『通常状態』の文字と『入替状態』の文字を並べ、どの文字がどの場所に移動しているか確かめよう。
『通常状態』：ABCD
『入替状態』：CDAB
A：1文字目→3文字目(1+2)
B：2文字目→4文字目(2+2)
C：3文字目→1文字目(3-2)
D：4文字目→2文字目(4-2)
『通常状態』で半分より左にある文字は『入替状態』で+2文字目
『通常状態』で半分より右にある文字は『入替状態』で-2文字目
の位置に来ている事がわかる。
つまり『入替状態』でクエリ
1 1 4(T=1 1文字目と4文字目を入れ替え)
が来た場合は
1文字目→3文字目
4文字目→2文字目
と読み替えて入れ替えを行えば良い。
ゆえにABCDの3文字目と2文字目を入れ替えて
S=ACBD
となる。
最後に答えを出力するとき、状態が『入替状態』なら実際に入れ替えを行う。
S=ACBD
→S=BDAC
答え「BDAC」を出力する。
○文字目と○文字目を入れ替える
ではなく
どの文字とどの文字を入れ替える(上記例ならBとC)→それは何文字目に位置するか？
というように考えるとわかりやすいと思う。
もうひとつ具体例として入力例2をどのように処理するか見てみよう。
「入力例2」
2
FLIP
6
1 1 3
2 0 0
1 1 2
1 2 3
2 0 0
1 1 4
N=2
S=FLIP
Q=6
「1番目のクエリ：1 1 3(T=1 1文字目と3文字目を入れ替え)」
状態：『通常状態』
『通常状態』なので1文字目と3文字目を入れ替える。
操作後：ILFP
「2番目のクエリ：2 0 0(T=2 入れ替え)」
状態：『入替状態』
状態を変更する。ただし文字列には何もしない。
操作後：ILFP
「3番目のクエリ：1 1 2(T=1 1文字目と2文字目を入れ替え)」
状態：『入替状態』
現在の状態が『入替状態』のため、入れ替える文字が変わる。
1文字目→N以下=半分より左=1+N=1+2=3文字目
2文字目→N以下=半分より左=2+N=2+2=4文字目
つまり
1文字目→3文字目
2文字目→4文字目
と読み替え、3文字目と4文字目を入れ替える。
操作後：ILPF
「4番目のクエリ：1 2 3(T=1 2文字目と3文字目を入れ替え)」
状態：『入替状態』
現在の状態が『入替状態』のため、入れ替える文字が変わる。
2文字目→N以下=半分より左=2+N=2+2=4文字目
3文字目→Nより大きい=半分より右=3-2=1=1文字目
つまり
2文字目→4文字目
3文字目→1文字目
と読み替え、4文字目と1文字目を入れ替える。
操作後：FLPI
「5番目のクエリ：2 0 0(T=2 入れ替え)」
→状態を変更
状態：『通常状態』
状態を変更する。ただし文字列には何もしない。
操作後：FLPI
「6番目のクエリ：1 1 4(T=1 1文字目と4文字目を入れ替え)」
状態：『通常状態』
『通常状態』なので1文字目と4文字目を入れ替える
操作後：ILPF
答え：ILPF
【実装】
まずは入力をQまで受け取る。
N=int(input())
S=input()
Q=int(input())
Sについてそのまま扱うと1文字目が0インデックスで0文字目になり処理が面倒。Sの先頭に「0」という文字を追加し、入力で与えられた文字が1文字目となるようにしよう。
S="0"+S
Sの入力が「FLIP」だった場合、現在のSは「0FLIP」となっている。これで「F」をインデックス番号1=1文字目として扱うことができる。
さらにこのままだとA文字目とB文字目を入れ替える、という操作が面倒なのでリストにしてしまおう。
S=list(S)
これでSの入力が「FLIP」だった場合
S[1]=F
S[2]=L
S[3]=I
S[4]=P
とそれぞれの文字を取り出して入れ替えすることができる。
次に状態を管理する変数を用意する。つまり『通常状態』と『入替状態』を管理する変数だ。ここではflipという名前にしよう。
flip=False
『通常状態』ならFalse
『入替状態』ならTrue
とする。最初は『通常状態』なのでFalse。
ここからクエリの処理に移る。
T、A、Bを受け取り、まず『通常状態』の場合について処理を書く。
『通常状態』のときはA文字目とB文字目をそのまま入れ替えるだけで良い。
for i in range(Q):
T,A,B=map(int, input().split())
if T==1:
if flip==False:
S[A],S[B]=S[B],S[A]
S[A],S[B]=S[B],S[A]
というのが入れ替えの処理。
pythonでは
x,y=y,x
と書くことでxの値をyに、yの値をxに代入してくれる。よく使う書き方なのでぜひ覚えてほしい。
次に『入替状態』の場合について処理を書く。
AがN以下=半分より左→A+N文字目
AがNより大きい=半分より右=A-N文字目
と入れ替える文字を変更する。Bについても同様。
else:
if A<=N:
A+=N
else:
A-=N
if B<=N:
B+=N
else:
B-=N
S[A],S[B]=S[B],S[A]
T=2のときは『通常状態』→『入替状態』、『入替状態』→『通常状態』に変更するだけ。
# T=2
else:
if flip==True:
flip=False
else:
flip=True
クエリの処理が終わったら答えを出力する。
ただしクエリの終了時に『通常状態』なのか『入替状態』なのかで処理が変わる。
まず文字列の左半分と右半分を取り出す。
(左半分については0文字目に”0”を入れているからインデックス1から取り出す)
S_left=S[1:N+1]
S_right=S[N+1:]
・『通常状態』の場合
左半分と右半分をそのまま結合
・『入替状態』の場合
右半分+左半分と入れ替えして結合
if flip==False:
ans=S_left+S_right
else:
ans=S_right+S_left
最後にans(=リスト)を結合して出力する。
print("".join(ans))
“”.join(リスト)
と書くことでリストの中身を結合してくれる。あまり馴染みのない書き方かもしれないが、「python 文字列 結合 リスト」で検索すればすぐに出てくるので無理に暗記する必要はない。
【コード全文】
N=int(input())
S=input()
Q=int(input())
S="0"+S
S=list(S)
flip=False
for i in range(Q):
T,A,B=map(int, input().split())
if T==1:
if flip==False:
S[A],S[B]=S[B],S[A]
else:
if A<=N:
A+=N
else:
A-=N
if B<=N:
B+=N
else:
B-=N
S[A],S[B]=S[B],S[A]
# T=2
else:
if flip==True:
flip=False
else:
flip=True
S_left=S[1:N+1]
S_right=S[N+1:]
if flip==False:
ans=S_left+S_right
else:
ans=S_right+S_left
print("".join(ans))
この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/b301698295e6b6721b35
次：https://qiita.com/sano192/items/261790cbd90dbe6cf596