ABC [AtCoder Grand Contest 034 B]

https://atcoder.jp/contests/agc034/tasks/agc034_b

前提知識

• しゃくとり法

解説

https://atcoder.jp/contests/agc034/submissions/5779466

操作回数の最大値を求めよという問題が実はどんな操作をしてもその回数になってしまうという
パターンがあり、今回もそんな気がする。
これは何回か実験したところそうなったためである。
　
あとは、何回操作を行えるかというのを考えて行けばいい。
操作を言い換えると、A BCをBC Aに置き換えているので、A,BCのswapをする操作である。
ABCBCは2回操作を行える。
BBとかCCとかCBとかあると、Aは乗り越えることができない。
なにかの全探索を考えるとAで全探索すれば良さそう。
あるAが何個のBCを超えるかを右を伸ばして考えればいい。
例えば、AABCABCの最初のAはBCを2つ超えることになるので、2回分。
2つ目のAも2回分。3つ目のAは1回分。なので5が正解。
　
あるAについて、移動できる先は右端を伸ばして判定していくが、しゃくとり法的なやり方でこれはできる。
伸ばしていって、BCかA以外の組が出てきたら止めて、そこから左端を右に動かしていく。
左端が右端に到達したら、改めて右端を決めて左端を動かす。
提出コードでは左端を全探索して、右端を伸ばすしゃくとり法をしている。
応用的なしゃくとり法。
番兵でBBBBBを最後につけている（5個は適当。3個くらいで十分かも）。

int N;
string S;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> S;
	N = S.length();
	S += "BBBBB";

	ll ans = 0;
	int R = 0;
	int BC = 0;
	rep(L, 0, N) {
		if (S[L] == 'A') {
			if (R <= L) {
				BC = 0;
				R = L + 1;
				while (R < N) {
					if (S[R] == 'A') R++;
					else if (S[R] == 'B' and S[R + 1] == 'C') {
						BC++;
						R += 2;
					}
					else break;
				}
			}

			ans += BC;
		}
		else if (S[L] == 'B' and S[L + 1] == 'C') BC--;
	}
	cout << ans << endl;
}