Day 175-Q3 | スイッチの和

問題

$N$ 枚のカードがあり、$i$ 枚目には整数 $a_i\ge b_i$ が書かれている。Left と Right の 2 人が交互に手番を持ち、手番では次のどちらかをする。

まだ使っていないカードを 1 枚選んで使う。Left が使えば得点 $X$ に $a_i$ を足し、Right が使えば $b_i$ を足す（カードはなくなる）
「整数の山」で 1 手指す: $X>0$ なら Left だけが $X$ を 1 減らせる。$X<0$ なら Right だけが $X$ を 1 増やせる

最初は $X=0$。手番で何もできない人の負けである（カードが尽き、$X>0$ なのに Right の番、など）。

これは、スイッチ $\{a_i\mid b_i\}$ の和と整数の和をそのままゲームにしたものである。「Left が先手のとき」「Right が先手のとき」のそれぞれについて勝者を答え、先手が勝つときは最初に使うカードの番号を 1 つ答えよ。

入力形式

N
a_1 b_1
...
a_N b_N

出力形式

2 行。1 行目は Left が先手の場合、2 行目は Right が先手の場合。先手が勝つなら Left i（または Right i）、後手が勝つなら勝者の名前だけ。

制約

$1\le N\le2\times10^5$
$-10^{18}\le b_i\le a_i\le10^{18}$

入出力例

入力例1

1
3 -1

出力例1

Left 1
Right 1

（$\{3\mid-1\}$ は先に取った方が勝つ。値は数でない）

入力例2

出力例2

Left 1
Right 1

（$\pm1$ が 2 枚だけなら値 0 で後手勝ち。そこに $\{0\mid0\}=*$ を 1 枚足すと、カードの枚数が奇数になり先手勝ちに変わる）

入力例3

2
4 0
-1 -1

出力例3

Left 1
Right 1

（Right 先手で「自分の得点が一番小さいカード」$b=-1$ を取ると、Left に $4$ を取られて負ける。温度 2 のカード 1 で $0$ を取るのが正しい。3 例とも全状態探索と一致）

---

背景と出典

スイッチ: $\{a\mid b\}$（$a>b$）は、Left が動けば $a$、Right が動けば $b$ になるゲーム。平均 $\mu=\frac{a+b}2$ と温度 $t=\frac{a-b}2$ で $\mu\pm t$ と書く。$a=b$ なら $\{a\mid a\}=a+*$（温度 0、数にスターが付いたもの）
数の回避定理（number avoidance theorem）: 数でない成分があるうちは、数の成分で指す必要はない。本問の「整数の山」で指すのは、カードが尽きてからでよい
スイッチの和では、温度の高いものから取るのが最善だと私は記憶している（Berlekamp–Conway–Guy『Winning Ways』の熱いゲームの章、Berlekamp の "hotstrat" など。原典は本セッションで未確認）。本問ではこの主張を、整数の山の手も含めた全状態探索 600 局面で確かめた
本問は自作。Day174-Q3 の「発展2」（値が数にならないパルチザンゲーム）の最初の一歩として、熱図（thermograph）を描かずに済む「スイッチだけ」の場合を扱う

概念図

ヒント（クリックで段階的に開示）

ヒント1（方向性）

$\{3\mid-1\}$ 1 枚だけのゲームは、Left 先手でも Right 先手でも先手が勝つ。値の符号で勝者が決まる「数」とは違う。このカードは「取った人が得をする」ので、早く取りたい。

ヒント2（アプローチ）

カードを取るときの「得の大きさ」は、Left が取った場合と Right が取った場合の差 $a-b$ の半分（温度）。両者とも温度の高いカードから取るのが最善になる。カードが尽きたら、残るのは整数 $y$ と「次の手番の人」だけ。

ヒント3（誘導）

$a-b$ の降順に並べる。Left 先手なら Left が 1・3・5 番目（$a$ を足す）、Right が 2・4・6 番目（$b$ を足す）を取ったとして $y$ を計算
カードが尽きたとき、$N$ が偶数なら Left の番、奇数なら Right の番。整数 $y$ の山では、$y>0$ なら Left、$y<0$ なら Right が勝ち、$y=0$ なら手番の人が負け
よって Left 先手で Left が勝つのは $y>0$、または $y=0$ かつ $N$ が奇数のとき。勝ち手は温度が最大のカード

模範解答 (Python)

模範解答を表示する（まず自力で解いてから）

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1:2 * n + 1:2]]
    b = [int(x) for x in data[2:2 * n + 2:2]]
    order = sorted(range(n), key=lambda i: a[i] - b[i], reverse=True)   # 熱い順（温度 (a-b)/2）
    out = []
    # Left が先手: 熱い順に Left, Right, Left, ... が取る。最後に残る整数 y と、そのとき手番の人
    y = sum(a[i] for i in order[0::2]) + sum(b[i] for i in order[1::2])
    left_wins = y > 0 or (y == 0 and n % 2 == 1)
    out.append(f"Left {order[0] + 1}" if left_wins and n else ("Left" if left_wins else "Right"))
    y = sum(b[i] for i in order[0::2]) + sum(a[i] for i in order[1::2])
    right_wins = y < 0 or (y == 0 and n % 2 == 1)
    out.append(f"Right {order[0] + 1}" if right_wins and n else ("Right" if right_wins else "Left"))
    print('\n'.join(out))


main()

計算量: 整列 $O(N\log N)$。$N=2\times10^5$、$a,b$ を $[-10^{18},10^{18}]$ の一様乱数で 0.40 s（Python 3.14.7、M1 MacBook Pro 8GB、負荷平均 10〜12 での実測、起動込み）。

Step-by-Step 解説

1なぜ数の和で考えられないか

