ARC071 E - TrBBnsformBBtion

解法

どんな文字列でも"A"or"B"or""の3種類のどれかにすることができる。そのため無限にある文字列を"A"にできる文字列、"B"にできる文字列、""にできる文字列の3つのグループに分けることができる。"A"にできる文字列は逆に"A"から作ることができる。"B"、""にできるグループについても同様である。

よってクエリで与えられる文字列SとTが"A"、"B"、""のどれにできるかわかれば良い。同じ時YES、そうでない時NOを出力すれば良い。

"AB"->"","AAA"->"","BBB"->"","AA"->"B","BB"->"A"なので"A"の個数と"B"の個数を3で割った数を求め、どのグループに属するか求める。

(解説によるとA=1, B=2として和を3で割った値でグループ判定すれば楽だった)

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  string S, T;
  cin >> S >> T;
  int slen = S.length();
  int tlen = T.length();
  int SA[slen+1], SB[slen+1];
  int TA[tlen+1], TB[tlen+1];
  SA[0] = SB[0] = 0;
  TA[0] = TB[0] = 0;
  FOR(i,0,slen) SA[i+1] = SA[i] + (S[i] == 'A');
  FOR(i,0,slen) SB[i+1] = SB[i] + (S[i] == 'B');
  FOR(i,0,tlen) TA[i+1] = TA[i] + (T[i] == 'A');
  FOR(i,0,tlen) TB[i+1] = TB[i] + (T[i] == 'B');
  int q; cin >> q;
  FOR(i,0,q) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int sa = (SA[b] - SA[a-1]) % 3; // Aの数
    int sb = (SB[b] - SB[a-1]) % 3; // Bの数
    int ta = (TA[d] - TA[c-1]) % 3; // Aの数
    int tb = (TB[d] - TB[c-1]) % 3; // Bの数
    int check_a, check_b;
    if(sa == sb) check_a = 0;
    if(sa == 2 && sb == 1) check_a = 1;
    if(sa == 0 && sb == 2) check_a = 1;
    if(sa == 1 && sb == 0) check_a = 1;
    if(sa == 1 && sb == 2) check_a = 2;
    if(sa == 2 && sb == 0) check_a = 2;
    if(sa == 0 && sb == 1) check_a = 2;
    if(ta == tb) check_b = 0;
    if(ta == 2 && tb == 1) check_b = 1;
    if(ta == 0 && tb == 2) check_b = 1;
    if(ta == 1 && tb == 0) check_b = 1;
    if(ta == 1 && tb == 2) check_b = 2;
    if(ta == 2 && tb == 0) check_b = 2;
    if(ta == 0 && tb == 1) check_b = 2;
    cout << (check_a == check_b ? "YES" : "NO") << endl;
  }
}