Problem:


Score : 400 points

Problem Statement

Snuke has N strings. The i-th string is s_i.

Let us concatenate these strings into one string after arranging them in some order.
Find the maximum possible number of occurrences of AB in the resulting string.

Constraints

1 \leq N \leq 10^{4}

2 \leq |s_i| \leq 10

s_i consists of uppercase English letters.

Input

Input is given from Standard Input in the following format:

N
s_1
\vdots
s_N

Output

Print the answer.

Sample Input 1

3
ABCA
XBAZ
BAD

Sample Output 1

2

For example, if we concatenate ABCA, BAD and XBAZ in this order, the resulting string ABCABADXBAZ has two occurrences of AB.

Sample Input 2

9
BEWPVCRWH
ZZNQYIJX
BAVREA
PA
HJMYITEOX
BCJHMRMNK
BP
QVFABZ
PRGKSPUNA

Sample Output 2

4

Sample Input 3

7
RABYBBE
JOZ
BMHQUVA
BPA
ISU
MCMABAOBHZ
SZMEHMA

Sample Output 3

4



Sample input:
3
ABCA
XBAZ
BAD


Sample output:
2

Submission status: Accepted

Solution code:
n = int(input())
s = [input() for _ in range(n)]

ans, cnt = 0, [0, 0, 0]
for i in s:
    ans += i.count('AB')
    if i[0] == 'B' and i[-1] == 'A':
        cnt[0] += 1
    elif i[0] == 'B':
        cnt[1] += 1
    elif i[-1] == 'A':
        cnt[2] += 1

if cnt[1] + cnt[2] == 0:
    print(ans + max(cnt[0] - 1, 0))
else:
    print(ans + min(cnt[1], cnt[2]) + cnt[0])

Submission status: Accepted

Solution code:
N = int(input())
res = 0
b_, _a, b_a = 0, 0, 0

for i in range(N):
    s = input()
    res += s.count("AB")
    s = s.replace("AB", "*")
    if s[0] == "B":
        if s[-1] == "A":
            b_a += 1
        else:
            b_ += 1
    elif s[-1] == "A":
        _a += 1

if b_a > 0:
    res += b_a - 1
    if _a > 0:
        res += 1
        _a -= 1
    if b_ > 0:
        res += 1
        b_ -= 1

res += min(_a, b_)
print(res)

Submission status: Accepted

Solution code:
n = int(input())

cnt_a = 0   # Bで始まらないがAで終わる
cnt_b = 0   # Bで始まるがAで終わらない
cnt_ba = 0  # Bで始まりAで終わる

ans = 0
for _ in range(n):
    s = input()
    ans += s.count('AB')
    if s.endswith('A') and s.startswith('B'):
        cnt_ba += 1
    else:
        if s.endswith('A'):
            cnt_a += 1
        if s.startswith('B'):
            cnt_b += 1

if cnt_ba == 0:
    ans += min(cnt_a, cnt_b)
else:
    ans += cnt_ba-1
    if cnt_a > 0:
        cnt_a -= 1
        ans += 1
    if cnt_b > 0:
        cnt_b -= 1
        ans += 1
    # 残ったxxAとBxxを組み合わせてABを作る
    ans += min(cnt_a, cnt_b)

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()

    ans = 0
    ar, br, abr = 0, 0, 0
    for i in range(N):
        s = in_s()
        ans += s.count('AB')
        if s[0] == 'B' and s[-1] == 'A':
            abr += 1
        elif s[0] == 'B':
            br += 1
        elif s[-1] == 'A':
            ar += 1

    # print(ans)
    #print(ar, br, abr)

    t = abr
    if ar > 0:
        ar -= 1
        t += 1
    if br > 0:
        br -= 1
        t += 1
    if t > 1:
        ans += t - 1

    ans += min(ar, br)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = [input() for _ in range(N)]

AB_cnt = 0
c1 = 0
c2 = 0
c3 = 0


for s in S:
    AB_cnt += s.count('AB')
    if s[0] == 'B' and s[-1] == 'A':
        c1 += 1
    elif s[0] == 'B':
        c2 += 1
    elif s[-1] == 'A':
        c3 += 1
if c1 == 0:
    print(AB_cnt + min(c2,c3))
elif c2 + c3 > 0:
    print(AB_cnt + c1 + min(c2,c3))
else:
    print(AB_cnt + c1 - 1)

Submission status: Accepted