$\{3\mid-1\}$ に Left が先に動くと $3$、Right が先に動くと $-1$ で、どちらも先手が勝つ。数 $x$ なら先手・後手で勝者は変わらない（$x>0$ なら常に Left）。だから「値を足して符号を見る」方法（Day171〜174）は使えない。

2カードが尽きた後

数の回避定理により、カードが残っている間に整数の山で指す必要はない（全状態探索では整数の山の手も許して確かめた）。カードが尽きると残りは整数 $y$ の山で、手番の人が $y=0$ なら負け、$y\ne0$ なら符号どおり。

3温度の高い順に取る

$\mu_i=\frac{a_i+b_i}2$、$t_i=\frac{a_i-b_i}2$ とすると、カード $i$ を Left が取れば $\mu_i+t_i$、Right が取れば $\mu_i-t_i$。$\sum\mu_i$ は誰が何を取っても同じなので、勝負は $\pm t_i$ の取り合い。$t$ の降順に $t_1\ge t_2\ge\dots$ とすると、交互に一番大きいものを取ると $t_1-t_2+t_3-\cdots$。相手が温度の低いカードを取ったら、こちらは高い方を取れば損をしない（交換論法）。

4温度 0 のカード（スター）と偶奇

$a=b$ のカード（温度 0）は、どちらが取っても得点は同じ。しかし手番を 1 つ消費するので、最後に整数の山で手番を持つのが誰かを変える。入力例 2 がこの効果だけを取り出した例: $\pm1$ が 2 枚なら $y=0$ で後手勝ち、スターを足すと先手勝ち。

5勝ち手

先手が勝つ場合、温度が最大のカードを最初に取る。温度が同じカードが複数あっても、$a_i-b_i=a_j-b_j$ なら $a_i+b_j=a_j+b_i$ なので、どれを取っても $y$ は変わらない。

迷った他案と採らなかった理由

案	計算量	採否	理由
全状態探索（残りのカードの集合 × $X$ × 手番、整数の山の手も許す）	指数	検算用のみ	$N\le8$、$	a	,	b	\le5$
値の和の符号で判定	$O(N)$	不採用（誤り）	スイッチは数でない。入力例 1 で両方とも「先手勝ち」が出せない
Left は $a$ の大きい順、Right は $b$ の小さい順に欲張る	$O(N\log N)$	不採用（誤り）	600 局面中 141 局面で誤答（実測）。入力例 3 が反例
平均 $\frac{a+b}2$ の大きい順に取る	$O(N\log N)$	不採用（誤り）	600 局面中 130 局面で誤答（実測）
温度順に取るが、$y=0$ を常に後手勝ちとする	$O(N\log N)$	不採用（誤り）	600 局面中 79 局面で誤答（実測）。手番の偶奇を落としている
温度順に取り、$y$ と手番の偶奇で判定（本解）	$O(N\log N)$	採用	0.40 s

前提が変わったら

カードが 2 段以上のゲーム（例: $\{a\mid\{b\mid c\}\}$）なら、温度の高い順は最善とは限らない。熱図を描き、冷却（cooling）した値で比べる必要がある（本セッションでは未実装）
数の成分が分数（例: $\frac12=\{0\mid1\}$）でも、数の回避定理により最後に残る数の符号で決まる。$y=0$ の判定だけは厳密な分数で行う
スターが複数種類（$*2$ など、Nim の山）なら、偶奇ではなく Nim 和で決まる

よくあるミス

ミス	原因	正しい書き方
値の和の符号で勝者を決める	数のゲームの習慣	スイッチは数でない。先手・後手で勝者が変わる
自分の得点が一番良いカードを取る	相手の得点を見ていない	温度 $a-b$ の大きい順。600 局面中 141 局面で誤答（実測）
$y=0$ を後手勝ちにする	数のゲームの「0 は後手勝ち」をそのまま使う	カードの枚数の偶奇で、整数の山の手番が変わる。79 局面で誤答（実測）
温度 0 のカードを無視する	得点が変わらないので要らないと思う	手番を 1 つ消費する（入力例 2）
$\frac{a+b}2$、$\frac{a-b}2$ を浮動小数で計算	$10^{18}$ 付近で丸め誤差	$a-b$ のまま整数で比べる

次のステップ

発展1: 2 段のスイッチ $\{a\mid\{b\mid c\}\}$ を混ぜ、全状態探索で「温度順」が破れる最小の例を探す
発展2: 熱図（thermograph）を描いて、一般の短いゲームの平均値と温度を求める
発展3: 『Winning Ways』の熱いゲームの章で、本問の主張と証明を確かめる（本セッションでは未確認）

検証ログ（本セッションで実行した数値）

全状態探索との照合（実測）: カード 1〜8 枚、$|a|,|b|\le2,3,5$ のランダム局面 600（うち 30% は鏡像のカード $\{-b\mid-a\}$ を足して $y=0$ 付近を狙った）。整数の山の手も許した探索で、勝者が一致し、先手が勝つときの出力したカードが勝ち手の集合に入る。不一致 0。勝者の内訳: 先手勝ち 209、Left 197、Right 158、後手勝ち 36
誤った方法（実測、同じ 600 局面）: 自分の得点で欲張る 141、平均の大きい順 130、$y=0$ を常に後手勝ち 79 局面で誤答
入力例（実測）: 3 例とも全状態探索と一致。入力例 2 からスターを除いた $\pm1$ 2 枚は後手勝ち（Right / Left）
実行時間（実測、起動込み）: $N=2\times10^5$ で 0.40 s
扱っていない範囲: 2 段以上のゲーム、熱図、分数の数成分、原典の確認

自己評価

完全理解おおむね理解要復習

Day 175-Q3 — 2026-10-11 | スイッチの和（値が数にならない「熱い」ゲームを、温度の高い順に取り合う）

問題