概要

? をすべて R または W に置き換えて、赤希望人数と白希望人数の差の絶対値 \(|R-W|\) を最小にする問題です。
? を何人 R にするか（残りは W）だけを決めればよい、という形に落とし込みます。

考察

まず、確定している票数を数えます：

• R の人数を \(r\)
• W の人数を \(w\)
• ? の人数を \(q\)

ここで、? のうち \(x\) 人を R と解釈し、残り \(q-x\) 人を W と解釈するとします。
すると最終的な差は

• 赤希望人数：\(r + x\)
• 白希望人数：\(w + (q-x)\)

なので、その差は [ (r+x) - (w+q-x) = (r-w) + 2x - q ] よって最小化したい値は [ \left| (r-w) + 2x - q \right| ] です。

重要な気づき

上式は \(x\) に関して一次式の絶対値なので、グラフにすると V字型になり、最小は「中身が 0 に最も近いところ」で達成されます。
つまり [ (r-w) + 2x - q = 0 ] を満たす \(x\) に近い整数を選べばよいです。解くと [ x = \frac{q - (r-w)}{2} ] となります。

ただし \(x\) は整数かつ \(0 \le x \le q\) の範囲なので、

• 目標値 \(x^\* = \dfrac{q-(r-w)}{2}\) の 床と天井（実装では \(x1, x1+1\)）
• 範囲外に出たときのために 端（\(0\) と \(q\)）

だけ調べれば十分です。

（素朴に \(x=0..q\) を全探索してもよいですが、この方法なら「候補4つを確認するだけ」で確実に最小が求まります。）

アルゴリズム

1. 入力から R,W,? の個数 \(r,w,q\) を数える。
2. もし \(q=0\) なら答えはそのまま \(|r-w|\)。
3. そうでなければ、差の式 [ diff(x) = (r-w) + 2x - q ] を用意する。
4. 目標に近い [ x^* = \frac{q-(r-w)}{2} ] を考え、実装では
   • \(x1 = \left\lfloor x^\* \right\rfloor\)
   • \(x1+1\)
   • 端の \(0, q\) を候補として列挙する。
5. 各候補 \(x\) を \([0,q]\) に丸め（クランプし）、\(\min |diff(x)|\) を答える。

計算量

• 時間計算量: \(O(N)\)（カウントが \(N\) 回、候補チェックは定数回）
• 空間計算量: \(O(1)\)（カウンタのみ）

実装のポイント

• 差の式は必ず [ diff(x) = (r-w) + 2x - q ] になることを確認すると、実装ミスが減ります。

• 最適な \(x\) は \(\dfrac{q-(r-w)}{2}\) 付近なので、整数誤差に備えて 床と床+1の両方を調べます。

• \(x\) が \(0..q\) の範囲外になる場合があるため、候補は 必ず \([0,q]\) に丸める必要があります。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    r = w = q = 0
    for i in range(1, n + 1):
        s = data[i]
        c = s[:1]
        if c == b'R':
            r += 1
        elif c == b'W':
            w += 1
        else:
            q += 1

    if q == 0:
        print(abs(r - w))
        return

    num = q - (r - w)  # want x close to num/2
    x1 = num // 2
    candidates = {0, q, x1, x1 + 1}
    ans = 10**18
    for x in candidates:
        if x < 0:
            x = 0
        elif x > q:
            x = q
        diff = (r - w) + 2 * x - q
        ans = min(ans, abs(diff))
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。