Solution code:
n = int(input())
s = [str(input()) for _ in range(n)]

ba = 0
bo = 0
oa = 0
ans = 0

for i in range(n):
    ans += s[i].count('AB')
    if s[i][0] == 'B' and s[i][-1] == 'A':
        ba += 1
    elif s[i][0] == 'B':
        bo += 1
    elif s[i][-1] == 'A':
        oa += 1
#print(ans, ba, min(bo, oa))

if ba > 0 and bo + oa > 0:
    ans += ba + min(bo, oa)
if ba > 0 and bo + oa == 0:
    ans += ba - 1
if ba == 0 and bo + oa > 0:
    ans += min(bo, oa)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
lb=0
ra=0
ba=0
ans=0

import re

for _ in range(n):
    s=input()

    ans+=s.count('AB')

    if s[0]=='B' and s[-1]=='A':
        ba+=1
    elif s[0]=='B':
        lb+=1
    elif s[-1]=='A':
        ra+=1

if ba>0:
    ans+=ba-1
    ba=1

tmp=min(lb,ra,ba)
ans += 2*tmp

lb-=tmp
ra-=tmp
ba-=tmp

if lb<0:
    lb=0
if ra<0:
    ra=0
if ba<0:
    ba=0

if lb!=0 or ra!=0:
    ans+=min(lb,ra)
    ans+=min(lb,ba)
    ans+=min(ra,ba)


print(ans)

Submission status: Accepted

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    cnt=0
    a=0
    b=0
    A="A"
    B="B"
    ab=0
                
    
    for i in range(N):
        s=input()
        cnt+=s.count("AB")
        if s[0]==B and s[-1]==A:
            ab+=1
        elif s[0]==B:
            b+=1
        elif s[-1]==A:
            a+=1
            
    if a==0 and b==0:
        cnt+=ab-1
        if ab==0:
            cnt+=1
    else:
        cnt+=ab
    ans=cnt+min(a,b)
    print(ans)

main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = [input() for _ in range(N)]
    ans = 0
    cnt = [0] * 3
    for i in range(N):
        ans += S[i].count('AB')
        if S[i][0] == 'B' and S[i][-1] == 'A':
            cnt[0] += 1
        elif S[i][0] == 'B':
            cnt[1] += 1
        elif S[i][-1] == 'A':
            cnt[2] += 1

    if cnt[0] > 0:
        ans += cnt[0] - 1
        if not(cnt[1] == 0 and cnt[2] == 0):
            ans += 1
            ans += min(cnt[1],cnt[2])
    else:
        ans += min(cnt[1],cnt[2])

    print(ans)

    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


N=int(input())
L=[] #(lastA, firstB, have AB)
ans=0
lastA=0
firB=0
AB=0
for i in range(N):
    s=input()
    c=s.count("AB")
    #print(c)
    a=s[-1]=="A"
    b=s[0]=="B"
    d=(a==b==1)
    if d:
        a=0
        b=0
    ans+=c
    lastA+=a
    firB+=b
    AB+=d

if lastA and firB:
    ans+=2+AB-1
    lastA-=1
    firB-=1
    ans+=min(lastA, firB)
elif lastA or firB:
    ans+=AB
else:
    ans+=max(AB-1,0)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    
    n = ii()
    b_a, b_start, a_end = 0, 0, 0
    ans = 0

    for _ in range(n):
        s = input()
        ans += s.count('AB')
        if s[0] == 'B' and s[-1] == 'A':
            b_a += 1
        elif s[0] == 'B':
            b_start += 1
        elif s[-1] == 'A':
            a_end += 1
    
    # print(b_a, b_start, a_end)
    
    # m = min(b_start, a_end)
    # ans += m
    # b_start -= m
    # a_end -= m
    # if max(b_start, a_end) > 0:
    #     ans += b_a
    # else:
    #     ans += max(b_a - 1, 0)
    # print(ans)

    if b_start and a_end:
        if b_a:
            ans += (b_a + 1)
            b_start -= 1
            a_end -= 1
        ans += min(b_start, a_end)
    elif b_start or a_end:
        ans += b_a
    else:
        ans += max(b_a - 1, 0)
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a,b,ba,ans=0,0,0,0
for _ in range(n):
    s=input()
    for i in range(len(s)-1):
        if s[i]=="A" and s[i+1]=="B": ans+=1
    if s[0]=="B": b+=1
    if s[-1]=="A": a+=1
    if s[0]=="B" and s[-1]=="A": ba+=1
