yukicoder No.1506 Unbalanced Pocky Game - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

長さ ${N}$ の数列 ${A}$ があり， ${A}$ の末尾の要素を ${k}$ として，末尾の要素を ${0}$ 以上 ${k}$ 未満の整数に変えて ${0}$ になった要素は消すという操作を ${2}$ 人のプレーヤーが交互に行う．操作ができなくなる(自分の操作開始時に ${A}$ が空)と負けとなるとき，どちらのプレーヤーが勝つか．

${1\leq N\leq 2×10^5\\ 1\leq A_i\leq 10^9}$

解説

grundy数を考える． ${grundy_i(x)}$ を「 ${|A|=i}$ かつ ${A_i=x}$ 」のgrundy数とすると

${grundy_i(x)=\left\{\begin{array}{ll} 0 & (i=1\land x=0)\\ grundy_{i-1}(A_{i-1}) & (2\leq i \land x=0)\\ x-1 & (1\leq x\leq grundy_i(0))\\ x & (grundy_i(0) < x) \end{array} \right.}$