diverta 2019 C - AB Substrings(400)

Submission #5371956 - diverta 2019 Programming Contest

概要

N個の文字列sのすべてを好きな順番に連結し、連結した後の文字列から'AB'という部分文字列がいくつ含まれているかを数える。すべての連結方法を試したときに、各連結方法で含まれうる'AB'の個数の最大値を答えよ。

制約

1 ≦ N ≦ 10^4
2 ≦ |si| ≦ 10

方針

部分文字列ABができる場合としては、
①もともと文字列にABが含まれている
②*Aという文字列とB*という文字列を連結する
の2通りがある。これらは独立して数えることができる。

①はそのまま数えればよい。

②は場合分けが必要。
sbea:Bで始まりAで終わる文字列の個数(例:BA)
sb:Bで始まりA以外の文字で終わる文字列(例:BY)の個数
ea:B以外の文字で始まりAで終わる文字列(例:XA)の個数　とする。

1. sbea = 0の場合
XAとBYをペアにして連結してゆけばよい。

2. それ以外の場合
2-1. sb = 0, ea = 0 の場合、 BA, BA, ... と連結してゆく。
2-2. sb > 0, ea = 0 の場合, BA, BA, ..., BA, BYと連結する。1つ以外のBYは無駄になる。
2-3. sb = 0, ea > 0 の場合, XA, BA, BA, ..., BAと連結する。1つ以外のXAは無駄になる。
2-4. sb > 0, ea > 0 の場合, XA, BA, BA, ..., BA, BYと連結し、残りのXA, BYをペアにする。

2-2～2-4のケースの連結数はすべてsbea + min(sb, ea)と表現される。

解答

Submission #5371956 - diverta 2019 Programming Contest

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	vector<string> v(N);
	rep(i, N) cin >> v[i];
 
	ll ab = 0;
	ll sbea = 0;
	ll sb = 0;
	ll ea = 0;
	for(int i = 0; i < N; i++){
		string s = v[i];
 
		for(int j = 0; j < s.size()-1; j++){
			if(s[j] == 'A' && s[j+1] == 'B') ab++;
		}
 
		if(s[0] == 'B' && s[s.size()-1] == 'A') {
			sbea++;
		}else if(s[0] == 'B'){
			sb++;
		}else if(s[s.size()-1] == 'A'){
			ea++;
		}
	}
 
	ll ans = ab;
	if(sbea == 0){
		ans += min(sb, ea);
	}else{
		if(sb == 0 && ea == 0){
			ans += max(sbea - 1, 0LL);
		}else{
			ans += sbea + min(sb, ea);
		}
	}
	cout << ans << endl;
}