if ba==b==a!=0: ans-=1 
print(ans+min(a,b))

Submission status: Accepted

Solution code:
n = int(input())
a_end_count = 0
b_start_count = 0
ab_count = 0
a_or_b_count = 0
for _ in range(n):
  s = input()
  if s[-1] == 'A':
    a_end_count += 1
  if s[0] == 'B':
    b_start_count += 1
  if s[-1] == 'A' or s[0] == 'B':
    a_or_b_count += 1
  ab_count += s.count('AB')
ab_count += max(0, min([a_or_b_count - 1, a_end_count, b_start_count]))
print(ab_count)

Submission status: Accepted

Solution code:
N = int(input())
ans = 0
Count_A = 0
Count_B = 0
Count_BA = 0
s = []
for _ in range(N):
    s.append(input())

for i in range(N):
    ans += s[i].count("AB")
    if s[i][0] == "B" and s[i][-1] == "A":
        Count_BA += 1
    elif s[i][0] == "B":
        Count_B += 1
    elif s[i][-1] == "A":
        Count_A += 1

if Count_BA == 0:
    ans += min(Count_A, Count_B)
elif Count_A + Count_B == 0:
    ans += Count_BA-1
else:
    ans += Count_BA + min(Count_A, Count_B)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = [input() for _ in range(n)]
a = 0
b = 0
ab = 0
for i in range(n):
    if s[i][0] == "B" and s[i][-1] == "A":
        ab += 1
    elif s[i][0] == "B":
        b += 1
    elif s[i][-1] == "A":
        a += 1
c = min(a, b)
ans = c
if ab > 0:
    ans += ab
if a== 0 and b==0 and not ab==0: #not abは盲点
    ans = ab - 1
for S in s:
    for i in range(len(S)-1):
        if S[i: i + 2] == "AB":
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()

ans = 0
a = 0
b = 0
ba = 0

for _ in range(N):
	s = input()
	ans += s.count("AB")
	if s[0] == "B" and s[-1] == "A":
		ba += 1
	elif s[0] == "B":
		b += 1
	elif s[-1] == "A":
		a += 1

if 1 < ba:
	ans += ba-1
	ba = 1

if a != 0 or b != 0:
	if ba == 1:
		ans += min(a, b) + 1
	else:
		ans += min(a, b)

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()

ans = 0
a = 0
b = 0
ba = 0

for _ in range(N):
	s = input()
	ans += s.count("AB")
	if s[0] == "B" and s[-1] == "A":
		ba += 1
	elif s[0] == "B":
		b += 1
	elif s[-1] == "A":
		a += 1
if 0 < ba:
	if 0 < a and 0 < b:
		ans += ba + 1 + min(a-1, b-1)
	elif 0 < a or 0 < b:
		ans += ba
	else:
		ans += ba-1

else:
	ans += min(a, b)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

S = []
D = {'ab': 0, 'a': 0, 'b': 0}

res = 0
for _ in range(N):
    s = input()
    res += s.count('AB')
    if s[0] == 'B' and s[-1] == 'A':
        D['ab'] += 1
    elif s[0] == 'B':
        D['b'] += 1
    elif s[-1] == 'A':
        D['a'] += 1

if D['ab'] > 0:
    res += D['ab'] - 1
    res += int(D['a'] > 0) + int(D['b'] > 0)
    res += max(0, min(D['a'] - 1, D['b'] - 1))
else:
    res += min(D['a'], D['b'])

print(res)

Submission status: Accepted

Solution code:
xa = 0
bx = 0
ba = 0
ans = 0
N = int(input())

for _ in range(N):
    s = input()
    ans += s.count("AB")
    if s[0] == "B" and s[-1] == "A":
        ba += 1
    elif s[0] == "B":
        bx += 1
    elif s[-1] == "A":
        xa += 1

if xa == 0 and bx == 0 and ba != 0:
    print(ans+ba-1)
else:
    print(ans+min(xa,bx)+ba)

Submission status: Accepted

Solution code:
n = int(input())
count = 0
l = [input() for i in range(n)]
a = 0
b = 0
ab = 0
for i in range(n):
    if "AB" in l[i]:
        count += l[i].count("AB")
    if l[i][0] == "B" and l[i][-1] == "A":
        ab += 1
    elif l[i][0] == "B":
        b += 1
    elif l[i][-1] == "A":
        a += 1
