問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

インタラクティブ問題

次のようなゲームを行う.

$1$ から $N$ までの番号がついた $N$ 枚のカードがある.
$1 \leq x \leq N, L \leq y \leq R$ かつ, $y$ 枚のカード $x, x+1, \dots, x+y-1$ が全て存在するような整数の組 $(x,y)$ を選び, この $y$ 枚のカードを取り除く.
先に $(x,y)$ を選べなくなったほうが負け.

$N,L,R$ が与えられる. このゲームは先手必勝か? 後手必勝か? また, その解答に対して, 実際にジャッジとのゲームを行い, 勝利せよ.

制約

$1 \leq L \leq R \leq N \leq 2000$

解法1

このゲームについて, 以下のことがわかる.

2人で行う.
一方が勝ち, 一方が負ける.
有限回の手番でゲームが終了する.
ランダム要素がない.
全ての情報が両プレイヤーに開示されている.
同じ場面に遭遇したとき, 打てる手が人に依らない.

このようなゲームは不偏ゲームと呼ばれ, Grundy 数と Sprague–Grundy の定理によって勝敗の解析ができる.

よって, 与えられたゲームの Grundy 数を求められれれば, どちらが必勝か. そして, どのような手を選択すべきかが判定できる. しかし, 実際に Grundy 数を計算しようとすると, 以下のようになり, 素朴な方法だと $O(N^2(R-L)$ 時間かかってしまい, 間に合わない (( 一応高速化することによって $O(N^2 \log N)$ 時間が可能らしい).

なお, ちょうど $K$ 枚のカードが連続しているような状況における grundy 数 $G_K$ は

$G_K=\begin{cases} 0 & (K \lt L) \\ \operatorname{mex} \{G_t \oplus G_{K-y-t} \mid L \leq y \leq R, 0 \leq t \leq K-y \} & (L \leq K) \end{cases}$

である.

解法 2

$R-L$ が大きい時, Grundy 数を直接もとめることは難しいように思えるが, 実は $L \leq R$ のときは先手必勝であることが示せ, 勝利のための行動が容易に構築できる.

$L \neq R$ だから, $L \leq y \leq R$ かつ $N \equiv y \pmod{2}$ となるような $y$ が存在する. この $y$ を取ってくる.
先手の第1ターンでは $x$ を $\displaystyle x=\dfrac{N-y}{2}+1$ として $(x,y)$ を選択する.
このようにすると, $(x-1)$ 枚の連続した2つのカードの組 $1,2, \dots, x$ と $x+y, \dots, N$ が生成される.
後は自分のターンが来た際, 直前に相手が行った行動をその行った方とは他方の組で同等な行動を行うことを繰り返せば自分が勝てる.

解法 3

$L=R$ の場合, $L \leq y \leq R$ かつ $N \equiv y \pmod{2}$ となるような $y$ が存在するとは限らないが, このときは Grundy 数を直接求めても時間的猶予がある. よって, $G_0, \dots, G_N$ を求め, $G_N$ から先手後手を選択し, あとは自分のターンが来たら Grundy 数が $0$ になるような手を相手に押し付け続ければ良い.