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

hamayanhamayan's blog

AB Substrings [diverta 2019 Programming Contest C]

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_c

解法

https://atcoder.jp/contests/diverta2019/submissions/5348793

文字列中にABがあれば順番にかかわらず含まれるので、そこを最初に数えておこう。
そのついでに先頭がBの個数topB、末尾がAの個数backA、先頭B末尾Aの個数ABも数えておこう。
(ABにカウントされていれば、topB, backAでは数えないことに注意)
 
あとは、最適な順番を考える。
B????Aは使い勝手が良さそうなので、B???と???Aをうまく使いたい。
???AB???という風になるべくつなげよう。
あとは、B????Aをどこに置くかだが、???AB???になっている所に挟めば無駄がない。
???AB???が1つもない場合に注意して場合分けすれば、AC

int N;
string S[10101];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> S[i];
 
	int ans = 0;
	int backA = 0, topB = 0, AB = 0;
	rep(i, 0, N) {
		int n = S[i].length();
		rep(j, 0, n - 1) if (S[i][j] == 'A' && S[i][j + 1] == 'B') ans++;
 
		if (S[i][n - 1] == 'A') {
			if (S[i][0] == 'B') {
				AB++;
			}
			else {
				backA++;
			}
		}
		else {
			if (S[i][0] == 'B') {
				topB++;
			}
			else {
 
			}
		}
	}
 
	int pair = min(backA, topB);
 
	if (pair == 0) {
		if (backA + topB == 0) {
			if (0 < AB) ans += AB - 1;
		}
		else {
			ans += AB;
		}
	}
	else {
		ans += pair + AB;
	}
 
	cout << ans << endl;
}