if ab >= 2:
    count += ab-1
    ab = 1
x= min(ab,b)
count += x
b -= x
x= min(ab,a)
count += x
a -= x
if a and b:
    count += min(a,b)
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N = int(input())
S = [input() for i in range(N)]

ret = 0

for s in S:
    ret += s.count('AB')

D = [0] * N
for i in range(N):
    r = [0, 0]
    if S[i][0] == 'B':
        r[0] = 1
    if S[i][-1] == 'A':
        r[1] = 1

    D[i] = r

b_c = D.count([1, 0])
a_c = D.count([0, 1])
ab_c = D.count([1, 1])

if ab_c == 0:
    ret += min(b_c, a_c)
else:
    if a_c + b_c > 0:
        ret += ab_c + min(a_c, b_c)
    else:
        ret += ab_c - 1


print(ret)

Submission status: Accepted

Solution code:

N = int(input())
AB = 0
A = 0
B = 0
BA = 0
for i in range(N):
    s = list(input())
    for i in range(len(s)-1):
        if s[i] == 'A' and s[i+1] == 'B':
            AB += 1
    if s[-1] == 'A' and s[0] == 'B':
        BA += 1
    elif s[-1] == 'A':
        A += 1
    elif s[0] == 'B':
        B += 1
if BA == 0:
    AB += min(A,B)
elif A+B > 0:
    AB += BA + min(A,B)
else:
    AB += BA-1
print(AB)

Submission status: Accepted

Solution code:
N=int(input())
S=[""]*N
for i in range(N):
    S[i]=input()

H=0
A,B,C=0,0,0
for s in S:
    for j in range(len(s)-1):
        if s[j:j+2]=="AB":
            H+=1

    if s[0]=="B" and s[-1]=="A":
        C+=1
    elif s[0]=="B":
        B+=1
    elif s[-1]=="A":
        A+=1

if C==0:
    D=min(A,B)
else:
    if A+B!=0:
        D=C+min(A,B)
    else:
        D=C-1
        
print(H+D)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
n = int(input())
s = [input() for i in range(n)]

cnt1 = 0
cnt2 = 0
cnt3 = 0
ans = 0
for i in s:
    ans += i.count("AB")
    if i[0] == "B" and i[-1] == "A":
        cnt1 += 1
    elif i[0] == "B":
        cnt2 += 1
    elif i[-1] == "A":
        cnt3 += 1

ans += max(0, cnt1 - 1)
if cnt1 == 0:
    ans += min(cnt2, cnt3)
else:
    if cnt2 > 0:
        ans += 1
        cnt2 -= 1
    if cnt3 > 0:
        ans += 1
        cnt3 -= 1
    ans += min(cnt2, cnt3)
print(ans)

# ans2 = ans
# ans += max(cnt1 - 1, 0) + min(cnt2, cnt3)
# if cnt2 != cnt3 and cnt1 > 0:
#     ans += 1
# print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jun 23 13:27:43 2020

