AtCoder arc166 A - Replace C or Swap AB

A - Replace C or Swap AB

公式解説 を元に解いたのでメモ。

解説を見てもなかなかシュッと実装できなくて難しい

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int t; cin >> t;
  REP(_,t) {
    int n; string x,y;
    cin >> n >> x >> y;
    x += 'C'; y += 'C'; // 番兵
    n++; // 番兵分を +1
    map<char,vector<int>> mx,my;

    auto check = [&]() -> bool {
      int diff = my['A'].size() - mx['A'].size();
      // X の A の数が多ければ false
      // Y の A の数が多いときは X の C のよりも差分多ければ false
      if (diff < 0 || (int)mx['C'].size() < diff) return false;

      // X の C を早く出現するものから A に置き換える
      REP(i,diff) mx['A'].push_back(mx['C'][i]);
      sort(mx['A'].begin(),mx['A'].end());
      // 両者の A の出現位置を調べる
      REP(i,(int)my['A'].size()) if (my['A'][i] < mx['A'][i]) return false;
      return true;
    };

    bool ok = true;
    REP(i,n) {
      mx[x[i]].push_back(i);
      my[y[i]].push_back(i);
      if (y[i] == 'C') {
        ok = ok && x[i] == 'C' && check();
        mx.clear(); my.clear();
      }
    }
    cout << (ok ? "Yes" : "No") << endl;
  }
  return 0;
}