Edited at

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

  2. 最初がB

  3. 末尾がAで最初がB

  4. 部分文字列 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;
}