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; }