ARC071_E TrBBnsformBBtion

競技プログラミング AtCoder

問題

‘A'と'B'からなる文字列に対して

  1. ‘A’ -> ‘BB'、'B’ -> ‘AA'と変換
  2. ‘AAA'か'BBB'という部分文字列を削除

のいずれかの操作が可能である。 文字列S, TとQ個のクエリ(ai,bi,ci,di)が与えられる。各クエリは部分文字列S[ai]…S[bi]、T[ci]…T[di]に対応しており、両者を同じ文字列に変換できるかを判定せよ。

方針

全部の文字列をA（もしくはB）に置き換え、文字列の長さの差が3で割り切れれば同じ文字列にすることができ、そうでなければ出来ない。

ここでは、文字列を全てAにして比較する。 クエリごとに文字列の比較をしていくと間に合わないので、事前に累積和を計算しておく。 ここでいう累積和は、文字列をすべて'A'に変換するとき、i番目までの文字数である。 文字列S,Tそれぞれについて、Aなら1、Bなら2の足していく。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;

int main() {
    string s, t;
    cin >> s >> t;
    vector<int> s_sum(100010), t_sum(100010);
    for(int i=0;i<s.size();i++) {
        int add;
        if(s[i] == 'A') add = 1;
        else add = 2;
        s_sum[i+1] = s_sum[i] + add;
    }
    for(int i=0;i<t.size();i++) {
        int add;
        if(t[i] == 'A') add = 1;
        else add = 2;
        t_sum[i+1] = t_sum[i] + add;
    }


    int q;
    cin >> q;
    vector<string> ans;
    for(int i=0;i<q;i++) {
        int a, b, c, d, num_s, num_t;
        cin >> a >> b >> c >> d;

        num_s = s_sum[b] - s_sum[a-1];
        num_t = t_sum[d] - t_sum[c-1];
        if(abs(num_s-num_t)%3 == 0)
            ans.push_back("YES");
        else
            ans.push_back("NO");
    }
    for(int i=0;i<q;i++) 
        cout << ans[i] << endl;
}