\(S\) の連続部分文字列の中で、A…ARC…C という形をした極大なものをブロックと呼ぶことにします。また \(S\) のブロックを順にブロック \(1,2,\ldots,M\) と呼びます。

あるブロックにいずれの操作を行えなくなったとき、そのブロックはA…AC…C、R、A…AR、RC…C のいずれかの形をしています。このことから、複数のブロックが操作後に結合して一つのブロックになることがないことがわかります。

以上の観察から、ブロック \(i\) について \(\mathrm{min}\)(Aの個数、Cの個数) を \(X_i\) とするとこの問題は以下のように言い換えられます。

正数列 \(X=(X_1,X_2,\ldots,X_M)\) が与えられる。 以下の操作を最大で何回行えるか。

• 奇数回目の操作では、\(X\) から要素を一つ選び、選んだ要素を \(-1\) する。この操作で要素が \(0\) になった場合、その要素を削除する。
• 偶数回目の操作では、\(X\) から要素を一つ選び、選んだ要素を削除する。

この問題は線形時間で解けます。操作回数の上界を考えます。

偶数回目の操作では \(X\) から要素が一つ消えるので、明らかに操作回数は \(2M\) 回以下です。 また、 \(X\) の総和を考えると、各操作では \(X\) の総和が \(1\) 以上減少するので、操作回数は \(\sum_i X_i\) 以下です。

以上より操作回数の上界は \(\mathrm{min}(2M, \sum_i X_i)\) です。実はこの上界は常に達成可能です。

よってこの問題を \(\mathrm{Ο}(N)\) で解けました。

Python による実装例を以下で示します。

n = int(input())
s = input()
xsum, m = 0, 0

for i in range(1, n - 1):
    if s[i - 1:i + 2] == "ARC":
        l, r = i - 1, i + 1
        while l - 1 >= 0 and s[l - 1] == "A":
            l -= 1
        while r + 1 < n and s[r + 1] == "C":
            r += 1
        x = min(i - l, r - i)
        xsum += x
        m += 1

print(min(xsum, m * 2))

また、multiset などを用いた貪欲法による \(\mathrm{Ο}(N\log N)\) 解法もあります。