はまやんはまやんはまやん

hamayanhamayan's blog

Villages and Tribes [CodeChef November Challenge 2017 A]

https://www.codechef.com/NOV17/problems/VILTRIBE
N文字の'A','B','.'からナなる文字列がある。
AはAの領地、BはBの領地である。
それ以外は、Aに挟まれていればAの領地、Bに挟まれていればBの領地となる。
Aの総領地、Bの総領地数を答えよ。

A..A..B...B -> AAAA..BBBBB -> 4 5
..B..B..B.. -> ..BBBBBBB... -> 0 7

解法

同じ文字による区間を数えるテクなのだが、前の文字とその文字の座標を記録しておき、
それを利用しながら、順番に数えていく。

string S;
void solve() {
    cin >> S;
    int a = 0, b = 0;
    char c = '?'; int pre = -1;
    rep(i, 0, S.length()) if(S[i] != '.') {
        if (c == S[i]) {
            if(c == 'A') a += i - pre;
            else b += i - pre;
 
            pre = i;
        } else {
            if (S[i] == 'A') a++;
            else b++;
            
            c = S[i], pre = i;
        }
    }
 
    printf("%d %d\n", a, b);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}