ABC199 C 解答
C - IPFL (436)
問題文
長さ 2N の文字列 Sがあります。
この文字列に対して Q 個のクエリが与えられます。
i 番目のクエリでは 3 つの整数 Ti, Ai, Bi が与えられるので、以下の処理をします。
・Ti = 1のとき : S の Ai 文字目と Bi 文字目を入れ替える
・Ti = 2のとき : Sの前半 N 文字と後半 N文字を入れ替える( Ai, Biの値は用いない)
例えば S が FLIP のときにこのクエリを処理すると、S は IPFL となる。これら Q 個のクエリを与えられた順に全て処理した後の S を出力してください。
制約
1 ≤ N ≤ 2×10^5
S は長さ2Nの英大文字のみからなる文字列
1 ≤ Q ≤ 3×10^5
Ti は 1 または 2
Ti = 1 のとき、1 ≤ Ai < Bi ≤2N
Ti = 2 のとき、Ai = Bi = 0
考察
文字列をクエリごとに操作していく問題です。Ti = 1のときには2文字を入れかえ、Ti = 2 のときに 前半部分と後半部分を入れ替えます。
Ti = 1はまあいいでしょう。2文字をスワップするだけなので簡単にできます。一方で、Ti = 2 だと前半 N 文字、後半 N 文字を入れ替えるので、一つづつ行うと、N 回のスワップが必要となります。文字列の長さは 2 * N で N ≦2 * 10^5です。また、クエリは Q ≤ 3×10^5個飛んできますので、最も時間がかかる場合で 6 * 10^10 回のスワップが必要となります。これはちょっと厳しそうです。
ということで、 Ti = 2の処理を早くする方法を考えます。
フラグで管理して反転したとみなす、という賢い考え方もありますが、今回は前半部分と後半部分を分けて、それを実際に入れ替えることで問題を改善していきます。今回も例をあげましょう。
N = 5 : ABCDEFGHIJ
これを考えます。まず、前半部分と後半部分に分けてそれぞれ配列の0番目と1番目に入れてしまいましょう。
この状態になってしまえば、Ti = 2の処理は簡単にできます。配列の0番目と1番目に入っている文字を入れ替えればOKです。
とすると、次はTi = 1が少し変わってきてしまいます。
0~N-1文字目まではいいのですが、N~2N-1目の文字は後半の文字となります。そのため、Ti = 1のときは、
どっちの文字か?
そのインデックス
この2つを調べてあげる必要があります。
まずは、「どっちの文字か?」です。これは上にも書きましたが次のようになります。
0~N-1 : 配列[0]に入っている文字
N~2N-1:配列[1]に入っている文字
ですね。これは、与えられるインデックス a を用いて
a / N
で表すことが可能です(aを0インデックスに直す)。
続きまして、「そのインデックス」です。つまり何番目の文字か?ということです。前半部分であればそのままでいいのですが、後半部分であるなら N をひいてあげる必要があります。これをうまいことまとめますと、
a % N
です。これでTi=1用の変換の用意ができました。
あとはクエリに従って全部の処理をした後に、[0][1]の順番で出力すれば無事ACです。
実装
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;++i) #define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main()
{
int n,q;
string s;
cin >> n >> s >> q;
vector<string> v(2);
//substr(a,b)
//sのa番目からb文字を取得する
v[0] = s.substr(0,n);
v[1] = s.substr(n,n);
while(q--)
{
int t,a,b;
cin >> t >> a >> b;
if(t == 1){
--a,--b;
int sa = a / n;
int sb = b / n;
int idxa = a % n;
int idxb = b % n;
//v[a][b]とすると、
//v[a]に入ってる文字の b 番目にアクセス可能
swap(v[sa][idxa],v[sb][idxb]);
}
else swap(v[0],v[1]);
}
cout << v[0] << v[1] << endl;
return 0;
}
あとがき
余談です。Ti = 1の変換方法で、/Nと%Nをやりました。これは、2次元グラフを1次元化したり、画像データを格納したりするときにお世話になる考え方です。
2次元でいいじゃん、いつ役に立つんだよ。と私自身思ってましたが、この問題で役に立ちました。よかったよかった。
こういう問題は「いかに複雑化させないで解くか」がとても大切になると思います。なるべくシンプルにできる方法を探しましょう。
また、他にもrotateするやり方などもあるそうなので、興味がある方は是非調べて見てください。
この記事が気に入ったらサポートをしてみませんか?