/
Time Limit: 6 sec / Memory Limit: 1024 MiB
Score: 100 points
Problem Statement
On the stage, 2N beavers are standing in a row. They are members of the chorus. Each beaver sings either the alto part or the bass part of the chorus. This information is given by a string S. Precisely, the i-th beaver (1 \le i \le 2N) from the stage right (i.e., from left when seen from the audience seats) sings the alto part if the i-th character of S is A. The i-th beaver sings the bass part if the i-th character of S is B. There are N beavers singing the alto part, and N beavers singing the bass part.
From now, the beavers will sing K songs. However, since all the songs are very difficult, each beaver sings exactly one song only, and does not sing other songs. Moreover, in order to make singing voice more beautiful, for every song, the following conditions should be satisfied.
- At least one beaver sings the song.
- The number of beavers singing the alto part of the song is equal to the number of beavers singing the bass part of the song.
- If we consider the beavers singing the song only, every alto beaver stands the stage right of every bass beaver.
Bitaro, the conductor, tried to find a way to allot songs to beavers which satisfies the conditions. Since Bitaro is bright, he notices that it might be impossible to allot songs to beavers.
In order to cope with this issue, Bitaro will perform the following operation several times so that there is a way to allot songs to beavers which satisfies the conditions.
- Swap the position of two adjacent beavers.
Since Bitaro thinks efficiency is important, he wants to minimize the number of operations. However, it turns out to be a surprisingly difficult problem. Since you are a brilliant programmer, Bitaro asks you to solve this problem.
Write a program which, given information of the chorus and the number of songs K, calculates the minimum number of operations Bitaro needs to perform. Note that, under the constraints of this task, it is possible to perform the operations several times so that there is a way to allot songs to beavers which satisfies the conditions.
Input
Read the following data from the standard input.
N K S
Output
Write one line to the standard output. The output should contain the minimum number of operations Bitaro needs to perform.
Constraints
- 1 \le N \le 1\,000\,000.
- 1 \le K \le N.
- S is a string of length 2N. In the string S, the character
Aappears N times, and the characterBappears N times. - N, K are integers.
Subtasks
- (16 points) N \le 10.
- (24 points) N \le 500.
- (21 points) N \le 5\,000.
- (26 points) N \le 100\,000.
- (13 points) No additional constraints.
Sample Input 1
5 2 AABABABBAB
Sample Output 1
2
In this sample input, for example, Bitaro can perform the following operations. Here, the underline denotes the positions of the two beavers swapped by Bitaro.
-
Swap the third beaver and the fourth beaver from the stage right.
After this operation, the string which denotes the parts of the beavers from the stage right becomes “AAABBABBAB”.
-
Swap the eighth beaver and the ninth beaver from the stage right.
After this operation, the string which denotes the parts of the beavers from the stage right becomes “AAABBABABB”.
After these operations, Bitaro can allot songs to beavers as follows.
- From the stage right, the 1, 2, 3, 4, 5, 7-th beavers sing the first song.
- From the stage right, the 6, 8, 9, 10-th beavers sing the second song.
This way to allot songs to beavers satisfies the conditions.
If the number of operations is less than 2, there does not exist a way to allot songs to beavers which satisfies the conditions. Therefore, output 2.
This sample input satisfies the constraints of all the subtasks.
Sample Input 2
5 3 AABABABBAB
Sample Output 2
0
Without performing operations, Bitaro can allot songs to beavers as follows.
- From the stage right, the 1, 2, 3, 5-th beavers sing the first song.
- From the stage right, the 4, 6, 7, 8-th beavers sing the second song.
- From the stage right, the 9, 10-th beavers sing the third song.
This way to allot songs to beavers satisfies the conditions. Therefore, output 0.
This sample input satisfies the constraints of all the subtasks.
Sample Input 3
3 1 BBBAAA
Sample Output 3
9
This sample input satisfies the constraints of all the subtasks.
Sample Input 4
10 3 ABABBBBABBABABABAAAA
Sample Output 4
37
This sample input satisfies the constraints of all the subtasks.
配点 : 100 点
問題文
2N 匹のビーバーが舞台上に横一列に並んでいる.ビーバーたちは合唱隊であり,それぞれのビーバーはアルトまたはバスのいずれかのパートを担当している.この情報は文字列 S によって与えられる.具体的には,下手側(客席から見て左側)から i 番目 (1 \leqq i \leqq 2N) の位置にいるビーバーは,S の i 文字目が A ならばアルトを,B ならばバスを担当している.ここで,アルトとバスはそれぞれ N 匹ずついる.
ビーバーたちはこれから K 個の曲を歌う.ただし,どの曲もとても難しいため,それぞれのビーバーはちょうど 1 曲だけを歌い,それ以外の曲は歌わない.さらに,声が美しく響くためには,それぞれの曲について次の条件をすべて満たす必要がある.
- その曲を歌うビーバーが 1 匹以上いる.
- その曲を歌うアルトとバスの数が等しい.
- その曲を歌うビーバーだけに注目したとき,すべてのアルトはすべてのバスより下手側に立っている.
指揮者のビ太郎は,上記の条件を満たすようそれぞれのビーバーに歌う曲を割り振ろうとした.しかし,聡明なビ太郎はこれがそもそも不可能かもしれないことに気がついた.
そこでまずビ太郎は,以下の操作を繰り返すことで,条件を満たす曲の割り振りが存在するようにしたいと考えた.
- 隣接している 2 匹のビーバーの位置を入れ替える.
何事も効率を重視するビ太郎は操作の回数を最小化したかったが,これが思いの外難しかったため,優秀なプログラマーであるあなたに代わりに問題を解いてほしいと頼んできた.
合唱隊の情報と歌う曲の数 K が与えられたとき,ビ太郎が行う必要のある最小の操作回数を求めるプログラムを作成せよ.なお,この問題の制約下では,条件を満たす曲の割り振りが存在するように操作を行うことが可能である.
入力
入力は以下の形式で標準入力から与えられる.
N K S
出力
標準出力に,ビ太郎が行う必要のある最小の操作回数を 1 行で出力せよ.
制約
- 1 \leqq N \leqq 1\,000\,000.
- 1 \leqq K \leqq N.
- S は N 個の
Aと N 個のBからなる長さ 2N の文字列である. - N, K は整数である.
小課題
- (16 点) N \leqq 10.
- (24 点) N \leqq 500.
- (21 点) N \leqq 5\,000.
- (26 点) N \leqq 100\,000.
- (13 点) 追加の制約はない.
入力例 1
5 2 AABABABBAB
出力例 1
2
この入力例では,ビ太郎は例えば以下のように操作を行えばよい.ただし,下線はビ太郎が入れ替えた 2 匹のビーバーの位置を表す.
-
下手側から 3 番目と 4 番目のビーバーの位置を入れ替える.
この操作の後,各ビーバーの担当するパートを表す文字列は下手側から “AAABBABBAB” となる.
-
下手側から 8 番目と 9 番目のビーバーの位置を入れ替える.
この操作の後,各ビーバーの担当するパートを表す文字列は下手側から “AAABBABABB” となる.
これらの操作の後,ビ太郎は次のように曲を割り振ることができる.
- 下手側から 1, 2, 3, 4, 5, 7 番目のビーバーに 1 曲目を歌わせる.
- 下手側から 6, 8, 9, 10 番目のビーバーに 2 曲目を歌わせる.
この割り振りは条件をすべて満たしている.
2 回より少ない操作で,条件を満たすような曲の割り振りを行うことはできない.よって 2 を出力する.
この入力例はすべての小課題の制約を満たす.
入力例 2
5 3 AABABABBAB
出力例 2
0
一度も操作を行わずとも,ビ太郎は次のように曲を割り振ることができる.
- 下手側から 1, 2, 3, 5 番目のビーバーに 1 曲目を歌わせる.
- 下手側から 4, 6, 7, 8 番目のビーバーに 2 曲目を歌わせる.
- 下手側から 9, 10 番目のビーバーに 3 曲目を歌わせる.
この割り振りは条件をすべて満たしている.よって 0 を出力する.
この入力例はすべての小課題の制約を満たす.
入力例 3
3 1 BBBAAA
出力例 3
9
この入力例はすべての小課題の制約を満たす.
入力例 4
10 3 ABABBBBABBABABABAAAA
出力例 4
37
この入力例はすべての小課題の制約を満たす.