@author: NEC-PCuser
"""

N = int(input())

ans = 0
a_count = 0
b_count = 0
ab_count = 0
for i in range(N):
    s = input()
    if (s[0] == "B" and s[len(s) - 1] == "A"):
        ab_count += 1
    else:
        if (s[0] == "B"):
            b_count += 1
        if (s[len(s) - 1] == "A"):
            a_count += 1
    
    ans += s.count("AB")
    
    
plus = min([a_count, b_count])
    
if (ab_count != 0 and a_count + b_count > 0):
    plus += ab_count
elif (ab_count != 0):
    plus += (ab_count - 1)

print(ans + plus)

Submission status: Accepted

Solution code:
n = int(input())

cnt = 0
BA = 0
B_ = 0
_A = 0
for _ in range(n):
    s = input()
    cnt += s.count('AB')
    if s[0] == 'B' and s[-1] == 'A':
        BA += 1
    elif s[0] == 'B':
        B_ += 1
    elif s[-1] == 'A':
        _A += 1

if BA:
    cnt += BA - 1
    if B_:
        cnt += 1
        B_ -= 1
    if _A:
        cnt += 1
        _A -= 1
cnt += min(max(0, B_), max(0, _A))

print(cnt)

Submission status: Accepted

Solution code:
N,*s = open(0).read().split()
ans = sum(x.count('AB') for x in s)
bxa, xa, bx = 0, 0, 0
for x in s:
    if x[0] == 'B':
        if x[-1] == 'A':
            bxa += 1
        else:
            bx += 1
    elif x[-1] == 'A':
        xa += 1
if bxa > 0:
    ans += bxa - 1
    if xa > 0:
        ans += 1
        xa -= 1
    if bx > 0:
        ans += 1
        bx -= 1
    ans += min(xa,bx)
else:
    ans += min(xa,bx)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s_array = [input() for x in range(n)]
a_count = 0
b_count = 0
ab_count = 0
flag = False
for s in s_array:
    if s[-1] == "A" and s[0] != "B":
        a_count += 1
    elif s[0] == "B" and s[-1] != "A":
        b_count += 1
    elif s[0] == "B" and s[-1] == "A":
        ab_count += 1
    else:
        flag = True

res = sum([x.count("AB") for x in s_array])

if n == 1:
    print(res)
elif ab_count == 0:
    print(res + min(a_count, b_count))
elif a_count == 0 and b_count == 0:
    print(res - 1 + ab_count)
else:
    print(res + min(a_count, b_count) + ab_count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  divisors.sort()
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
data = SLs(N)

data = [d.replace("AB","#") for d in data]
ans = sum(Counter(d)["#"] if "#" in d else 0 for d in data)
ab = [(int(d[0]=="B"),int(d[-1]=="A")) for d in data]

dic = DD(int)
for x in ab:
  dic[x] += 1
if dic[(1,1)]==0:
  print(ans+min(dic[(1,0)],dic[(0,1)]))
else:
  if dic[(1,0)] or dic[(0,1,)]: 
    print(ans+dic[(1,1)]-1+min(dic[(1,0)],dic[(0,1)])+1)
  else:
    print(ans+dic[(1,1)]-1)

Submission status: Accepted

Solution code:
n = int(input())

ans = 0
A = 0
B = 0
BA = 0
for _ in range(n):
    s = input()
    ans += s.count('AB')
    if (s[0], s[-1]) == ('B', 'A'):
        BA += 1
        continue
    if s[-1] == 'A':
        A += 1
    if s[0] == 'B':
        B += 1
else:
    if BA:
        ans += BA-1
        if A:
            A -= 1
            ans += 1
        if B:
            B -= 1
            ans += 1
    ans += min(A, B)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ans = 0
dic = {'A':0, 'B':0, 'BA':0}
for i in range(N):
    tmp = input()
    if 'AB' in tmp:
        ans += tmp.count('AB')
    tmp = tmp.replace('AB','ZZ')
    if tmp[-1] == 'A' and tmp[0] == 'B':
        dic['BA'] += 1
    elif tmp[0] == 'B':
        dic['B'] += 1
    elif tmp[-1] == 'A':
        dic['A'] += 1

if dic['B'] >= 1 and dic['A'] >= 1 and dic['BA'] >= 1:
    ans += dic['BA'] + 1
    dic['BA'] = 0
    dic['B'] -= 1
    dic['A'] -= 1
if dic['BA'] >= 1:
    if dic['A'] == 0 and dic['B'] == 0:
        ans += dic['BA'] - 1
    elif dic['A'] == 0 or dic['B'] == 0:
        ans += dic['BA']
else:
    ans += min(dic['A'],dic['B'])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = 0
B = 0
AB = 0
ans = 0

for _ in range(N):
    S = list(input())

    for i in range(len(S)):
        try:
            if S[i] == 'A' and S[i+1] == 'B':
                ans += 1
        except:
            pass
    if S[0] == 'B':
        B += 1
        if S[-1] == 'A':
            A += 1
            AB += 1
    elif S[-1] == 'A':
        A += 1

if A == B and A == AB and AB != 0:
    print(A-1+ans)
else:
    print(min(A,B)+ans)

Submission status: Accepted

Solution code:
def m():
    N = int(input())
    S = [input() for _ in range(N)]
    A = B = C = 0
    ans = 0
    for s in S:
        ans += s.count('AB')
    for s in S:
        if s[0] == 'B' and s[-1] == 'A':
            C += 1
        elif s[0] == 'B':
            B += 1
        elif s[-1] == 'A':
            A += 1
        else:
            pass
    if C == 0:
        return ans + min(A, B)
    ans += C - 1

    if A > 0:
        A -= 1
        ans += 1
    if B > 0:
        B -= 1
        ans += 1
    ans += min(A,B)
    return ans


print(m())