Merry Problem Solving 2일차
Merry Problem Solving 2일차입니다! 12/22에 푼 문제들입니다.
문제: Nim 게임을 하는데, i번째 무더기에는 처음에 Ai개의 돌이 있고, i번째 무더기에 X개의 돌이 있을 때 최소 1개에서 최대 X/Ki (나머지는 버림)개 사이의 갯수에 돌만 가져갈 수 있습니다. 서로 번갈아가면서 하나의 무더기에서 몇개의 돌을 번갈아가면서 가져가고, 더 이상 돌을 가져갈 수 없는 사람이 진다고 했을 때, 첫째 사람이 이기는지, 둘째 사람이 이기는지를 구하시오.
풀이: 이 문제는 그냥 Nim 게임(모든 K가 1인 경우)를 푼다고 하면, Impartial Game에서의 Sprague-Grundy Theorem를 사용합니다. 이에 관한 정보는 위키피디아 게시글에서 얻을 수 있습니다.
요약하자면 Impartial Game이란 누가 플레이하냐에 관계 없이, 현재 상태로, 바꿀 수 있는 다음 상태가 정해지며 (첫째 사람 혹은 둘째 사람만 가져갈 수 있는 돌이라는건 존재하지 않습니다.) 유한한 게임입니다. (게임이 무한히 진행될 수 없습니다.) Normal play condition 이라는 것은, 더 이상 일을 계속할 수 없는 사람이 진다는 것을 의미합니다. 여기서 상태라고 함은, 이 게임에서는 각 무더기에 있는 돌의 갯수가 됩니다.
여기에서 우리는 Nimber(혹은 Grundy Number)라는 것을 정의합니다. 이 Nimber는 재귀적으로 정의 되는데, "갈 수 있는 상태의 Nimber를 모두 모았을 때, 등장하지 않는 가장 작은 0 이상의 정수." 라고 정의합니다.
예를 들어, K=4인 상황을 가정합시다. 이 경우에 X = 0, 1, 2, 3인 경우에는 돌을 더 이상 가져갈 수 없기 때문에 (X/K 가 1 미만이기 때문에) 갈 수 있는 상태가 존재하지 않기 때문에, 어떤 정수도 등장하지 않고 Nimber는 0이 됩니다. X = 4인 경우에는, X=3인 상태로만 갈 수 있습니다. 이 때의 Nimber는 0이고, 1은 존재하지 않기 때문에, X=4일때 Nimber는 1입니다. 마찬가지로 X=5일때는 0, X=6일때는 1, X=7일때는 0, X=8일 때는, 1개 이상 2개 이하의 돌을 가져갈 수 있고, X=6, 7인 상태로 갈 수 있고, Nimber를 모두 모으면 0, 1이기 때문에 2가 등장하지 않고, X=8일때의 Nimber는 2입니다. X=9일때의 Nimber는 X=7, 8일때의 Nimber를 모아 보면 0과 2인데, 1이 등장하지 않는 가장 작은 수 이므로 Nimber가 1입니다.
이렇게 K=4인 경우에 Nimber를 만들어 보면 다음과 같은 표가 나옵니다.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
2 |
1 |
0 |
2 |
3 |
1 |
0 |
2 |
4 |
3 |
이 Nimber에는 다음과 같은 성질이 있습니다. Nimber가 0이면 자신이 패배하고, Nimber가 0이 아니면 자신이 승리합니다. 이유는, Nimber가 0이 아니면, 0이 다음 상태라는 것을 의미하고, 다음 사람의 턴을 Nimber가 0인 상태로 만들 수 있습니다. 이렇게 다음 사람의 Nimber를 0으로 계속 만들 수 있고, Nimber가 0이 아니면 갈 수 있는 상태가 있다는 것을 의미하기 때문에 패배하지 않습니다. 그래서 4, 6, 8, 9, 11, 12, ... 이면 K=4일때 무더기가 하나일 때 처음 사람이 이깁니다.
그럼 여러개의 게임을 동시에 진행하는 경우에는 어떨까요? 우리는 Sprague-Grundy Theory를 쓰게 됩니다. 여러개의 게임을 동시에 진행하는 경우의 Nimber는 모든 subgame의 Nimber를 XOR한 값입니다. 증명은 위키백과 문서를 참고해 주시기 바랍니다.
이제 우리는 이 멋진 정리의 도움을 받아, 각 수의 Nimber를 구하는 것으로 일이 줄었습니다. 각 수의 Nimber를 구하는 방법은 어떻게 될까요? 위의 표에서 규칙성을 찾으면 다음과 같은 정리를 증명할 수 있습니다.
정리: nimber(X-X/K)... nimber(X)는 0부터 X/K까지의 X/K+1개의 수가 모두 존재한다.
증명: 강한 수학적 귀납법을 사용합니다.
base case: X<K, nimber(X)는 0이고, 자명합니다.
inductive case:
1. X가 K를 정확히 나눌 때, X-X/K는 (X-1) - (X-1)/K과 같으므로, X가 갈 수 있는 상태인 nimber(X-X/K)...nimber(X-1)를 모두 모으면 0부터 (X-1)/K = X/K-1 까지 이고, nimber(X)는 X/K 이므로, 성립합니다.
2. X가 K를 정확히 나누지 않을 때, X 가 갈 수 있는 상태인 nimber(X - X/K)...nimber(X-1)을 모두 모으면, 0부터 X/K = (X-1)/K 에서, nimber(X-1 - (X-1)/K)가 빠진 형태가 됩니다. 여기서 nimber의 정의에 의해서 nimber(X) = nimber(X-1 - (X-1)/K)가 되어서, 성립하게 됩니다.
우리는 이 증명을 하면서 유용한 정보를 얻었습니다. X가 K를 정확히 나누면 nimber(X) = X/K이고, 아니면 nimber(X) = nimber(X-X/K-1)이 됩니다.
이것을 그대로 구현하면 시간이 오래 걸리게 됩니다. 가령이면, K=A/2+1 정도의 경우를 생각 해 봅시다. X/K = 1이고, 계속 2씩 숫자를 빼게 되면, A/4번 정도 뺄셈을 하게 됩니다. 이렇게 되면 O(A)의 시간이 걸리게 되겠죠. 그래서 우리는 여기서 시간복잡도를 줄일 아이디어를 얻을 수 있습니다. 바로 계속 2씩 숫자를 뺀다는 부분은, X/K 가 작은 경우에, 같은 숫자를 빼는 경우가 많다는 것입니다. X/K 가 바뀌려면, X%K 만큼을 빼야하고, 이것을 빼는 동안에는 X/K의 배수로 한번에 빼 줄수가 있습니다.
이 경우에 숫자는 X/K가 적어도 1씩 줄고, K가 적어도 1씩 줄게 됩니다. (X/K - 1)(K-1) = XK - X/K - K + 1이므로, 숫자는 X/K + K 만큼은 적어도 줄게 되고, 산술기하평균 부등식에 의해서, 숫자가 적어도 sqrt(X)씩 줄게 되어서, 시간복잡도가 O(sqrt(A)) 가 나오게 됩니다.
우리는 어떤 무더기 하나의 Nimber를 sqrt(A)에 구할 수 있습니다! 이 Nimber를 모두 xor하면 답이 나오게 됩니다. 총 시간복잡도는 O(nsqrt(A)) 가 됩니다.
문제: 0과 1로 이루어진 문자열 S에서, 어떤 부분구간을 flip한다는 것은, 그 구간의 부분문자열의 문자를 0을 1로, 1을 0으로 바꾼 다는 것을 의미합니다. 길이 K이상의 구간만을 flip하여 모든 문자를 0으로 만들 수 있다고 할 때, 가능한 K의 최댓값을 구하시오. (동시에 K는 N이하)
풀이: [1, X] 구간을 flip하고 [1, X+1] 구간을 flip하면 X+1번째 문자만 flip할 수 있습니다. 즉, X가 K이상일 경우에는, 숫자를 하나씩 flip하는게 마찬가지라는 것 입니다. 그래서 왼쪽에서 세어서 K+1번째 이후 문자의 상태는 모두를 0으로 바꿀때 상관이 없습니다. 오른쪽에서도 마찬가지의 논리가 성립합니다.
그래서 왼쪽에서 세어도, 오른쪽에서 세어도 K+1번째 이내인 수들에 대하여, 이 문자들이 모두 같은지 (같으면 전체를 flip할 수 있습니다.)를 판단해 주면 됩니다. 다른 경우에는, 이 문자들은 길이 K의 구간을 어떻게 잡아도 모두를 한번에 뒤집을 수 밖에 없기 때문에, 전부를 0으로 만드는게 불가능 합니다.
이런 K를 문자열의 가운데 부터 시작해서 같은 구간이 어디까지를 세어 줄 경우에 O(|S|)의 시간복잡도로 풀 수 있습니다.