一発 AC への第一歩:AB Substring

問題

考察

ザックリ以下のアプローチが必要となることが分かる。
i).入力 Si に "AB" が何個入っているかカウント
ii).任意に文字列を連結した際に "AB" が出来るケースをカウント

 カウント時の注意点
  例えば B※※A + B※※A + B※※A の場合、AB は 2 個になる。
  B※※※/※※※A と B※※A を混在させてカウントすると上記に辿り着けない

よって、以下のように B※※※, ※※※A, B※※A を分けて考えよう

 Case1 ※※※A + B※※※ = ※※※AB※※※
 Case2 B※※ A + B※※※ = B ※※AB※※※
 Case3 ※※※A + B※※A = ※※※AB※※A
 Case4 B※※A + B※※A = B※※AB※※A

Case1 ~ Case4 で、どれを優先すれば "AB" が最大になるのか。
B※※A,B※※A,B※※※,※※※A,※※※A を例に考える。

 B※※AB※※AB※※※※※※A※※※A　=> 2個
        or
 B※※AB※※A※※※AB※※※※※※A　=> 2個
        or
 ※※※AB※※AB※※A※※※AB※※※　=> 3個
        or
 ※※※AB※※AB※※AB※※※※※※A　=> 3個

よって、以下の式で対応できそうだ。
  B※※A の個数+ min(※※※Aの個数 , B※※※の個数)

しかし、冒頭に少しコメントした注意点を思い出す。
それは入力が B※※A only の場合だ。

 B※※AB※※A　=> 1個
 B※※AB※※AB※※A　=> 2個
 B※※AB※※AB※※AB※※A　=> 3個

よって、以下の式で対応できそうだ。
  B※※A の個数 - 1

実装

ABsubstrings.cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
	int N; cin >> N;
	vector<string>num(N, "");

	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}

	int cnt=0,ABcnt = 0, Acnt = 0, Bcnt = 0;
	for (auto S : num) {
		for (int i = 0; i < S.size() - 1; i++) {
			if (S.substr(i, 2) == "AB")
				cnt++;
		}
		if (S[0] == 'B' && S[S.size() - 1] == 'A')
			ABcnt++;
		else if (S[0] == 'B')
			Bcnt++;
		else if (S[S.size() - 1] == 'A')
			Acnt++;
	}

	if (Acnt == 0 && Bcnt == 0)
		cout << cnt + max(ABcnt - 1, 0);
	else
		cout << cnt + ABcnt + min(Acnt, Bcnt);

	//while (1) {}
	return 0;

}