C - 列車の組み換え / Train Rearrangement 解説
by 
MMNMM
\(T\) に含まれる R の個数が \(A\) でないことを判定するのは \(O(A+B)\) 時間で可能です。
以下では、\(T\) に含まれる R の個数は \(A\) 個であるとします。
\(T\) に連続する部分文字列として含まれる BR の個数を \(K\) とすると、答えが \(K\) となることを示します。
まず、答えが \(K\) 以上となることを示すために、操作を \(1\) 回行ったときに BR の個数がたかだか \(1\) しか増加しないことを示します。
証明
操作において、後ろから \(k\) 両を切り離し、\(i-1\) 両目と \(i\) 両目の間に挿入したとします（\(i-1,i\) が \(0\) 以下や \(N+1\) 以上になるときは、列の端に挿入しているものとします）。
\(i=N+1\) のとき、列は操作の前後で変化しません。
よって、BR の個数は増加しません。
\(i=1\) のとき、操作前の列の末尾の車両と先頭の車両がこの順に隣接するようになります。
それ以外の連続する \(2\) 車両はもともとあった組み合わせなので、BR の個数は新しくできた \(1\) 組ぶんより多く増えることはありません。
\(1\lt i\le N\) のとき、操作前の列の
- 末尾の車両と \(i+1\) 両目の車両
- \(i\) 両目の車両と \(N-k+1\) 両目の車両
の \(2\) 組がこの順に隣接するようになり、それ以外の連続する \(2\) 車両はもともとあった組み合わせです。
よって、操作によって BR の個数が \(2\) 以上増加するならこれらの両方が BR に対応する組である必要があります。
しかし、このとき操作前の列の \(i\) 両目と \(i+1\) 両目も BR であることがわかるので、BR の個数が \(2\) 以上増加することはないことが示されました。
逆に、\(T\) に含まれる連続する極大な BB...B それぞれについて、前から順に適切な長さの B を切り出して挿入することで、\(K\) 回で操作を行うことができます。
実装例は以下のようになります。
#include <iostream>
using namespace std;
int main() {
int A, B;
cin >> A >> B;
string T;
cin >> T;
int R_count = 0, BR_count = 0;
for (int i = 0; i < A + B; ++i) {
if (i + 1 < A + B && T[i] == 'B' && T[i + 1] == 'R') {
++BR_count;
}
if (T[i] == 'R') {
++R_count;
}
}
if (R_count != A) { // R の個数が一致しなければ
cout << -1 << endl; // -1
} else { // 一致すれば
cout << BR_count << endl; // BR の個数が答え
}
return 0;
}
A, B = map(int, input().split())
T = input()
if T.count('R') != A: # R の個数が一致しなければ
print(-1)
else: # 一致すれば
print(T.count('BR')) # BR の個数が答え