젓가락 게임

상태와 유한성

현재 플레이어의 1손과 2손의 수를 $a$와 $c$, 상대방의 1손과 2손의 수를 $b$와 $d$라 하자. $n=a+c$, $m=b+d$로 둔다. 손의 위치는 중요하지 않다.

각 1손에 가중치 $2$, 각 2손에 가중치 $1$을 주면, 한 번 공격할 때마다 양쪽 손의 가중치 합이 적어도 $1$ 줄어든다. 따라서 무승부는 없다. 이 가중치 합에 대한 강한 귀납법으로 다음 판정식을 동시에 증명할 수 있다. 현재 플레이어의 손이 없으면 패배이고, 상대방의 손이 없으면 이미 승리한 상태로 본다.

판정식

• $n>m$이면 승리한다.
• $m\geq n+2$이면 패배한다.
• $n=m$이면, $b=m$이고 가 홀수일 때만 패배한다.

손 수가 다른 경우

$n>m$일 때 상대 손을 즉시 제거할 수 있으면 제거한다. 상대는 자신의 턴을 손이 적어도 $2$개 부족한 상태로 시작하므로 패배한다. 즉시 제거할 수 없다면 양쪽 손이 모두 1손이다. 상대의 1손 하나를 2손으로 바꾼다. 상대는 손이 더 적고 2손도 있으므로, 손이 하나 부족할 때의 예외적인 승리 조건도 만족하지 못한다.

$m\geq n+2$일 때는 어떤 공격을 해도 상대방의 손이 현재 플레이어보다 더 많이 남는다. 따라서 상대방이 승리한다.

$m=n+1$일 때 상대의 1손을 2손으로 바꾸면, 상대가 더 많은 손을 가지고 턴을 시작하므로 패배한다. 승리하려면 상대 손을 하나 제거하여 동수를 만들어야 한다. 다음 플레이어가 동수에서 패배하려면 그 상대, 즉 현재 플레이어의 손이 모두 1손이어야 하고, 다음 플레이어의 1손 수가 홀수여야 한다. 자신의 손이 모두 1손이라면 제거할 수 있는 것은 상대의 2손뿐이다. 따라서 정확히 $a=n$, $b<m$, $b$가 홀수인 경우에 승리한다.

손 수가 같은 경우

먼저 상대방에게 2손이 있다고 하자. 상대 손 하나를 제거한 뒤 상대가 손 하나 부족한 상태의 승리 조건을 만족하지 않도록 고르면 된다.

• 상대의 2손이 적어도 두 개면 2손 하나를 제거한다. 상대에게 2손이 남으므로 다음 턴에 승리할 수 없다.
• 상대의 2손이 하나이고 자신에게 2손이 있으며 상대에게 1손도 있으면, 자신의 2손으로 상대의 1손을 제거한다. 상대에게 2손이 남는다.
• 자신의 손이 모두 1손이면 상대의 2손을 제거한다. 다음 플레이어의 상대가 모두 1손이므로 예외적인 승리 조건이 성립하지 않는다.
• 남은 경우는 상대 손이 하나뿐인 경우이며, 그 손을 제거하면 즉시 승리한다.

상대의 손이 모두 1손이면, 자신의 2손으로 상대의 1손을 제거하는 수는 $a$가 짝수일 때만 승리하는 수이다. 다음 플레이어는 손 하나가 부족하며, 자신의 모든 손이 1손인 상태에서 상대의 1손 수 $a$의 홀짝에 따라 승패가 정해지기 때문이다.

자신의 1손으로 상대의 1손을 2손으로 바꾸는 수는, 자신의 손도 모두 1손이고 $n$이 짝수일 때만 승리한다. 다음 상태에서 손 수가 같고, 다음 플레이어의 1손 수가 $n-1$이기 때문이다. 이를 합치면 상대가 모두 1손인 경우에는 정확히 $a$가 홀수일 때 패배한다.

상대에게 2손이 있다고 해서 반드시 그 2손부터 제거해야 하는 것은 아니다. 예를 들어 양쪽이 각각 1손과 2손을 하나씩 가진 경우에는 자신의 2손으로 상대의 1손을 제거해야 한다.

서브태스크와 구현

서브태스크 1은 $(a,c,b,d)$를 상태로 하는 메모이제이션 완전탐색으로 해결한다. 가능한 공격 종류는 네 개뿐이며, 공격 후 현재 플레이어와 상대방의 역할을 바꾼다. 패배 상태로 보내는 공격이 하나라도 있으면 승리이다. 손 수는 증가하지 않는다. 양쪽의 최대 손 수를 $K$라 할 때 상태 수는 $O(K^4)$이고, 제공된 구현은 정렬된 맵을 사용하므로 시간은 $$, 공간은 이다. 이면 충분하다.

서브태스크 2에서는 $N>M$이거나 $N=M$이고 $N$이 짝수인 경우에만 선공이 승리한다. 시간과 공간은 $O(1)$이다.

전체 문제는 판정식에 $n=N$, $m=M$, $a=a_1$, $$을 대입하면 된다. 시간과 공간은 이다. 입력과 계산에는 64비트 정수를 사용한다.

여러 테스트 케이스는 독립적으로 처리한다. 전체 정답의 시간은 $O(T)$, 추가 공간은 $O(1)$이다. 완전탐색 구현은 테스트 케이스 사이에 메모이제이션을 공유하므로 전체 시간은 $O(T+K^4\log(K+1))$, 공간은 이다. 은 개수로만 처리하므로 전체 손 수의 합에 대한 제한은 필요하지 않다.

Solution written by GPT