問題
$N$ 枚の長方形の板がある。$i$ 枚目は縦 $h_i$ 行・横 $w_i$ 列のマス目に区切られている。Left と Right の 2 人が交互に次の操作をする。
- Left: 横幅が 2 以上の板を 1 枚選び、マス目の縦の線に沿って切り、横幅 $c$ と $w-c$ の 2 枚に分ける（$1\le c<w$）
- Right: 縦幅が 2 以上の板を 1 枚選び、マス目の横の線に沿って切り、縦幅 $c$ と $h-c$ の 2 枚に分ける（$1\le c<h$）
自分の番に操作できない人の負けである。「Left が先手のとき」と「Right が先手のとき」のそれぞれについて、両者が最善を尽くしたときの勝者を答えよ。さらに先手が勝つ場合は、勝ちにつながる最初の 1 手を答えよ（複数あればどれでもよい）。
入力形式
N
h_1 w_1
...
h_N w_N出力形式
2 行。1 行目は Left が先手の場合、2 行目は Right が先手の場合。先手が勝つなら Left i c（または Right i c）、すなわち板 $i$ を幅（Right なら高さ）$c$ と残りに切る手を出力する。後手が勝つなら勝者の名前（Left または Right）だけを出力する。
制約
| # | 条件 |
|---|---|
| 1 | $1\le N\le2\times10^5$ |
| 2 | $1\le h_i,w_i\le10^{18}$ |
入出力例
入力例1
1
1 3出力例1
Left 1 1
Left（Right は高さ 1 の板を切れない。Left は先手でも後手でも勝つ）
入力例2
2
2 2
3 3出力例2
Right
Left（値の和が 0 なので、どちらが先手でも後手が勝つ）
入力例3
3
3 8
8 2
1 2出力例3
Left 1 2
Left（値は $3$, $-3$, $1$ で和は $1$。Left は板 1 から幅 2 を切り落とし、和を 0 にする。3 例とも全状態のミニマックスと一致）
背景と出典
- パルチザンゲームの値: 局面 $G$ の Left の選択肢の値の最大を $L$、Right の選択肢の値の最小を $R$ とし、$L<R$ なら $G$ の値は「$L$ と $R$ の間で最も単純な数」（単純性規則: 区間に整数があれば絶対値が最小の整数、無ければ分母が最小の 2 進小数）。値が数のゲームの和は値の和で、和 $>0$ なら Left、$<0$ なら Right が手番によらず勝ち、$=0$ なら後手が勝つ
- Cutcake は Berlekamp–Conway–Guy『Winning Ways』で扱われる例と記憶している（原典は本セッションで未確認）。本問の閉じた式は原典を見ずに、単純性規則で作った $40\times40$ の表から当て、下の帰納法で示した
- 赤青 Hackenbush（Day171・172）との違い: Hackenbush の値は 2 進小数で、和の符号を正確に出すのに多倍長の分数が要った。Cutcake の値は整数なので、和は 64 ビットに収まらなくても Python の整数でそのまま足せる
概念図
ヒント（クリックで段階的に開示）
ヒント1（方向性）
Sprague–Grundy の数（Grundy 数）は使えない。Left と Right で打てる手が違うパルチザンゲームだから。各板の「値」を求めて足し、符号を見る。
ヒント2（アプローチ）
小さい板の値を単純性規則で表にする。$h=1$ の行は $0,1,2,3,\dots$、$h=2,3$ の行は $-1,0,0,1,1,2,2,\dots$、$h=4..7$ の行は $0$ が 4 個ずつ並ぶ……と、$h$ を 2 冪に切り下げた値 $b$ で $w$ を割っているように見える。
ヒント3（誘導）
- $w\ge h$ のとき $v(h,w)=\lfloor w/b\rfloor-1$（$b=2^{\lfloor\log_2h\rfloor}$）。$w<h$ のときは縦横を入れ替えて符号を反転
- 和 $S>0$ なら、値 $1$ 以上の板が必ずある。その板から幅 $b$ を切り落とすと値がちょうど $1$ 減り、和が $S-1\ge0$ になる。Right 番で和 $\ge0$ なら Left が勝つ
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
def value(h, w):
# Cutcake の値。Left は縦に切って幅 w を分け、Right は横に切って高さ h を分ける
if w >= h:
return (w >> (h.bit_length() - 1)) - 1
return -((h >> (w.bit_length() - 1)) - 1)
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
hs = [int(x) for x in data[1:1 + 2 * n:2]]
ws = [int(x) for x in data[2:2 + 2 * n:2]]
vals = [value(h, w) for h, w in zip(hs, ws)]
s = sum(vals)
out = []
# Left が先手: s > 0 なら値 1 以上の長方形から幅 2^floor(log2 h) を切り落とす
if s > 0:
i = next(i for i in range(n) if vals[i] >= 1)
out.append(f"Left {i + 1} {1 << (hs[i].bit_length() - 1)}")
else:
out.append("Right")
# Right が先手: s < 0 なら値 -1 以下の長方形から高さ 2^floor(log2 w) を切り落とす
if s < 0:
i = next(i for i in range(n) if vals[i] <= -1)
out.append(f"Right {i + 1} {1 << (ws[i].bit_length() - 1)}")
else:
out.append("Left")
print('\n'.join(out))
main()計算量: 板 1 枚につき bit_length とシフトで $O(1)$（$10^{18}$ は 60 ビット）、全体 $O(N)$。$N=2\times10^5$、$h,w\le10^{18}$ で 0.25 s（Python 3.14.7、M1 MacBook Pro 8GB、負荷平均 2〜3 での実測、起動込み）。
Step-by-Step 解説
$v(1,1)=0$。$v(h,w)$ は Left の選択肢 $v(h,c)+v(h,w-c)$ の最大 $L$ と、Right の選択肢 $v(c,w)+v(h-c,w)$ の最小 $R$ の間で最も単純な数。$h,w\le40$ の 1600 マスを計算すると、すべて整数で $L<R$ を満たし、上の式と 1600 マスすべて一致した（実測 0.19 s）。
$b=2^{\lfloor\log_2h\rfloor}$、$v=\lfloor w/b\rfloor-1$ とする。
- 幅 $x\ge b$ の破片の値は $\lfloor x/b\rfloor-1$: $x\ge h$ なら式そのもの。$b\le x<h$ なら $x<2b$ なので値は $0=\lfloor x/b\rfloor-1$
- 幅 $x<b$ の破片の値は $-1$ 以下: $x<b\le h$ なので式の $w<h$ 側で、$h/2^{\lfloor\log_2x\rfloor}\ge2$
- Left の最善 $L$: $v\ge1$（$w\ge2b$）なら $c=b$ で $0+(v-1)=v-1$ が最大（2 枚とも幅 $\ge b$ だと $\lfloor c/b\rfloor+\lfloor(w-c)/b\rfloor\le\lfloor w/b\rfloor$）。$v=0$ なら必ず一方が幅 $<b$ で $L\le-1$
- Right の最善 $R$: 高さ $c$, $h-c$ の破片はどちらも高さ $<h$ で、$h<2b$ なので一方は高さ $<b$。その破片は $2^{\lfloor\log_2c\rfloor}\le b/2$ より値 $\ge2v+1$、もう一方は値 $\ge v$。よって $R\ge3v+1\ge v+1$
- $L\le v-1<v<v+1\le R$ で、$(L,R)$ に入る最も単純な数は $v$（$v\ge1$ なら $L=v-1\ge0$ より大きい最小の整数、$v=0$ なら $0$ 自身）。$h=1$ では Right の手が無く $R=+\infty$ でも同じ
値が整数のゲームの和は値の和。$S>0$ なら Left、$S<0$ なら Right が、手番によらず勝つ。$S=0$ なら後手が勝つ。
Left 先手で $S>0$: 値 $v_i\ge1$ の板 $i$ がある。幅 $b_i=2^{\lfloor\log_2h_i\rfloor}$ を切り落とすと、破片の値は $0$ と $v_i-1$（Step 2）。和は $S-1\ge0$ で、Right の番。Right 先手は縦横を入れ替えて同じ。
「Left が切れる線の数 − Right が切れる線の数」= $w-h$ は、高さ 1 の板（値 $w-1$）や $3\times4$（値 1）では一致する。しかし $3\times8$ の値は $3$ で $w-h=5$、$4\times7$ の値は $0$ で $w-h=3$。Left は幅を $b$ ずつしか「得」にできないので、値は $w$ に比例して増えず $w/b$ に比例する。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| 局面（板の多重集合）のミニマックス | 指数 | 不採用 | 検証用。辺 5 以下・3 枚まで |
| 単純性規則で表を作る | $O(HW(H+W))$ | 不採用 | 正しいが $10^{18}$ には届かない。式を見つけるための道具として使った（$40\times40$ で 0.19 s） |
| Grundy 数の XOR | — | 不採用（誤り） | パルチザンゲームでは定義できない |
| 値を $w-h$ とする | $O(N)$ | 不採用（誤り） | 900 局面中 141 局面で勝敗を誤る（実測） |
| 値を $\lfloor w/h\rfloor-1$ とする（2 冪に切り下げない） | $O(N)$ | 不採用（誤り） | 900 局面中 129 局面で誤る。$h$ が 2 冪のときだけ正しい |
| 閉じた式＋値の和＋値 1 以上の板から $b$ を切る（本解） | $O(N)$ | 採用 | 0.25 s |
前提が変わったら:
- 切った破片のうち片方を捨てる（Eatcake 系）なら、値は整数とは限らない。表を作り直して式を探す（未計測）
- 板が長方形でない（L 字など）なら、閉じた式は無いかもしれない。小さい形の値を表にして、和に分ける
- 最後に動いた人の負け（misère）なら、値の和で判定できない。Day170-Q1 のように局面の全探索から始める
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| Grundy 数の XOR で判定 | 不偏ゲームと混同 | パルチザンゲームの値（整数）の和 |
| $b$ を $h$ のまま使う | 表の規則性を 2 冪で見ていない | 1 << (h.bit_length() - 1)。900 局面中 129 局面で誤答（実測） |
| 和が 0 のとき先手勝ちにする | 数のゲームで 0 は後手勝ち | $S=0$ なら後手 |
| 勝ち手で値 0 の板を切る | 値を下げすぎる | 値 1 以上の板から $b$ を切り落とすと値がちょうど 1 減る |
math.log2 で $b$ を求める | $10^{18}$ 付近で浮動小数の丸め | bit_length を使う |
次のステップ
- 発展1: Right の手が「横に切って片方を捨てる」に変わった変種の値を、表から当てて示す
- 発展2: 値が数にならないパルチザンゲーム（温度を持つゲーム）の和を、熱図（thermograph）で比べる
- 発展3: 『Winning Ways』の Cutcake の章を確認し、本問の式と証明を照らし合わせる（本セッションでは未確認）
検証ログ（本セッションで実行した数値）
- 式の確認（実測）: 単純性規則で $1\le h,w\le40$ の 1600 マスを計算し、すべて整数・$L<R$ で、閉じた式と 1600 マス一致（0.19 s）
- 正解との照合（実測）: 板の多重集合を状態にしたミニマックス（$1\times1$ は捨てる）で、辺 4 以下・1〜3 枚の 600 局面と、辺 5 以下・1〜2 枚の 300 局面、計 900 局面。勝者が一致し、先手が勝つ場合に出力した手で動かすと相手番で相手が負けることも確認。不一致 0
- 誤った方法（実測、同じ 900 局面）: 値を $w-h$ とすると 141 局面、$\lfloor w/h\rfloor-1$ とすると 129 局面で勝敗を誤る
- 入力例（実測）: 3 例ともミニマックスと一致。例 3 の勝ち手のあとの局面 $(3,2),(3,6),(8,2),(1,2)$ は Right 番で Right が負け
- 実行時間（実測、起動込み）: $N=2\times10^5$、$h,w$ を $[1,10^{18}]$ の一様乱数で 0.25 s
- 扱っていない範囲: Eatcake などの変種、misère、原典の確認