概要

初期状態は RR...RBB...B です。目標文字列 \(T\) に含まれる R の個数が \(A\) 個でなければ不可能で、そうでなければ答えは \(T\) 中の BR の出現回数になります。

考察

まず、\(T\) に含まれる R の個数が \(A\) 個でなければ、初期状態と車両の構成が異なるため、どのように並べ替えても \(T\) にはできません。
この場合は -1 です。

以降、R の個数が \(A\) 個であるとします。

重要な観察は、文字列中の BR の個数です。

例えば、

RRBB      -> BR の個数は 0
RBBR      -> BR の個数は 1
BRBR      -> BR の個数は 2
BBRRBB    -> BR の個数は 1

初期状態 RR...RBB...B には BR は存在しません。
なぜなら、R の後に B が続く境目 RB はありますが、B の後に R が続く境目 BR はないからです。

ここで、1 回の操作で BR の個数は高々 \(1\) 個しか増えません。

操作を文字列のブロックで見ると、ある状態を

U V W

と表したとき、末尾ブロック \(W\) を切り離して、\(V\) の前に挿入する操作は

U V W -> U W V

と見なせます。

このとき変化する可能性がある隣接関係は、ブロックの境目だけです。
内部の並びは変わらないため、BR の個数は一度の操作で高々 \(1\) しか増えません。

したがって、初期状態の BR の個数は \(0\) なので、目標 \(T\) に BR が \(c\) 個あるなら、少なくとも \(c\) 回の操作が必要です。

次に、実際に \(c\) 回で必ず達成できることを考えます。

操作は逆向きにも同じ形式で実行できます。
つまり、

U V W -> U W V

という操作の逆は、

U W V -> U V W

であり、これも末尾ブロック \(V\) を切り離して途中に挿入する操作として実現できます。

そこで、目標文字列 \(T\) から初期状態 RR...RBB...B に戻すことを考えます。

\(T\) に BR があるなら、一番右の BR に注目します。
その部分は、ある \(B\) の連続ブロックの後ろに、\(R\) の連続ブロックが続いている形です。

例えば、

U B...B R...R B...B

のように表せます。

ここで、末尾側の

R...R B...B

を切り離して、直前の B...B の前に移動すると、

U R...R B...B B...B

となり、注目していた BR を 1 個消せます。

これを繰り返すと、BR の個数を 1 回の操作で 1 個ずつ減らせます。
最終的に BR が \(0\) 個になると、文字列は必ず

RR...RBB...B

という形になります。

よって、\(T\) から初期状態へ BR の個数と同じ回数で戻せます。
操作は逆向きにも可能なので、初期状態から \(T\) へも同じ回数で到達できます。

したがって、答えは

\(T\) 中の BR の個数

です。

アルゴリズム

1. 入力として \(A, B, T\) を受け取る。
2. \(T\) に含まれる R の個数を数える。
3. その個数が \(A\) と異なるなら -1 を出力する。
4. そうでなければ、\(T\) 中の部分文字列 BR の出現回数を数えて出力する。

例えば、

A = 2, B = 2
T = BRBR

の場合、BR は 2 回出現するので答えは \(2\) です。

計算量

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

実装のポイント

\(N\) は最大で \(10^7\) と大きいため、文字列全体を何度も加工したり、操作をシミュレーションしたりすると間に合いません。

Python では、入力を bytes として扱うと高速です。

T.count(b'R')
T.count(b'BR')

を使えば、それぞれ R の個数と BR の個数を効率よく数えられます。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    A, B = map(int, input().split())
    T = input().strip()

    if T.count(b'R') != A:
        print(-1)
    else:
        print(T.count(b'BR'))

if __name__ == "__main__":
    main()

---

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