ARC225 B - Independent Nim
独立ニム
考え方
Nim と名前についているが、ゲーム性は Nim と全く関係ない。
まず、小さい方から実験していく。
特に全部 $1$ の場合を考えてみる。
まず、$\{1\}$ の場合。
取れる手が $1$ つしかなく、明らかに先手必勝。
次に、$\{1,1\}$ の場合。
取れる手が実質 $1$ つしかなく、明らかに後手必勝。
$\{1,1,1\}$ の場合。
端を $1$ つ $0$ にすれば、後手必勝形にして相手に渡せる。
よって、先手必勝。
$\{1,1,1,1\}$ の場合。
両端を $0$ にすれば、後手必勝形にして相手に渡せる。
よって、先手必勝。
$\{1,1,1,1,1\}$ の場合。
これが初めての難しいケース。
まず、両サイドを削るのは、長さ $3$ にしても $4$ にしても先手必勝形で相手に渡すので負け。
$1$ 個ずつ $2$ グループか $3$ グループにするのは全部取られて負け。
$1$ と $2$ または $1$ と $3$ にするのは、$2$ だけにして返されて負け。
$2$ と $2$ のときだけ、これは続きを調べると勝ちになる。
ということで、予想として、長さ $2$ がたくさんあるだけのものは後手必勝と予想される。
これを数学的帰納法で証明する。
まず、長さ $2$ が $0$ 個ある場合。
何もないので既に後手が勝っている。
長さ $2$ が $k$ 個未満ある場合は全て後手必勝と仮定して、長さ $2$ が $k$ 個ある場合を考える。
先手がどこからどうとったとしても、各ブロックから $1$ つしか取れない。
従って、後手は同じブロックの残った $1$ 個を全て取ると、後手必勝形になっている。
以上により、長さ $2$ がたくさんあるだけのものは後手必勝であると示された。
次に、長さ $2$ 以外のものが存在する場合。
長さ $1$ のものは、消せる。
長さ $3$ のものは、長さ $2$ にできる。
長さ $4$ のものは、長さ $2$ にできる。
長さ $5$ のものは、長さ $2$ のもの $2$ ブロックにできる。
長さ $k$ ($k\geq 6$) のものは、長さ $k-3$ のものの対応形の端に $0,1,1$ か $1,1,0$ の適切な方をつける。
各ブロックは $0$ で隔てられているので、これらの操作は全てのブロックに対して同時に行える。
これらにより、長さ $2$ 以外のものが $1$ つでも存在すれば、長さ $2$ がたくさんあるだけの状態にできる。
以上により、$1$ の連続数を数えて、$2$ 連続以外のところが $1$ つでもあれば Alice の勝ち。
全て $2$ 連続（$1$ つもない場合を含む）の場合は Bob の勝ちである。
入力例1での動作
入力例1の全テストケースを順に考える。
1つ目のテストケースを受け取る。
n: 5
a: 1 0 1 0 1先頭から、それぞれ $1$ が何個続くか調べると、$1,1,1$ である。
最初の $1$ の時点で、$2$ 以外の数が見つかったので Alice の勝ちである。
2つ目のテストケースを受け取る。
n: 2
a: 1 1先頭から、それぞれ $1$ が何個続くか調べると、$2$ である。
$2$ 以外の数がないので Bob の勝ちである。
3つ目のテストケースを受け取る。
n: 14
a: 1 1 1 0 1 1 1 1 0 1 1 1 1 1先頭から、それぞれ $1$ が何個続くか調べると、$3,4,5$ である。
最初の $3$ の時点で、$2$ 以外の数が見つかったので Alice の勝ちである。
注意点
特になし。
別解
特になし。