전형적인 스프라그 그런디 문제다. 따라서 각 말의 nimber 값을 구하면 된다. 문제를 푸는 입장에서는 여러 게임 이론 문제처럼 단순 dp로 표를 그려놓고 열심히 규칙을 찾은 다음 케이스 워크로 구현하면 된다. 매우 큰 k에서 성립하는 규칙이 k >= 11에서 성립하기 때문에 k <= 10은 인덱스가 큰 부분을 작은 부분으로 옮기는 부분만 처리하고 작은 인덱스에 대해서 dp로 구할 수 있다. k >= 11은 영락없이 규칙을 찾아야 한다. 좌표 (x, y)의 nimber 값을 f(x, y)로 표현한다. k를 고정하고 표를 그려보면 k*k 영역 별로 규칙이 있음을 알 수 있다. 앞으로 k*k 영역을 타일이라고 부르겠다. 좌표 (x, y)가 주어졌을 때 (x, y)가 속하는 타일 좌표를 T(x, y) = (ceil(x / k), ceil(y / k))로, (x, y)의 타일 내에서의 좌표를 S(x, y) = ((x - 1) % k + 1, (y - 1) % k + 1)로 정의한다. (표기의 편의성을 위해 T(x) = ceil(x / k)로, S(x) = (x - 1) % k + 1로 정의한다) 문제의 대칭성에 의하여 x >= y인 영역만 고려하면 됨을 알 수 있다. 즉, T(x) >= T(y)인 타일만 고려한다. 아래는 k >= 11일 때 T(x) >= T(y)인 영역에서 f(x, y)의 규칙을 증명없이 제시한 것이다. 증명은 x + y에 대한 강한 수학적 귀납법으로 될 것이다. 아마도. 규칙이 보이니까 분명 맞긴 맞을텐데 수학적 귀납법을 다 확인해보기엔 양이 좀 있어서 하다 지쳐서 내려놓은 상태다... ## '대부분'의 경우 * T(x, y) % 2 = (1, 1)일 때 f(x, y) = 0 * T(x, y) % 2 = (0, 1)이고 T(x) >= 4, T(y) <= T(x) - 3일 때 f(x, y) = 1 * T(x, y) % 2 = (0, 0)이고 T(y) >= 4일 때 f(x, y) = 2 * T(x, y) % 2 = (1, 0)이고 T(x) >= 7, 4 <= T(y) <= T(x) - 3일 때 f(x, y) = 3 ## 원점 근처 * T(x, y) = (2, 1)일 때 f(x, y) = 1 when S(x) >= S(y) S(x) + 1 when S(x) < S(y) * T(x, y) = (2, 2)일 때 f(x, y) = max(S(x), S(y)) + 1 * T(x, y) = (3, 2)일 때 f(x, y) = k + 2 when S(x, y) = (1, 1) 2 when S(x) >= 2 and S(x) >= S(y) k + 3 when S(x) = 1 and S(x) < S(y) k + 2 when S(x) = 2 and S(x) < S(y) S(x) when S(x) >= 3 and S(x) < S(y) * T(x, y) = (4, 2)일 때 f(x, y) = 2 when S(x) = 1 3 when S(x) = 2 4 when S(x) = 3 3 when S(x) >= 4 ## x 축(?) 근처 * T(x) % 2 = 1, T(x) >= 5, T(y) = 2일 때 f(x, y) = 3 when S(x) = 1 2 when S(x) >= 2 * T(x) % 2 = 0, T(x) >= 6, T(y) = 2일 때 f(x, y) = 2 when S(x) = 1 3 when S(x) >= 2 Note: 타일이 한 칸 오른쪽으로 밀린 것 처럼 보인다. ## 대각선 근처 가장 규칙이 난해한 대각선 한 칸 오른쪽/아래쪽 타일에 대해 기술한다. 일단 간단한 S(x) >= S(y)부분부터 정리하면 다음과 같다. * T(x) = T(y) + 1이고 T(x) >= 4이고 S(x) >= S(y)일 때 f(x, y) = 1 when T(x) % 2 = 0 3 when T(x) % 2 = 1 이제 S(x) < S(y)일 때를 기술하기 위해서 다음과 같은 2차원 수열을 정의한다. 고정된 k에 대해서 x + 1 <= y < x + k인 정수쌍 (x, y)에 대해 정의된 2차원 수열 W(x, y)를 다음과 같이 정의한다. W(x, y) = W(x + k + 2, y + k + 2) when x < 0 W(x - k - 2, y - k - 2) when x >= k + 2 W(y - k - 1, x - 1) when y >= k + 1 and x <= k + 1 4 when x = 0 x + 4 when 1 <= x <= 5 and x + 1 <= y <= x + 4 y when 1 <= x <= 3 and x + 6 <= y <= 9 y when 1 <= x <= 5 and 10 <= y <= k - 1 x + 4 when 1 <= x <= 5 and y = k k + 1 when (x, y) = (1, 6) k when (x, y) = (2, 7) k + 1 when (x, y) = (3, 8) k when (x, y) = (4, 9) x - 1 when 6 <= x <= k - 1 and x + 1 <= y <= k 표기의 편의를 위해 (x', y') = (S(x) - T(x) + 4, S(y) - T(x) + 4)로 정의하자. * T(x) = T(y) + 1이고 T(x) >= 9이고 S(x) < S(y)일 때 f(x, y) = W(x', y') 4 <= T(x) <= 8에 대해서는 거의 W(x', y')와 같이 나오는데 일부가 다르다. 아래의 'W에서 다음과 같이 수정한다'라는 표현은 위의 W의 정의에서 해당하는 부분을 고친 새로운 W를 정의한 다음 f(x, y) = W(x', y')로 구한다는 의미이다. * T(x, y) = (8, 7)이고 S(x) < S(y)일 때 W에서 다음과 같이 수정한다. k when (x, y) = (1, 6) k when (x, y) = (2, 7) k + 1 when (x, y) = (3, 8) k when (x, y) = (4, 9) * T(x, y) = (7, 6)이고 S(x) < S(y)일 때 W에서 다음과 같이 수정한다. k + 1 when (x, y) = (1, 6) k + 1 when (x, y) = (2, 7) k + 1 when (x, y) = (3, 8) k when (x, y) = (4, 9) * T(x, y) = (6, 5)이고 S(x) < S(y)일 때 W에서 다음과 같이 수정한다. k when (x, y) = (1, 6) k when (x, y) = (2, 7) k when (x, y) = (3, 8) k when (x, y) = (4, 9) * T(x, y) = (5, 4)이고 S(x) < S(y)일 때 W에서 다음과 같이 수정한다. 6 when (x, y) = (1, 6) 7 when (x, y) = (2, 7) 8 when (x, y) = (3, 8) 9 when (x, y) = (4, 9) * T(x, y) = (4, 3)이고 S(x) < S(y)일 때 W에서 다음과 같이 수정한다. 6 when (x, y) = (1, 6) 7 when (x, y) = (2, 7) 8 when (x, y) = (3, 8) 9 when (x, y) = (4, 9) y when 1 <= x <= 5 and y = k # k <= 10 dp table을 채워보면 대각선 근처 이외에는 k >= 11일 때의 타일 분류를 그대로 사용할 수 있음을 알 수 있다. 규칙을 찾아도 되지만 그냥 같은 타일 분류가 되는 타일 중 인덱스가 가장 작은 타일로 평행이동 한 다음 dp로 구하면 된다. 대각선 근처는 T(x) >= 9에 대해서 S(x) >= S(y) 부분의 주기가 2이고 S(x) < S(y) 부분의 주기가 k + 2이므로 2 * (k + 2)를 주기로 평행하면 된다.