概要

初期状態は RR...RBB...B です。
目標文字列 \(T\) にするための最小操作回数は、\(T\) の中にある隣接ペア BR の個数になります。

考察

まず、操作では車両の色の個数は変わりません。
そのため、\(T\) に含まれる R の個数が \(A\) 個でなければ、目標状態にすることは不可能です。

次に重要なのは、文字列中の BR という隣接ペアの個数に注目することです。

例えば、

• RRRBBB には BR は \(0\) 個
• RBBRBR には BR は \(2\) 個
• BRBR には BR は \(2\) 個

です。

初期状態 RR...RBB...B には BR は存在しません。

ここで、1 回の操作で BR の個数を増やせるのは高々 \(1\) 個です。

操作では末尾のブロックを切り離して、どこかに挿入します。
このとき変化する隣接関係は、切り離した場所と挿入した場所の周辺だけです。

挿入によって新しく BR ができる可能性はありますが、同時に元々あった隣接関係が消えるため、結果として BR の個数は 1 回の操作で高々 \(1\) しか増えません。

したがって、目標 \(T\) に BR が \(x\) 個あるなら、少なくとも \(x\) 回の操作が必要です。

一方で、BR の個数が \(x\) 個なら、実際に \(x\) 回の操作で作ることができます。

例えば \(T = \texttt{BRBR}\) の場合、BR は \(2\) 個です。

初期状態が RRBB なら、

1. 末尾の B を先頭へ移動
   RRBB → BRRB
2. 末尾の B を真ん中へ移動
   BRRB → BRBR

となり、\(2\) 回で作れます。

一般に、\(T\) を BR の位置で区切ると、それぞれの部分は R...RB...B の形になります。
つまり、BR の個数だけ操作すれば、それぞれの B のブロックを適切な位置に移動して \(T\) を作れます。

よって、答えは \(T\) 中の BR の個数です。

素朴にすべての操作を試したり、状態を探索したりすると、文字列長が最大 \(10^7\) と大きいため到底間に合いません。
必要なのは文字列を左から見て BR を数えるだけです。

アルゴリズム

1. \(T\) に含まれる R の個数を数える。
2. その個数が \(A\) でなければ -1 を出力する。
3. そうでなければ、\(T\) の隣り合う文字を順に見て、T[i] == 'B' かつ T[i+1] == 'R' となる箇所を数える。
4. その個数を答えとして出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

ただし、\(N = A + B\) です。
入力文字列 \(T\) を保持するために \(O(N)\) のメモリを使います。

実装のポイント

T の長さは最大 \(10^7\) なので、二重ループなどは使わず、単純な線形走査だけで処理します。

また、\(T\) の長さは \(A+B\) で固定なので、R の個数が \(A\) なら B の個数も自動的に \(B\) になります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int A, B;
    string T;
    cin >> A >> B >> T;

    int cntR = 0;
    for (char c : T) {
        if (c == 'R') cntR++;
    }

    if (cntR != A) {
        cout << -1 << '\n';
        return 0;
    }

    int ans = 0;
    for (int i = 0; i + 1 < (int)T.size(); i++) {
        if (T[i] == 'B' && T[i + 1] == 'R') ans++;
    }

    cout << ans << '\n';
    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。