概要

R、W、? からなる \(N\) 人分のアンケート結果が与えられ、? を R か W に自由に置き換えて、赤チームと白チームの人数差の絶対値を最小化する問題です。

考察

重要な気づき

まず、確定している情報を整理しましょう。

• R の個数を \(r\)、W の個数を \(w\)、? の個数を \(q\) とします。
• ? の \(q\) 個それぞれを R か W に割り当てます。

? のうち \(x\) 個を R に、残り \(q - x\) 個を W に割り当てると、最終的な人数差は次のようになります：

\[\text{赤チーム} - \text{白チーム} = (r + x) - (w + q - x) = (r - w) + 2x - q\]

したがって、最小化したいのは \(|(r - w) - q + 2x|\) であり、\(x\) は \(0 \leq x \leq q\) の整数です。

素朴なアプローチとの比較

\(x\) を \(0\) から \(q\) まで全探索すると \(O(q)\) かかりますが、\(q\) は最大 \(10^5\) 程度なので十分間に合います。しかし、数学的に最適な \(x\) を直接計算すれば \(O(1)\) で求まります。

数学的な解法

\(f(x) = (r - w) - q + 2x\) とおくと、\(f(x) = 0\) となる \(x\) は：

\[x = \frac{q - (r - w)}{2}\]

この \(x\) が整数かつ \([0, q]\) の範囲内なら答えは \(0\) です。そうでなければ、\(x\) の理想値に最も近い整数（\([0, q]\) の範囲にクランプしたもの）で \(|f(x)|\) を計算します。

具体例

• \(r = 3, w = 1, q = 2\) の場合：\(f(x) = 3 - 1 - 2 + 2x = 2x\)。\(x = 0\) で最小値 \(0\)。
• \(r = 3, w = 1, q = 1\) の場合：\(f(x) = 3 - 1 - 1 + 2x = 1 + 2x\)。\(x = 0\) で最小値 \(1\)。

アルゴリズム

1. 入力を読み込み、\(r\)（R の個数）、\(w\)（W の個数）、\(q\)（? の個数）を数える。
2. \(\text{diff} = r - w\) とする。
3. \(|(r-w) - q + 2x|\) を最小化する \(x \in [0, q]\) を求める。
   • 理想値 \(x^* = \frac{q - \text{diff}}{2}\) を計算。
   • \(x^*\) が整数かつ \(0 \leq x^* \leq q\) なら答えは \(0\)。
   • そうでなければ、\(x^*\) の前後の整数（\(\lfloor x^* \rfloor\) と \(\lceil x^* \rceil\)）を \([0, q]\) にクランプして、それぞれの \(|f(x)|\) の小さい方を出力。

計算量

• 時間計算量: \(O(N)\)（入力の読み込みに \(O(N)\)、最適解の計算は \(O(1)\)）
• 空間計算量: \(O(1)\)（カウンタ変数のみ）

実装のポイント

• \(x^*\) が整数になるかどうかは、\((q - \text{diff})\) が偶数かどうかで判定できます。\((q - \text{diff})\) が奇数なら \(f(x)\) は常に奇数値を取るため、答えは \(0\) にはなりません。

• \(\lfloor x^* \rfloor\) を int() で計算する際、\(x^*\) が負の場合にも正しくクランプ（\(\max(0, \cdot)\) や \(\min(q, \cdot)\)）する必要があります。

• 入力の末尾に空白や改行が含まれる可能性があるため、strip() で前後の空白を除去しています。

  ソースコード

N = int(input())
r = 0
w = 0
q = 0
for _ in range(N):
    s = input().strip()
    if s == 'R':
        r += 1
    elif s == 'W':
        w += 1
    else:
        q += 1

diff = r - w
# We can assign each '?' to R (+1) or W (-1) to adjust diff
# We want to minimize |diff + (assigned_to_R - assigned_to_W)|
# Let x = number of '?' assigned to R, then assigned_to_W = q - x
# diff + x - (q - x) = diff + 2x - q
# Minimize |diff - q + 2x| for x in [0, q]
# Target: diff - q + 2x = 0 => x = (q - diff) / 2

target = q - diff
if target % 2 == 0 and 0 <= target // 2 <= q:
    print(0)
else:
    # Find closest x in [0, q] such that |diff - q + 2x| is minimized
    # diff - q + 2x = 0 => x = (q - diff) / 2
    x_ideal = (q - diff) / 2
    x_low = max(0, int(x_ideal))
    x_high = min(q, x_low + 1)
    x_low = max(0, min(q, x_low))
    best = min(abs(diff - q + 2 * x_low), abs(diff - q + 2 * x_high))
    print(best)

---

この解説は claude4.6opus-thinking によって生成されました。