AGC034 B - ABC (600)

B - ABC

概要

A, B, Cからなる文字列がある。この文字列の部分文字列のうちABCの部分をBCAに変える操作を好きなだけ行う。操作が行える最大の回数を答えよ。

制約

1 ≦ |s| ≦ 200 000

方針

①前から順に操作したいが、次の例のように後ろを走査した後に前が再び操作可能になる例がある。
ABCABC⇒BCAABC⇒BCABCA⇒BCBCAA

②AAAABCのような形は操作がどんどん前にさかのぼってゆく。
AAAABC⇒AAABCA⇒AABCAA⇒ABCAAA⇒BCAAAA
この操作ではBCの前の連続したAの個数だけ操作可能。

これら2つの考察より次のような操作を考えると、実際にこの操作方法が回数最大となるようだ。

• 連続したAの後にBCが来る場合、連続するAの個数をカウントしておき②の操作を行い、カウント分操作回数に加える
• BCの直後にAがくると、BCの前に連続していたAとその後のAがつながるのでAのカウントは継続される（①のケースでは、最初のABCはカウント1、直後にAがくるのでカウント継続、その後のBCではカウント2になっている。トータルの操作回数は1+2=3である。）
• それ以外ではカウントがリセットされる（後ろから前に操作がさかのぼることはない）

解答

Submission #5782620 - AtCoder Grand Contest 034

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	string s;
	cin >> s;
 
	int n = s.size();
	if(n <= 2){
		cout << 0 << endl;
		return 0;
	}
 
	ll ans = 0;
	ll acnt = 0;
	for(int i = 0; i < n - 1; ){
		if(s[i] == 'B' && s[i+1] == 'C'){
			ans += acnt;
			i += 2;
		}else if(s[i] == 'A') {
			acnt++;
			i++;
		}else{
			acnt = 0;
			i++;
		}
	}
 
	cout << ans << endl;
 
}