問題
$n$ 個の石が 1 つの山にある。先手と後手が交互に石を取る。
- 先手の最初の手では、$1$ 個以上 $n-1$ 個以下を取る（全部は取れない）
- 2 手目以降は、直前に相手が取った数の 2 倍以下（かつ 1 個以上、残りの個数以下）を取る
最後の石を取った人の勝ちとする。
$Q$ 個の $n$ について、両者が最善を尽くすときの 先手の初手のうち、そのあと先手が必ず勝てる手の数 $c$ と、そのような手のうち 最小の取る個数 $m$ を出力せよ。勝てる初手が無い（先手必敗）なら 0 0 を出力する。
入力形式
Q
n_1
n_2
...
n_Q制約
| # | 条件 |
|---|---|
| 1 | $1\le Q\le 2\times10^5$ |
| 2 | $2\le n_i\le 10^{18}$ |
入出力例
入力例1
5
5
6
17
100
1000000000000000000出力例1
0 0
1 1
2 1
2 3
20 2（$5$ はフィボナッチ数なので先手必敗。$17$ の勝てる初手は「1 個取る」「4 個取る」の 2 つ。$100=89+8+3$ の勝てる初手は 3 個と 11 個）
背景と出典
Fibonacci Nim は M. J. Whinihan「Fibonacci Nim」（The Fibonacci Quarterly 1(4), 1963）で解析されたとされる。結論は「$n$ がフィボナッチ数なら先手必敗、そうでなければ $n$ の Zeckendorf 分解の最小項を取れば勝てる」。本セッションでは原論文を参照していない。
本問の「勝てる初手 すべて の特徴づけ」（Step 4）は、状態 DP の結果から立てた予想を $n\le2000$ の全件で DP と照合 して確かめたもので、証明はしていない。
概念図：Zeckendorf 分解と「次の項が 2 倍より大きいか」
ヒント（クリックで段階的に開示）
ヒント1（方向性）
状態は「残り $r$ 個、今回取れる上限 $u$ 個」の組。$n\le30$ くらいまで DP で勝ち負けを表にし、先手必敗の $n$ を並べてみよう。
ヒント2（アプローチ）
先手必敗の $n$ は $2,3,5,8,13,21,\dots$（フィボナッチ数）。どの正の整数も「連続しないフィボナッチ数の和」に一意に書ける（Zeckendorf の定理）。例: $17=13+3+1$。
最小項 $z_1$ を取ると、残りの最小項 $z_2$ は $z_2>2z_1$（連続しないフィボナッチ数は 2 倍より大きく離れる）。相手は $2z_1$ 個までしか取れず、「$z_2$ という山」を崩しきれない。
ヒント3（誘導）
Zeckendorf 分解を小さい順に $z_1<z_2<\dots<z_t$ とし、$s_j=z_1+\dots+z_j$ とする。$j<t$ かつ $z_{j+1}>2s_j$ を満たす $s_j$ がちょうど勝てる初手 になる（$n\le2000$ で DP と全件一致）。
z = zeckendorf(n) # 小さい順
s = 0
for j in range(len(z) - 1): # j = t-1（全部取る）は初手で禁止
s += z[j]
if z[j+1] > 2 * s: 勝ち手 s模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
def main():
data = sys.stdin.buffer.read().split()
q = int(data[0])
fib = [1, 2] # 1, 2, 3, 5, 8, ...
while fib[-1] <= 10**18:
fib.append(fib[-1] + fib[-2])
rev = fib[::-1]
out = []
for t in range(1, q + 1):
n = int(data[t])
z = [] # Zeckendorf 分解（大きい順に貪欲）
r = n
for f in rev:
if f <= r:
r -= f
z.append(f)
z.reverse() # 小さい順に並べ直す
cnt, first, s = 0, 0, 0
for j in range(len(z) - 1): # 全部取る（j = 最後）は初手で禁止
s += z[j] # 小さい方から j+1 項の和を取る
if z[j + 1] > 2 * s: # 相手の上限 2s で次の項に届かない
cnt += 1
if first == 0:
first = s
out.append(f"{cnt} {first}")
sys.stdout.write("\n".join(out) + "\n")
main()計算量: 1 クエリ $O(\log_\varphi n)$（表は $10^{18}$ を超える最初の項までの 87 項）。実測で $Q=2\times10^5$、$n\le10^{18}$ の一様乱数が 1.31 s（Python 3.14.7、M1 Mac）。
Step-by-Step 解説
$W(r,u)$ = 残り $r$ 個・上限 $u$ 個で手番側が勝つか。
$$W(r,u)=\bigvee_{k=1}^{\min(u,r)}\Big(k=r\ \lor\ \lnot W(r-k,\,2k)\Big)$$
$W(r,u)=W(r,u-1)\lor(\dots k=u\dots)$ と累積すれば $O(r\cdot u)$。$n\le2000$ で 2.7 s（実測）。この表から先手必敗は $2,3,5,8,\dots,1597$（フィボナッチ数だけ）と読める。
大きいフィボナッチ数から貪欲に引くと、連続しないフィボナッチ数の和になる（連続する $F_k+F_{k+1}$ が残るなら貪欲で $F_{k+2}$ が先に取れていたはず）。
連続しないので、小さい順に並べた $z_1<z_2<\dots$ は $z_{j+1}\ge z_j+z_{j-1}+\dots$ を満たし、特に $z_{j+1}>2z_j$。
$z_1$ を取ると残りは $z_2+\dots+z_t$、相手の上限は $2z_1<z_2$。残りの「一番小さい山」$z_2$ をフィボナッチ数の山として相手は崩せない、という形が再帰的に続く。$n$ 自身がフィボナッチ数だと、初手で何を取っても相手がこの形を作れる（先手必敗）。
最小項だけでなく「小さい方から $j$ 項まとめて」取る $s_j$ も、次の項 $z_{j+1}$ が $2s_j$ より大きければ同じ理屈で勝ち手になる。逆にこれ以外は勝ち手にならない。
$n\le2000$ の全件で、この規則で作った勝ち手の集合が DP の集合と 完全一致（実測）。勝ち手の数の分布は 0 個: 15、1 個: 140、2 個: 537、3 個: 862、4 個: 421、5 個: 24。
例: $28=21+5+2$ → $s_1=2$（$5>4$ ○）、$s_2=7$（$21>14$ ○）→ 勝ち手 $\{2,7\}$。
$z_{j+1}=2s_j$ なら相手はちょうど $z_{j+1}$ 個取れて形が崩れる。「$\ge$」と書いた版は $n\le2000$ のうち 144 件で出力が誤った（実測）。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| 状態 DP $W(r,u)$ | $O(n^2)$ | 検算用のみ | $n\le2000$ で 2.7 s。$10^{18}$ は不可能 |
| 最小項 $z_1$ だけを勝ち手として数える | $O(\log n)$ | 不採用 | 勝ち手の数が $n\le2000$ の 1999 件中 1844 件で誤る（実測）。最小の勝ち手だけなら正しい |
| 「$\ge$」で判定 | $O(\log n)$ | 不採用 | 144 件で誤る（実測） |
| $s_j$ と $z_{j+1}>2s_j$（本解） | $O(\log n)$ | 採用 | DP と $n\le2000$ で全件一致 |
前提が変わったら:
- 上限が直前の $k$ 倍（$k\ne2$）なら、先手必敗の列はフィボナッチ数ではなく $a_{i+1}=a_i+a_j$（$a_j$ は $k a_j\ge a_i$ となる最小）のような別の列になる（Schwenk 1970 の一般化として知られるが、本セッションでは確かめていない）。DP で表を作ってから規則を探す手順は同じ
- 初手で全部取ってよい なら先手は常に勝つ（自明）。本問の「$n-1$ 個以下」がゲームを成り立たせている
- Step 4 の特徴づけは $n\le2000$ の照合だけが根拠。証明なしで本番に使うなら、少なくとも自分でも小さい範囲の DP と照合してから出す
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 最後の項まで $s_j$ を数える | $s_t=n$ は「全部取る」で初手では禁止 | range(len(z) - 1) |
比較を >= にする | ちょうど 2 倍なら相手が取れる | z[j+1] > 2 * s（>= は 144 件誤り） |
| 浮動小数で $\log_\varphi n$ を計算して項を探す | $10^{18}$ 付近で丸め誤差 | 整数のフィボナッチ表（87 項）を作って貪欲 |
次のステップ
- 発展1: 途中局面（残り $r$、上限 $u$）から勝ち手をすべて数える（$u$ で制限された $s_j$ を数える）
- 発展2: 上限が直前の 3 倍の版を DP で調べ、先手必敗の列を見つける
- 次回予告: DP の遷移を「凹関数との (max,+) 畳み込み」とみて高速化する → Q3
検証ログ（本セッションで実行した数値）
- 状態 DP との一致（実測）: $n=2..2000$ の全 1999 件で、プログラム全体（標準入出力）の出力（勝ち手の数と最小の勝ち手）が DP と全件一致
- 先手必敗の $n$（実測）: $n\le400$ で
[2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]（フィボナッチ数だけ） - 誤りの件数（実測、1999 件）: 最小項だけを数える → 1844 件、
>=→ 144 件 - 入力例（DP で列挙）: $6\to\{1\}$、$17\to\{1,4\}$、$100\to\{3,11\}$、$1000\to\{13\}$。$10^{18}$ は Zeckendorf 27 項で勝ち手 20 個・最小 2
- 実行時間（実測）: $Q=2\times10^5$、$n\in[2,10^{18}]$ の一様乱数で 1.31 s
- 扱っていない範囲: Step 4 の証明、Whinihan 原論文との照合