問題文：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$などに変換すると混乱しにくいかもしれないと思った。