/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 625 点
問題文
これから N 日間の天気が文字列 S として与えられます。
S の i 文字目が S であるとき i 日目の天気は晴れ、 R であるとき i 日目の天気は雨です。
あなたは、以下の操作を 0 回以上 k 回まで行うことができます。
- 1 以上 N 以下の整数 i を選択する。
- i 日目の天気が晴れであれば雨、雨であれば晴れに変更する。
操作を行った後の最終的な天気に対して、以下の条件で嬉しさを得ます。
- 1 \le i \le N-1 を満たす各整数 i について、変更後の i 日目の天気が雨、かつ i+1 日目の天気が晴れであるとき、嬉しさを 1 得る。
各 k=0,1,\dots,N について、操作を高々 k 回行った時に得る嬉しさの合計の最大値を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \le T \le 10^4
- N は 2 以上 10^6 以下の整数
- S は長さ N の
SとRからなる文字列 - ひとつの入力における N の総和は 10^6 以下
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 個目のテストケースを意味する。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N S
出力
T 行出力せよ。i 行目には i 個目のテストケースの答えを出力せよ。
各テストケースについて、 k=i とした場合の答えを A_i とする。このとき、以下の形式で答えを出力せよ。
A_0 A_1 \dots A_N
入力例 1
5 4 SSSR 2 SR 6 RSRSRS 10 RSRSRRRRRR 20 SSRRSSSSRRRSSRRSRSRS
出力例 1
0 1 1 2 2 0 0 1 3 3 3 3 3 3 3 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 8 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
この入力には 5 個のテストケースが含まれています。
1 個目のテストケースについて:
- 操作前の各日の天気は順に 晴れ、晴れ、晴れ、雨です。
- k=0 である場合、操作は行えません。
- 操作後の各日の天気は 晴れ、晴れ、晴れ、雨 となり、得る嬉しさの合計は 0 であり、これが達成可能な最大です。
- k=1 である場合、例えば 2 日目の天気を変更することが最適です。
- 操作後の各日の天気は 晴れ、雨、晴れ、雨 となり、得る嬉しさの合計は 1 であり、これが達成可能な最大です。
- k=2 である場合、例えば 1,2 日目の天気を変更することが最適です。
- 操作後の各日の天気は 雨、雨、晴れ、雨 となり、得る嬉しさの合計は 1 であり、これが達成可能な最大です。
- k=3 である場合、例えば 1,3,4 日目の天気を変更することが最適です。
- 操作後の各日の天気は 雨、晴れ、雨、晴れ となり、得る嬉しさの合計は 2 であり、これが達成可能な最大です。
- k=4 である場合、例えば 1,3,4 日目の天気を変更することが最適です。
- 操作後の各日の天気は 雨、晴れ、雨、晴れ となり、得る嬉しさの合計は 2 であり、これが達成可能な最大です。
Score : 625 points
Problem Statement
The weather for the upcoming N days is given as a string S.
If the i-th character of S is S, then the weather on day i is sunny; if it is R, then the weather on day i is rainy.
You can perform the following operation between 0 and k times, inclusive:
- Choose an integer i with 1 \le i \le N.
- If the weather on day i is sunny, change it to rainy; if it is rainy, change it to sunny.
After performing the operations, you gain happiness based on the final weather according to the following condition:
- For each integer i with 1 \le i \le N-1, if the weather on day i after modification is rainy and the weather on day i+1 is sunny, your happiness increases by 1.
For each k = 0, 1, \dots, N, find the maximum total happiness you can gain by performing the operation at most k times.
T test cases are given; solve each.
Constraints
- 1 \le T \le 10^4
- N is an integer between 2 and 10^6, inclusive.
- S is a string of length N consisting of
SandR. - The sum of N in a single input is at most 10^6.
Input
The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N S
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
For each test case, let A_i be the answer for k = i. Then, output the answer in the following format:
A_0 A_1 \dots A_N
Sample Input 1
5 4 SSSR 2 SR 6 RSRSRS 10 RSRSRRRRRR 20 SSRRSSSSRRRSSRRSRSRS
Sample Output 1
0 1 1 2 2 0 0 1 3 3 3 3 3 3 3 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 8 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10
This input contains five test cases.
For the 1st test case:
- The weather on each day before any operations is sunny, sunny, sunny, rainy in order.
- For k = 0, no operations can be performed.
- The weather on each day after operations is sunny, sunny, sunny, rainy, and the total happiness is 0, which is the achievable maximum.
- For k = 1, for example, changing the weather on day 2 is optimal.
- The weather on each day after operations is sunny, rainy, sunny, rainy, and the total happiness is 1, which is the achievable maximum.
- For k = 2, for example, changing the weather on days 1 and 2 is optimal.
- The weather on each day after operations is rainy, rainy, sunny, rainy, and the total happiness is 1, which is the achievable maximum.
- For k = 3, for example, changing the weather on days 1, 3, and 4 is optimal.
- The weather on each day after operations is rainy, sunny, rainy, sunny, and the total happiness is 2, which is the achievable maximum.
- For k = 4, for example, changing the weather on days 1, 3, and 4 is optimal.
- The weather on each day after operations is rainy, sunny, rainy, sunny, and the total happiness is 2, which is the achievable maximum.