BOJ 26973 - Circular Barn

BOJ 26973 - Circular Barn

직접 $N-\text{position}$인지를 검사해보면 $n \equiv 0 \pmod 4$ 가 아닐 때 항상 이긴다는 것을 알 수 있다.

이는 소수중에 $4$의 배수가 없고 $1,2,3$ 은 항상 지울 수 있다는 것에서 유도된다.

하지만 그냥 직접 몇개를 돌려봐도 바로 알 수 있다.

Nhoj가 이길 수 있는 수를 생각해본다.

어떤 수 $x$가 $4 \mid x$라면 가장 느리게 끝나게 만드는 횟수, $4 \nmid x$라면 가장 빠르게 끝나게 횟수를 $f(x)$라 하자. 예를 들어, $f(1)=1,~f(4)=2,~f(p)=1~~ \left(p \in \text{소수}\right)$ 이다.

John은 $4 \nmid a_i$ 인 $i$들에 대해 빠르게 게임을 끝내길 원할 것이고, $4 \mid a_i$인 $i$들에 대해 최대한 느리게 게임을 끝내길 원할 것이다.

$4 \mid x$ 라면 $f(x)$는 짝수이고 $4 \nmid x$라면 $f(x)$는 홀수이다.

Nhoj가 이기기 위한 전략을 보자.

$a_i \equiv 0 \pmod 4$ 이고 $\text{Min}_{j = 0}^{ i - 1 } f(a_j) > f(a_i)+2 \text{~AND~} \text{Min}_{ j = i + 1}^{ n - 1 } f(a_j) > f(a_i)$ 여야 한다.

여기서 $j$는 $4 \nmid a_j$ 인 $j$들이다.

$f(x)$만 적절히 전처리하면 문제가 해결된다.

$4 \nmid x$ 일 때 가장 빨리 끝내는 방법은 $p \le x$인 소수나 $1$인 $p$중에 $p \equiv x \pmod 4$인 가장 큰 $p$를 고르는 것이다.

그래야 $x-p\equiv 0 \pmod 4$ 가 되고 상대방에게 $4$의 배수를 줄 수 있다.

$4 \mid x$ 일 때 가장 느리게 방법은 사실 $p=2$ 인 경우이다. 왜냐면 $p$ 중 짝수인건 $2$밖에 없고 그럼 상대방도 어쩔수 없이 나에게 다시 $4$의 배수를 주기 위해 $2$만 뺄 것이기 때문이다.

USACO 정해에선 귀납적으로 $x \equiv 0 \pmod 2$ 인 경우엔 $f(x)=\dfrac{x}2$ 라고 설명한다.