/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は N 人の生徒を赤チームと白チームの2つに分けようとしています。事前にアンケートを取り、各生徒に希望するチームを紙に書いてもらいました。
しかし、アンケート用紙の一部にコーヒーがこぼれてしまい、何人かの回答が読めなくなってしまいました。読めなくなった回答は ? として記録されており、元々「赤」だったか「白」だったかが判別できません。
各生徒の回答は、R（赤チーム希望）、W（白チーム希望）、?（判読不能）のいずれか1文字で表されます。
高橋君は、判読不能な回答（?）のそれぞれを R（赤チーム希望）または W（白チーム希望）に独立に置き換えることで、最終的な赤チーム希望者数と白チーム希望者数の差の絶対値を最小にしたいと考えています。
? を最適に置き換えたとき、赤チーム希望者数と白チーム希望者数の差の絶対値の最小値を求めてください。なお、? が1つも含まれない場合は、そのままの回答に基づいて差の絶対値を求めてください。
制約
- 1 \leq N \leq 10^5
- S_i は
R、W、?のいずれかである (1 \leq i \leq N)
入力
N S_1 S_2 \vdots S_N
- 1 行目には、生徒の人数を表す整数 N が与えられる。
- i = 1, 2, \dots, N について、1 + i 行目には i 番目の生徒の回答を表す1文字 S_i が与えられる。S_i は
R、W、?のいずれかである。
出力
赤チーム希望者数と白チーム希望者数の差の絶対値の最小値を1行で出力せよ。
入力例 1
5 R W ? R ?
出力例 1
1
入力例 2
8 R W ? R ? ? R ?
出力例 2
0
入力例 3
10 R R W ? R ? R R ? W
出力例 3
0
Score : 300 pts
Problem Statement
Takahashi is trying to divide N students into two teams: the Red team and the White team. He conducted a survey in advance, asking each student to write their preferred team on a piece of paper.
However, coffee was spilled on some of the survey papers, making several responses unreadable. The unreadable responses are recorded as ?, and it is impossible to determine whether they originally said "Red" or "White".
Each student's response is represented by a single character: R (prefers Red team), W (prefers White team), or ? (unreadable).
Takahashi wants to independently replace each unreadable response (?) with either R (prefers Red team) or W (prefers White team) so as to minimize the absolute difference between the final number of Red team supporters and White team supporters.
Find the minimum possible absolute difference between the number of Red team supporters and the number of White team supporters when the ?s are replaced optimally. If there are no ?s, simply compute the absolute difference based on the responses as they are.
Constraints
- 1 \leq N \leq 10^5
- S_i is one of
R,W, or?(1 \leq i \leq N)
Input
N S_1 S_2 \vdots S_N
- The first line contains an integer N representing the number of students.
- For i = 1, 2, \dots, N, the (1 + i)-th line contains a single character S_i representing the response of the i-th student. S_i is one of
R,W, or?.
Output
Print the minimum possible absolute difference between the number of Red team supporters and the number of White team supporters on a single line.
Sample Input 1
5 R W ? R ?
Sample Output 1
1
Sample Input 2
8 R W ? R ? ? R ?
Sample Output 2
0
Sample Input 3
10 R R W ? R ? R R ? W
Sample Output 3
0