문제 문장 : 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$등으로 변환하면 혼란하기 어려울지도 모른다고 생각했다.