AtCoder diverta 2019 Programming Contest C - AB Substrings(400点)

#問題概要
問題へのリンク

$N$個の文字列がある。$i$ 番目の文字列は $s_i$ 。
これらの文字列を任意の順に並べる。作った文字列に部分文字列 AB が最大いくつ含まれるか求めよ。

#制約条件

• $1≤N≤10^4$
• $2≤|s_i|≤10$
• $s_i$ は英大文字のみからなる

#考えたこと
求める値に影響を与える文字列は以下の4パターン

1. 末尾がA

• 最初がB
• 末尾がAで最初がB
• 部分文字列 AB が含まれている

基本的にパターン4にパターン1とパターン2の小さい方を足したものが答えとなる(小さい方以上に AB の文字列を作ることはできないので)が、コーナーケースとして1と2と3が重なる、あるいは存在しない場合がある。
1と2と3のパターンが重なる場合は「末尾がAで最初がB」となっている 該当ケース数-1 が答えとなる。例えば$BA, BAAA, BZOPDA$が該当するケースだとした時、左端にB、右端にAが配置されワンセット分余ることになる。1と2と3のパターンが存在しない場合は0である。

max(0, ba-1) で1と2と3のケースが重なっているか、存在しないかは判定すればよい。

#解答

c.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    int ab = 0;
    int a = 0;
    int b = 0;
    int ba = 0;
    for(int i = 0; i < n; i ++) {
        string s; cin >> s;
        int l = s.size();
        if(s[l-1]=='A') a++;
        if(s[0]=='B') b++;
        if(s[0]=='B' && s[l-1]=='A') ba ++;
        for(int j = 0; j < l-1; j ++) {
            if(s[j]=='A' && s[j+1]=='B') ab ++;
        }
    }
    if(a==ba && b==ba) cout << ab + max(0,ba-1) << endl;
    else cout << ab + min(a,b) << endl;
}