C - AB Substrings

Contest Duration: 2019-05-11(Sat) 12:15 - 2019-05-11(Sat) 14:15 (local time) (120 minutes)

C - AB Substrings Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $400$ 点

問題文

すぬけ君は $N$ 個の文字列を持っています。 $i$ 番目の文字列は $s_i$ です。

これらの文字列を好きな順序で並べたあと、連結して $1$ つの文字列を作ることを考えます。作った文字列に AB という部分文字列が含まれる個数としてありうる値のうち、最大値を求めてください。

制約

$1 \leq N \leq 10^{4}$
$2 \leq |s_i| \leq 10$
$s_i$ は英大文字のみからなる

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $s_1$ 
 $\vdots$ 
 $s_N$

出力

答えを出力せよ。

入力例 1Copy

Copy

3
ABCA
XBAZ
BAD

出力例 1Copy

Copy

例えば、ABCA, BAD, XBAZ の順で連結して ABCABADXBAZ を作ったとき、AB という部分文字列は $2$ つ含まれます。

入力例 2Copy

Copy

9
BEWPVCRWH
ZZNQYIJX
BAVREA
PA
HJMYITEOX
BCJHMRMNK
BP
QVFABZ
PRGKSPUNA

出力例 2Copy

Copy

入力例 3Copy

Copy

7
RABYBBE
JOZ
BMHQUVA
BPA
ISU
MCMABAOBHZ
SZMEHMA

出力例 3Copy

Copy

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 1Copy

Copy

3
ABCA
XBAZ
BAD

Sample Output 1Copy

Copy

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

Sample Input 2Copy

Copy

9
BEWPVCRWH
ZZNQYIJX
BAVREA
PA
HJMYITEOX
BCJHMRMNK
BP
QVFABZ
PRGKSPUNA

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

7
RABYBBE
JOZ
BMHQUVA
BPA
ISU
MCMABAOBHZ
SZMEHMA

Sample Output 3Copy

Copy