問題
地面に $N$ 本の茎（辺が縦に一列につながったもの）が立っている。$i$ 本目の茎は文字列 $S_i$ で表され、$S_i$ の $1$ 文字目が地面に接する辺、$j$ 文字目が下から $j$ 番目の辺の色である（B は青、R は赤）。
Blue と Red が交互に手番を持つ。Blue は青い辺を 1 本、Red は赤い辺を 1 本選んで切る。切った辺より上にある辺は地面から離れるので、すべて取り除かれる（色は問わない）。手番で切れる辺が無いプレイヤーの負けである。
「Blue が先手のときの勝者」と「Red が先手のときの勝者」を空白区切りで出力せよ（勝者は Blue か Red）。
入力形式
N
S_1
S_2
...
S_N制約
| # | 条件 |
|---|---|
| 1 | $1\le N\le 2\times10^5$ |
| 2 | $1\le |S_i|$、$\sum|S_i|\le 2\times10^5$ |
| 3 | $S_i$ は B と R だけからなる |
入出力例
入力例1
2
BR
R出力例1
Red Red（BR の値は $1-\frac12=\frac12$、R は $-1$。和 $-\frac12<0$ なので、どちらが先手でも Red が勝つ）
入力例2
3
BR
BR
R出力例2
Red Blue（和 $\frac12+\frac12-1=0$。値 0 の局面は後手が勝つ。Blue 先手なら Red、Red 先手なら Blue が勝つ）
入力例3
3
BRRR
RBB
B出力例3
Blue Blue（$\frac18-\frac14+1=\frac78>0$。青い辺と赤い辺の本数はどちらも 4 本で、本数の差で決めると「後手勝ち」と誤る。3 例とも全状態探索で確認）
背景と出典
パルチザンゲームの和の理論（Conway の *On Numbers and Games*、Berlekamp・Conway・Guy の *Winning Ways*）では、赤青 Hackenbush の局面の値は数になる。茎（1 本の鎖）の値は次の規則で読める、と私は記憶している（本セッションでは原典を参照していない。以下の規則は全状態探索との一致で確かめた）。
- 地面から続く同じ色の辺 $k$ 本（最初の並び）は、色が青なら $+k$、赤なら $-k$
- その上の辺は、下から順に $\pm\frac12,\pm\frac14,\pm\frac18,\dots$（青なら $+$、赤なら $-$）
例: BBR $=2-\frac12=\frac32$、BRB $=1-\frac12+\frac14=\frac34$。
値の和 $G$ について、$G>0$ なら Blue が、$G<0$ なら Red が先手後手によらず勝ち、$G=0$ なら後手が勝つ。数の局面では「先手必勝（ファジー）」が起きない。
本問は自作。茎は数直線の 2 進展開そのものなので、和を正確に（浮動小数点を使わずに）求めることが本体になる。
概念図
ヒント（クリックで段階的に開示）
ヒント1（方向性）
不偏ゲームではないので Grundy 数の XOR は使えない。茎 1 本の小さい例（B、R、BR、BBR、BRR）で、Blue と Red が動いた先の値を並べ、「両者の間にある一番簡単な数」が何になるかを確かめる。
ヒント2（アプローチ）
茎の値は「最初の同色の並びの長さ」が整数部分、それより上の $i$ 本目の辺が $\pm2^{-i}$。$N$ 本の和の符号だけが分かればよいが、尾が $2\times10^5$ 本あると倍精度の 53 ビットでは足りない。
ヒント3（誘導）
尾の長さが $L$ の茎は、分母 $2^L$ の分子が「青を 1・赤を 0 にした 2 進数」から「赤を 1・青を 0 にした 2 進数」を引いたものになる。尾の長さごとに分子を足しておき、最後に分母を最大の長さ $D$ にそろえて（左シフト）合計する。長さの種類は $\sqrt{2\sum|S_i|}$ 程度しかない。
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
integer = 0 # 最初の同色の並びの和（整数部分）
tails = {} # 尾の長さ L → 分母 2^L での分子の和
for s in data[1:1 + n]:
c0 = s[0]
m = len(s)
k = 1
while k < m and s[k] == c0:
k += 1
integer += k if c0 == 66 else -k # 66 は b'B'
tail = s[k:]
L = m - k
if L:
# 尾の i 本目（1 始まり）は ±1/2^i。分母 2^L の分子では ±2^(L-i) = 2 進数の各桁
pos = int(tail.replace(b'B', b'1').replace(b'R', b'0'), 2)
neg = int(tail.replace(b'R', b'1').replace(b'B', b'0'), 2)
tails[L] = tails.get(L, 0) + pos - neg
D = max(tails, default=0)
num = integer << D
for L, v in tails.items(): # 長さの種類は sqrt(2*総辺数) 個以下なので、シフトの回数も少ない
num += v << (D - L)
if num > 0:
print("Blue Blue") # 値 > 0: どちらが先手でも Blue が勝つ
elif num < 0:
print("Red Red")
else:
print("Red Blue") # 値 = 0: 後手が勝つ
main()計算量: 文字列の置換と int(…, 2) が全体で $O(\sum|S_i|)$。和は尾の長さの種類 $d\le\sqrt{2\sum|S_i|}\approx632$ 回のシフト（各 $O(D/64)$ 語）で $O(d\cdot D/64)$。最大ケースで 0.04〜0.07 s（Python 3.14.7、M1 Mac、負荷平均 5〜6 のときの実測）。
Step-by-Step 解説
Blue（Left）が動いた先の値の集合を $G^L$、Red（Right）が動いた先を $G^R$ として $G=\{G^L\mid G^R\}$。すべての $G^L<$ すべての $G^R$ なら $G$ は数で、その値は「$\max G^L$ と $\min G^R$ の間で一番簡単な数」（整数なら絶対値が小さいもの、そうでなければ分母の 2 冪が小さいもの）。
例: BBR は Blue が上の B を切ると B$=1$、下の B を切ると $0$。Red が R を切ると BB$=2$。$\{0,1\mid2\}=\frac32$。
最初の同色の並び $k$ 本は、相手が手を持たないので $\pm k$。そこに反対色の辺を足すと、値は「$k$ と $k-1$ の間で一番簡単な数」$=k-\frac12$。さらに上に足すたびに区間が半分になり、$\pm\frac14,\pm\frac18,\dots$ と続く。この規則を、茎 1〜4 本・各長さ 1〜5 のランダム 500 局面で全状態探索と照合し、不一致 0（実測）。
和 $G=\sum$（茎の値）の符号で勝者が決まる。分母はすべて 2 冪なので、最大の尾の長さ $D$ を共通の分母にすれば整数だけで計算できる。Python の整数は任意精度なので、$2\times10^5$ ビットの数もそのまま扱える。
茎ごとに $2^{D-L}$ 倍して足すと、$N$ 回 $D$ ビットの数を作ることになり、長い茎 1 本（$10^5$ 本の辺）＋短い茎 $10^5$ 本で 0.81 s かかった（実測。本解は 0.07 s）。尾の長さごとにまとめれば、シフトは長さの種類の数（最大で約 632）だけで済む。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| 局面の全状態探索（メモ化） | 状態数が辺数の積 | 検算用のみ | 規則の確認に使用（500＋200 局面） |
fractions.Fraction で茎ごとに足す | 足すたびに約分（gcd） | 不採用 | 長い茎 1 本＋短い茎 $10^5$ 本で 6.16 s（実測） |
| 茎ごとに $2^{D-L}$ 倍して足す | $O(N\cdot D/64)$ | 不採用 | 同じ入力で 0.81 s（実測） |
| 尾の長さごとにまとめてからシフト（本解） | $O(\sum|S_i|+d\cdot D/64)$ | 採用 | 同じ入力で 0.07 s |
倍精度 float で足す | $O(\sum|S_i|)$ | 不採用 | 53 ビットを超える尾で符号を誤る（下の「よくあるミス」） |
前提が変わったら:
- 茎ではなく木（枝分かれあり）なら、茎の規則は使えない。子の部分木の値から $\{G^L\mid G^R\}$ を作り「一番簡単な数」を求める再帰が要る（木の Blue-Red Hackenbush は数になるが、計算は茎よりずっと重い）
- 緑の辺（どちらも切れる）が混ざると値は数にならず（$*$ など）、先手必勝の局面が出てくる。符号だけの判定では足りない
- 値そのものを既約分数で出力させるなら、
intを 10 進文字列にする上限（Python 3.11 以降の既定 4300 桁）をsys.set_int_max_str_digitsで外す必要がある
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 青と赤の本数の差で判定する | 辺の重みがすべて同じだと思う | 尾は $\pm2^{-i}$。700 局面中 109 局面で誤答（実測） |
| 最初の同色の並びだけ見る | 尾を無視する | 整数部分が同じとき尾で決まる。700 局面中 26 局面で誤答（実測） |
float で和を取る | 53 ビットを超える尾が消える | BR…R（R が 60 本）・R・B の和は $2^{-60}>0$ だが、float では 0 になり「後手勝ち」と誤る（実測） |
| Grundy 数の XOR を使う | 不偏ゲームと取り違える | パルチザンゲームでは手の集合が手番で違うので Sprague–Grundy の定理が使えない |
| 値 0 を「先手勝ち」にする | Nim の「XOR が 0 なら後手勝ち」の言い換えを忘れる | 値 0 は後手勝ち（出力 Red Blue） |
次のステップ
- 発展1: 茎ではなく根付き木の Blue-Red Hackenbush。部分木の値を「一番簡単な数」の再帰で求め、全状態探索と照合する
- 発展2: 緑の辺を混ぜた Hackenbush（数＋ニンバー）。先手必勝の局面が現れることを全探索で確かめる
- 発展3: 原典（*Winning Ways* の Hackenbush の章）で茎の規則と証明を確かめる（本セッションでは未確認）
検証ログ（本セッションで実行した数値）
- 全状態探索との照合（実測）: 茎 1〜4 本・長さ 1〜5 のランダム 500 局面で模範解答の不一致 0（Blue 勝ち 264・Red 勝ち 227・後手勝ち 9）。値 0 を狙った局面（茎とその色反転を並べる等）を足した 500 局面で規則の不一致 0（後手勝ち 84）
- 誤った方法（実測）: 上の 500 局面（ランダム 300＋値 0 狙い 200）で、本数の差 109・最初の並びだけ 26 局面誤答。float は小さい局面では 0 だが、上記の 3 本の茎で符号を誤る
- 入力例（実測）: 例 1
Red Red、例 2Red Blue、例 3Blue Blue（3 例とも全探索と一致） - 実行時間（実測、負荷平均 5〜6）: 茎 1 本・長さ $2\times10^5$ 0.04 s、長さ 1 の茎 $2\times10^5$ 本 0.05 s、長さ 1〜632 の茎（長さの種類が最大）0.04 s、茎とその色反転（値 0）0.04 s、長い茎 1 本＋短い茎 $10^5$ 本 0.07 s（Fraction 6.16 s・茎ごとのシフト 0.81 s）。負荷平均 36 のときは同じ入力で 0.13〜0.25 s（Fraction 17.98 s・シフト 2.99 s）
- 扱っていない範囲: 木や一般グラフの Blue-Red Hackenbush、緑の辺、値の出力、原典の確認