diverta 2019 Programming Contest C - AB Substrings

解法

まず、それぞれの文字列の中に含まれるABの個数を調べます。これは、文字列をどのように連結しても、個数が変化することはないので、そのまま答えに加算されます。
では、文字列の連結によってあらたに増えるABの個数を調べます。
文字列を連結したときに、新たにABを増やすには、
...Aという文字列と、B...という文字列を、この順に連結する必要があり、このときに1つだけ増えます。
ということで、3種類の文字列の個数をカウントします。それは、

B...Aのように、Bで始まりAで終わる文字列
X...Aのように、B以外の文字で始まりAで終わる文字列
B...Xのように、Bで始まりA以外の文字で終わる文字列

です。それぞれ、 $C_{1},C_{2},C_{3}$ とします。

さて、それぞれのパターンをどのように使えばいいか考えてみます。
B...の文字列と、...Aの文字列は、1対1で対応するので、パターン1の文字列たちは、1つの文字列にまとめてしまっても問題ありません(Aで終わる文字列と、Bで始まる文字列の、個数の差に影響はありません)。
ので、B...AB...AB...Aのような、おっきな文字列に置き換え、 $C_{1}-1$ を答えに追加します。もし $C_{1}=0$ ならこの操作はいりません。
次に、パターン1,2,3のうちどの文字列を優先して使用するべきか考えてみます。
すると、パターン2,3を先に利用してしまうと、パターン1の文字列1つではABを作成することができなくなってしまいますが、先にパターン1の文字列にパターン2,3の文字列を組み合わせてあげることで、パターン1の文字列を無駄なく使用することができます。その後に、残ったパターン2とパターン3の文字列を1つずつ使用して順番に組み合わせていけばよいです。 $min(C_{2},C_{3})$ です。
ということで、