003 - AB → BAA　解説

解説

　操作 '$\text{AB}$' $\to$ '$\text{BAA}$' を何度行っても、文字列中の '$\text{B}$' の数は変化しません。したがって、$S$ と $T$ で '$\text{B}$' の数が異なる場合は '$\text{No}$' です。

　'$\text{B}$' を仕切りとして文字列をブロックに分けると、操作は「左のブロックの '$\text{A}$' を $1$ つ消費し、右隣のブロックに '$\text{A}$' を $2$ つ生成する」ことと同等になります。'$\text{A}$' は左から右へしか移動・増殖できないため、左のブロックから順に貪欲に処理するのが最善です。

　$S$ と $T$ を '$\text{B}$' で分割した各ブロックの '$\text{A}$' の個数について、左から順に以下のように貪欲法を行います。

• 現在のブロックで $S$ 側の '$\text{A}$' が不足する場合（右から持ってきて補う手段はないため）即座に '$\text{No}$' と判定する。
• 余った '$\text{A}$' は、すべて $2$ 倍にして次の右隣のブロックへ持ち越す。

　なお、持ち越す '$\text{A}$' の数は指数関数的に増える可能性がありますが、$T$ の長さである $2 \times 10^5$ を超えた分は打ち切って（上限をかけて）問題ありません。最後のブロックまで処理して余りがぴったり $0$ になれば '$\text{Yes}$'、余っていれば '$\text{No}$' です。計算量は $O(|S| + |T|)$ となります。

コード例

以下はC++による想定解法のコードです。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string S, T;
    if (!(cin >> S >> T)) return 0;
    
    if (count(S.begin(), S.end(), 'B') != count(T.begin(), T.end(), 'B')) {
        cout << "No\n";
        return 0;
    }
    
    auto get_a = [](const string& s) {
        vector<long long> a;
        long long cnt = 0;
        for (char c : s) {
            if (c == 'A') cnt++;
            else { a.push_back(cnt); cnt = 0; }
        }
        a.push_back(cnt);
        return a;
    };
    
    auto A = get_a(S), B = get_a(T);
    long long rem = 0, LIMIT = 300000;
    
    for (size_t i = 0; i < A.size(); ++i) {
        rem = rem * 2 + A[i] - B[i];
        if (rem < 0) {
            cout << "No\n";
            return 0;
        }
        rem = min(rem, LIMIT);
    }
    
    cout << (rem == 0 ? "Yes\n" : "No\n");
    return 0;
}