C. ABBB (Codeforces Raif Round 1 Div. 1 + Div. 2)

Bでもよさそうな問題だと思いましたが、実際Bより正答者が多かった模様。

問題

https://codeforces.com/contest/1428/problem/C

問題概要

AとBからなる文字列が与えられる。文字列中に"AB"または"BB"があればそれを消去することができる。

消去した結果として得られる文字列のうちで長さが最小になるものの長さを答えよ。

考察

Bは"AB"でも"BB"でも消せますが、Aは"AB"でしか消せないので、Aを優先して消すことにします。

Bの数と最終的な文字列の長さ（つまり答え）を管理しながら文字列を後ろから見ていくとよいです。具体的には、BであればBの数を一つ増やします。Aであれば、そこまででBの数が0でないなら"AB"として消費するのでBの数を一つ減らして答えのカウントを2減らします。その操作が終わったら、Bのカウントが2n（偶数）か2n+1（奇数）になっているので、いずれにせよ答えから2nを減らします。つまり残された"BB"を消費するということです。

最後の操作で、Bはすべて"BB"として消費できるとして構いません。BとBの間にAがある場合、それは"AB"として消費されているはずなので、"AB"をすべて消費し終わった時点で"BBBBBBAAA"のように消費できなかったAは右側にすべて固まっていて、余ったBはすべて左側に固まっているからです。

#include <bits/stdc++.h>
using namespace std;
 
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define sz(v) (int)v.size()
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = sz(s);
        int b = 0;
        int ans = n;
        REPR(i, n) {
            if (s[i] == 'B') {
                b++;
            } else {
                if (b > 0) {
                    b--;
                    ans -= 2;
                }
            }
        }
        cout << ans - b / 2 * 2 << endl;
    }
}

余談

別に前から見ていってもいけそうですが、そうすると多分AとBの両方を数える必要があるのでちょっとだけ（本当にちょっとだけど）面倒かもです。