룩, 비숍, 킹, 나이트, 궁전 게임
체스판 위에 체스말 $N$개가 놓여져 있다. 가장 왼쪽 아랫칸 좌표는 $(0, 0)$이고 가장 오른쪽 윗칸의 좌표는$(10^9-1 * 10^9 -1)$이다. 두 개 이상의 말이 한 칸에 동시에 있을 수 있다.
체스말의 좌표가 $(x, y)$일때 다음과 같이 움직일 수 있다.
- 룩,R
- $(x, i) (0 \leq i<y)$
- $(i, y) (0 \leq i<x)$
- 비숍,B
- $(x-i, y-i) (0<i\leq min(x,y))$
- 킹,K
- $(x, y-1)(y>0)$
- $(x-1, y)(x>0)$
- $(x-1, y-1)(x>0,y>0)$
- 나이트,N:
- $(x-1, y-2)(x>0, y>1)$
- $(x-2, y-1)(x>1, y>0)$
- 궁전,P:
- $(x, i) (0 \leq i<y)$
- $(i, y) (0 \leq i<x)$
- $(x-1, y-1)(x>1,y>1)$
구사가와 큐브러버가 턴을 번갈아면서 체스말 한 개를 움직일 때 더이상 체스말을 이동시킬수없는 사람이 게임을 지게 된다. 최선의 전략으로 게임을 할 때 게임에서 이기는 사람의 이름을 출력하시오.
풀이
solved.ac 기준 다이아 5 레벨 문제다 보니 어느정도 사전 지식이 필요하다. 스프라그-그런디 정리를 알고 있지 않으면 먼저 그것을 공부하는 것을 추천한다.
좌표의 범위가 넓기 때문에 전처리로 그런디 넘버를를 계산하면서 각각 말의 패턴을 다 구한 후 xor을 해서 답을 구할 수 있다.
이제 각각의 말마다 그런디 넘버를 계산하면서 패턴을 찾아보자.
비숍
1 |
|
1 |
|
그러므로 코드는 다음과 같다.
1 |
|
사실 굳이 코드를 안짜도 이 정도는 쉬워서 알수 있긴 하다.
킹
1 |
|
1 |
|
패턴이 보일락 말락한다.
좀더 확실하게 $20 * 20$을 보도록 한다.
1 |
|
$0$ 패턴
$x$ 가 짝수면서 $y$가 짝수
$2$ 패턴
$x$ 가 홀수면서 $y$가 홀수
$1$ 패턴
$0, 2$가 아니면서 $min(x, y)$가 짝수
$3$ 패턴
$0, 1, 2$가 아닌 나머지
요약
1 |
|
나이트
1 |
|
1 |
|
패턴을 알아 차릴수 있겠는가? 정리하면 다음과 같다.
1 |
|
룩
좀 어렵다
1 |
|
1 |
|
이 숫자 패턴이 뭔지 알겠는가? 수학적 센스가 뛰어난 사람은 금방 알아 맞출수 있다. 나는 그렇지 않았기 때문에 오래걸렸다…
답은 허무하고 간단하다.
1 |
|
궁전
이 문제가 어려운 이유, 이문제만 따로 16879 궁전게임으로 존재하며 플레티넘 1이다. 미리 그런디 넘버를 계산하고 패턴을 파악해보자.
1 |
|
1 |
|
자세히 보면 3*3 단위로 마치 스도쿠 배열처럼 특정 패턴이 반복된다는 것을 관찰할 수 있다.
그리고 그 3*3안에서도 패턴들이 있는데 이를 정리하면 다음과 같다. (이미 푼 문제라서 쉽게 넘어갔으나 찾기 좀 어렵다)
1 |
|
소스코드
위 5가지 패턴을 합치기만 하면 된다. 소스코드는 짧고 명쾌하다.
1 |
|
맞았습니다!
532바이트만에 짠 kyo20111
님의 풀이는 같은 내용이지만 정말 숏코딩을 잘하셨다!
물론 이문제 숏코딩 1등은 역시나 sait2000
님이시긴 한다. :god: