概要

\(N\) 人の生徒を赤チームと白チームに分ける際、一部の未回答（?）を「赤」か「白」のいずれかに決めることで、両チームの人数差の絶対値を最小化する問題です。

考察

まず、与えられた回答のうち、既に決まっている「赤」の人数を \(n_R\)、「白」の人数を \(n_W\)、判読不能な ? の人数を \(n_Q\) とします。

\(n_Q\) 人のうち、\(x\) 人を「赤」に、残りの \((n_Q - x)\) 人を「白」に割り振るとすると（\(0 \leq x \leq n_Q\)）、それぞれのチームの合計人数は以下のようになります。 - 赤チームの人数 \(R = n_R + x\) - 白チームの人数 \(W = n_W + (n_Q - x)\)

このとき、人数の差 \(D\) は以下の式で表せます。 \(D = R - W = (n_R + x) - (n_W + n_Q - x) = (n_R - n_W - n_Q) + 2x\)

ここで重要な点は、\(x\) が 1 増えるごとに差 \(D\) は 2 ずつ変化するということです。 \(x\) は \(0\) から \(n_Q\) までの値をとるため、\(D\) がとり得る値の範囲は、下限 \(L = n_R - n_W - n_Q\) から 上限 \(U = n_R - n_W + n_Q\) までとなります。

この範囲において、絶対値 \(|D|\) を最小にするには以下のように考えます。

1. 範囲が 0 をまたぐ場合 (\(L \leq 0 \leq U\)) \(D\) は 2 刻みで変化するため、0 に最も近い値は 0 または 1 になります。 合計人数 \(N\) と差 \(D\) の偶奇（パリティ）は常に一致するため（\(R+W=N\) より \(R-W = 2R-N\) となり、偶奇は \(N\) に依存する）、最小値は \(N\) が偶数なら \(0\)、奇数なら \(1\) となります。これは N % 2 で計算できます。

2. 範囲がすべて正、またはすべて負の場合 0 を含むことができないため、0 に最も近い端点の絶対値、つまり \(\min(|L|, |U|)\) が最小値となります。

アルゴリズム

1. 入力された \(N\) 個の回答から、R, W, ? の個数（\(n_R, n_W, n_Q\)）をそれぞれカウントします。
2. \(x=0\) のときの差 \(L = n_R - n_W - n_Q\) と、\(x=n_Q\) のときの差 \(U = n_R - n_W + n_Q\) を求めます。
3. \(L \leq 0 \leq U\) であれば、N % 2 を出力します。
4. そうでなければ、\(\min(|L|, |U|)\) を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 全ての回答を 1 回走査して各文字をカウントするため、生徒数 \(N\) に対して線形時間で処理可能です。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の回答をリスト等に保持する場合に必要となります。

実装のポイント

• Python では sys.stdin.read().split() を使うことで、大量の入力（\(N=10^5\)）を高速に読み込むことができます。

• リストの count() メソッドは内部的に C 言語で実装されており高速なため、文字のカウントに利用するのが効率的です。

• 差 \(D\) の最小値を考える際、偶奇の性質を利用することで、ループを回すことなく \(O(1)\) で判定を行うことができます。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込み、空白（改行を含む）で分割してトークンのリストを作成します。
    # Nが10^5程度であれば、この方法が効率的です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 最初のトークンは生徒の人数 N です。
    n = int(input_data[0])
    
    # 次の N 個のトークンは各生徒の回答 S_i です。
    # スライスを使用して回答のリストを取得します。
    s_list = input_data[1:n+1]
    
    # 各回答（'R', 'W', '?'）の個数を効率的にカウントします。
    # Pythonの list.count() はC言語で実装されており高速です。
    nr = s_list.count('R')
    nw = s_list.count('W')
    nq = s_list.count('?')
    
    # 赤チーム希望者数を R、白チーム希望者数を W とします。
    # 判読不能な回答 '?' のうち、x 人を「赤」、(nq - x) 人を「白」と解釈するとします。
    # R = nr + x
    # W = nw + (nq - x)
    # 差の絶対値 |R - W| = |(nr + x) - (nw + nq - x)| = |nr - nw - nq + 2x|
    # ここで x は 0 から nq までの整数値をとります。
    
    # x = 0 のときの差を L、x = nq のときの差を U とします。
    # 差 D = nr - nw - nq + 2x は、L から U まで 2 刻みで変化します。
    l = nr - nw - nq
    u = nr - nw + nq
    
    if l <= 0 <= u:
        # 差 D の範囲が負から正にまたがる場合、最小の絶対値は 0 または 1 になります。
        # 差のパリティ（奇偶）は常に N と一致するため、
        # N が偶数なら 0、N が奇数なら 1 が最小値となります。
        print(n % 2)
    else:
        # 差 D の範囲がすべて正、またはすべて負の場合、
        # 境界値のうち絶対値が小さい方が最小値となります。
        print(min(abs(l), abs(u)))

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。