ABC199 C問題考察

C - IPFL

Ti = 1,2 の2種類のクエリが与えられますが、Ti = 2 の場合に毎回前後を入れ替えるという操作をすると時間がかかりすぎてしまうようです。
(具体的な計算時間については詳しくは知らないのですが)

ちなみに、前後を入れ替えるという操作はC++,Pythonでそれぞれ以下のように書けますね。

// C++
// s.length() == 2*n
s = s.substr(n) + s.substr(0,n)

# Python
# len(s) = 2*n
s = s[n:] + s[:n]

(↑のPythonのコードで s[n:] + s[:n+1] と書いてしまっていたため訂正しました 2021/04/25 12:00)

そこで、入れ替えるという情報をフラグとして持っておきます。

// C++
bool rev = false;
for (int i = 0; i < m; i++) {
  // t,a,bを入力
  if (t == 2) rev = !rev;
  else {
    // ~~ 省略 ~~
  }
}

# Python
rev = False
for i in range(m):
  # t,a,bを入力
  if t == 2:
    rev = !rev
  else:
    # 省略

そして、Ti = 2 が入力されるたびにフラグを反転することで、今この文字列の前後は入れ替えられているかをフラグで管理します。

ただ、これだとTi = 1 が入力された時の処理にも影響が出てしまいますので、Ti = 1 にも工夫をします。

// C++
if (t == 1) {
  if (rev) {
    if (a < n) a += n;
    else a -= n;
    
    if (b < n) b += n;
    else b -= n;
  }
  // ~~ 入れ替え処理 ~~
}

# Python
if t==1:
  if rev == True:
    if a < n:
      a += n
    else:
      a -= n
      
    if b < n:
      b += n
    else:
      b -= n
  # ~~ 入れ替え処理 ~~

a,b が左側にある場合は、実際は入れ替えられて右側に来ているので n を加算することで補正します。
逆に、右側にある場合も n を減算することで補正することができます。

--- 追記 ---

上の説明がわかりづらい気がしたので、付け足します。

例えば、「 xxxAx xxBxx」の左右を入れ替えてからA,Bを入れ替えるとします。
(クエリでは、「2,0,0」「1,3,7」のようになりますね。)

このとき、「xxxAx xxBxx」→「xxBxx xxxAx」→「xxAxx xxxBx」となります。

しかし、最初の 2 のクエリをやったふりだけをして 3 と 7 の場所を入れ替えても期待する結果は得られません。

そこで、3 というのは (左側のスタート地点) + 3 とも捉えられますから、 (右側のスタート地点)+3 というように書き換えます。
同様に、 7 は  (境界の値 = 5) + 2 となりますから、(左側のスタート地点) + 2 というように書き換えます。

ここで大切になるのが、n = 境界の値 = 5 という数字です。

これらのことを踏まえると上のような条件分岐になるのではないでしょうか。

(ここまで書いて気づいたのですが、長々とこんなに書かなくてもこのように2行だけで簡単に実装できましたね。)

C の位置の変換、
A = (A + N) % (N * 2);
B = (B + N) % (N * 2);
ってやった

— SSRS (@SSRS_cp) April 24, 2021

------------

最後に出力するときは、フラグが True なら表示の順番に注意します。

これらの処理をすることで、以下のコードになります。

#include<iostream>
using namespace std;
int main() {
 int n, q;
 string s;
 cin >> n >> s >> q;
 bool rev = false;
 for (int i = 0; i < q; i++) {
   int t,a,b;
   cin >> t >> a >> b;
   
   if (t == 1) {
     a--;
     b--;
     if (rev) {
       if (a < n) a += n;
       else a -= n;
       if (b < n) b += n;
       else b -= n;
     } 
     char tmp = s[a];
     s[a] = s[b];
     s[b] = tmp;
   } else {
     rev = !rev;
   }
   
 }
 if (rev) cout << s.substr(n) + s.substr(0, n) << endl;
 else cout << s << endl;
}