C - Train Rearrangement Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は列車の組み換え作業を行っています。

最初、列車は先頭から順に赤色（R）の車両が A 両、その後ろに青色（B）の車両が B 両連結された状態になっています。すなわち、初期状態を文字列で表すと R が A 個並んだ後に B が B 個並んだ長さ N = A + B の文字列です。

高橋君は次の操作を 0 回以上繰り返し行うことができます。

  • 整数 k（1 \leq k \leq N - 1）を選ぶ。現在の列車の後ろから k 両を切り離す。すなわち、列車を先頭側の N - k 両と末尾側の k 両に分割する。
  • 切り離した末尾側の k 両を、車両の並び順を保ったまま一つのブロックとして、先頭側の N - k 両の中の任意の位置に挿入して再連結する。挿入できる位置は、先頭の前、末尾の後ろ、または隣り合う 2 両の間の、合計 N - k + 1 箇所のうちいずれかである。

操作は毎回、その時点での列車の状態に対して行います。

目標となる車両の並びを表す長さ N の文字列 T が与えられます。初期状態から T の並びにするために必要な操作回数の最小値を求めてください。

ただし、T に含まれる R の個数が A でない場合（すなわち車両の構成が初期状態と異なる場合）、目標の並びにすることは不可能です。不可能な場合は -1 を出力してください。

制約

  • 1 \leq A
  • 1 \leq B
  • A + B \leq 10^7
  • T は R と B のみからなる長さ A + B の文字列である
  • T に含まれる R の個数が A 個であるとは限らない

入力

A B
T
  • 1 行目には、赤色の車両数を表す整数 A と青色の車両数を表す整数 B が、スペース区切りで与えられる。
  • 2 行目には、目標となる車両の並びを表す文字列 T が与えられる。

出力

初期状態から T にするために必要な操作回数の最小値を出力せよ。不可能な場合は -1 を出力せよ。

入力例 1

2 2
RBBR

出力例 1

1

入力例 2

3 2
RRBBB

出力例 2

-1

入力例 3

7 6
RBRBBRRBRRBBR

出力例 3

4

入力例 4

25 20
BBBBBBBBBBBBBBBBBBBBRRRRRRRRRRRRRRRRRRRRRRRRR

出力例 4

1

入力例 5

1 1
RB

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is performing train rearrangement work.

Initially, the train consists of A red (R) cars from the front, followed by B blue (B) cars connected behind them. In other words, representing the initial state as a string, it is a string of length N = A + B where A characters R are followed by B characters B.

Takahashi can perform the following operation zero or more times:

  • Choose an integer k (1 \leq k \leq N - 1). Detach the last k cars from the current train. That is, split the train into the front N - k cars and the rear k cars.
  • Insert the detached rear k cars as a single block, maintaining their order, into any position within the front N - k cars and reconnect them. The possible insertion positions are: before the front, after the end, or between any two adjacent cars, for a total of N - k + 1 possible positions.

Each operation is performed on the current state of the train at that point.

You are given a string T of length N representing the target arrangement of cars. Find the minimum number of operations needed to transform the initial state into the arrangement T.

However, if the number of R characters in T is not A (i.e., the composition of cars differs from the initial state), it is impossible to achieve the target arrangement. In that case, output -1.

Constraints

  • 1 \leq A
  • 1 \leq B
  • A + B \leq 10^7
  • T is a string of length A + B consisting only of R and B
  • The number of R characters in T is not necessarily A

Input

A B
T
  • The first line contains integers A and B representing the number of red cars and blue cars, separated by a space.
  • The second line contains the string T representing the target arrangement of cars.

Output

Output the minimum number of operations needed to transform the initial state into T. If it is impossible, output -1.

Sample Input 1

2 2
RBBR

Sample Output 1

1

Sample Input 2

3 2
RRBBB

Sample Output 2

-1

Sample Input 3

7 6
RBRBBRRBRRBBR

Sample Output 3

4

Sample Input 4

25 20
BBBBBBBBBBBBBBBBBBBBRRRRRRRRRRRRRRRRRRRRRRRRR

Sample Output 4

1

Sample Input 5

1 1
RB

Sample Output 5

0