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はまあいいでしょう。２文字をスワップするだけなので簡単にできます。一方で、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のときは、

どっちの文字か？
そのインデックス

この２つを調べてあげる必要があります。

まずは、「どっちの文字か？」です。これは上にも書きましたが次のようになります。

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次元でいいじゃん、いつ役に立つんだよ。と私自身思ってましたが、この問題で役に立ちました。よかったよかった。

こういう問題は「いかに複雑化させないで解くか」がとても大切になると思います。なるべくシンプルにできる方法を探しましょう。

また、他にもrotateするやり方などもあるそうなので、興味がある方は是非調べて見てください。