問題文:AtCoder Beginner Contest 027 C - 倍々ゲーム
解法
勝敗が決着するところ($N$近辺)から巻き戻すように考えると分かりやすい。自分の番になった時に$N+1$(以上)だったら勝ち。$N$なら負け。$N-1$より下は、大ざっぱに考えると、2倍して$N$を超えるような範囲なら負ける、それより下の範囲なら勝つ、というように、勝ちゾーンと負けゾーンが交互に存在すると考えられる。自分の番に回ってきた時の$x$を横軸に、最終的な勝敗を縦軸に取ると、下図のようになる。
勝ちゾーンと負けゾーンの下限を求めることを考える。勝ちゾーンの下限を$y_i$、負けゾーンの下限を$z_i$とする(図参照)。まず、$y_0=N+1$。
勝ちゾーンの下限$y_i$から、一つ左の負けゾーンの下限$z_i$を求めることを考える。一手進めると勝ちゾーンに入ってしまう(=相手が勝つ、自分が負ける)条件は、$2x, 2x+1$のどちらを選んでも、勝ちゾーンの下限$y_i$以上の値になってしまうこと。なるべく$y_i$以上になりたくないので、小さい方の手=$2x$を選ぶべき。よって、
\begin{align}
2x &\ge y_i \\
x &\ge \frac{y_i}{2}
\end{align}
よって下限$z_i$は以下のとおり($\lceil \ \ \rceil$は切り上げを表す)。
z_i=\Bigl\lceil \frac{y_i}{2} \Bigr\rceil
(切り上げなのか切り捨てなのか+1するのか-1するのか、など混乱しやすいので、式変形だけでここまで導いておくと楽になる、と現在のところ思っています)
次に、負けゾーンの下限$z_i$から、一つ左の勝ちゾーンの下限$y_{i+1}$を求めることを考える。一手進めると負けゾーンに入ることができる(=相手が負ける、自分が勝つ)条件は、$2x, 2x+1$のどちらかを選べば、負けゾーンの下限$z_i$以上の値になれること。なるべく$z_i$以上になりたいので、大きい方の手=$2x+1$を選ぶべき。よって、
\begin{align}
2x+1 &\ge z_i \\
x &\ge \frac{z_i-1}{2}
\end{align}
よって下限$y_{i+1}$は以下のとおり。
y_{i+1}=\Bigl\lceil \frac{z_i-1}{2} \Bigr\rceil
これで、$y_0$→$z_0$→$y_1$→$z_1$→$y_2$→$z_2$→… と順に計算できるようになった。
後は、スタート時点の値である $1$ が、勝ちゾーンに入っていれば先手の勝ち、負けゾーンに入っていれば後手の勝ちと判定できる。$y_i, z_i$を順に計算するループで、初めて1以下になるのが$y_i$なら先手勝ち、$z_i$なら後手勝ち、とすればよい。
感想
切り上げ$\lceil \ \ \rceil$なのか切り捨て$\lfloor \ \ \rfloor$なのか、-1するのか+1するのかしないのか、のあたりで混乱した。解を不等式で求め、それを最後に$\lceil \ \ \rceil$や$\lfloor \ \ \rfloor$などに変換すると混乱しにくいかもしれないと思った。