혜아의 아무말

문제: Nim 게임을 하는데, i번째 무더기에는 처음에 A_i개의 돌이 있고, i번째 무더기에 X개의 돌이 있을 때 최소 1개에서 최대 X/K_i (나머지는 버림)개 사이의 갯수에 돌만 가져갈 수 있습니다. 서로 번갈아가면서 하나의 무더기에서 몇개의 돌을 번갈아가면서 가져가고, 더 이상 돌을 가져갈 수 없는 사람이 진다고 했을 때, 첫째 사람이 이기는지, 둘째 사람이 이기는지를 구하시오.

풀이: 이 문제는 그냥 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를 만들어 보면 다음과 같은 표가 나옵니다.

  이 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)) 가 됩니다.

코드: https://atcoder.jp/contests/arc091/submissions/3851754

문제: 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|)의 시간복잡도로 풀 수 있습니다.

코드: https://atcoder.jp/contests/arc088/submissions/3851964

문제: 두 정수의 쌍 (a, b) 중에서, 1 ≤ a, b ≤ N 이면서, a를 b로 나눈 나머지가 K 이상인 것의 갯수를 세시오.

풀이: mod를 규칙적으로 보기 위해서는 b가 고정되어있으면 편하기 때문에, b를 고정시켜 놓습니다. b를 고정시킨 경우에는 어떤 수를 b로 나눈 나머지는 0, 1, 2, 3, ..., b-1 까지 갔다가, 다시 0부터 시작해서 1씩 증가하고, b-1 다음엔 0으로 돌아온다는 사실을 알 수 있습니다. 그래서 이렇게 돌아가는 수열 중에서 K 이상인 것의 갯수를 세는 것은, 반복되는 부분인 0, 1, 2, 3, ..., b-1이 몇번 반복 되는가와, 가장 마지막에 어떤식으로 수열이 끝나는지를 알면 알 수 있습니다. 자세한 수식은 코드의 수식을 보면 알 수 있습니다.

코드: https://atcoder.jp/contests/arc091/submissions/3832755

문제: 길이 N의 두 수열 a와 b가 주어진다. 모든 가능한 i와 j에 대해서 a_i+b_j의 합 N²개를 모두 XOR 한 값을 구하시오.

풀이: 모든 합을 구해서 XOR하는것은 구하기 때문에, XOR을 구할때 비트별로 볼 것 입니다. 우리가 어떤 특정한 2^B 에 해당하는 비트를 볼 때, 그 위에 있는 비트는 영향을 주지 않습니다. 중요한 것은 우리가 구하려는 비트(2^B)에 있는 값과, 그보다 하위 비트(작은 두 수를 더해서 2^B의 비트에 영향을 줄 수 있음)에 있는 값 입니다. 한 비트에 대해서 XOR은 1이 홀수개 있는지 짝수개 있는지 묻는 연산이기 때문에, 우리는 결국에는 해당하는 비트의 1의 홀짝성을 알려주면 됩니다. 즉, 이 비트에 영향을 홀수번 주었나, 짝수번 주었나를 묻는 문제입니다.

  일단 우리가 구하려는 비트 부터 살펴봅시다. 한 원소의 구하려는 비트가 1이라는 것은, 합 N개의 비트에 영향을 주었다는 의미입니다. 그래서 우리는 수열에 해당하는 비트의 원소가 몇개 있는지를 살펴보면 됩니다. 이제 우리가 구하려는 비트에 영향을 끼치는 갯수는 구했습니다.

  이 후에는, 우리가 구하려는 비트보다 하위 비트에 영향을 주는 갯수만 세면 됩니다.

그래서 우리는 이 문제를 비트마다 구하는 문제로 바꾸면, 각 수열의 원소는 2^B 보다 작고, 2^B에 해당하는 비트가 0인지 1인지를 구하는 문제가 됩니다. 2^B에 해당하는 비트가 0인지 1인지 구하는 문제이지만, 어떤 수열의 두 원소의 합은 2^B의 두배를 넘지 못하기 때문에, 결국 합해서 2^B보다 큰 합의 갯수를 세는 문제로 바뀝니다. 이 문제는 sliding window를 사용하거나, 아니면 binary search를 사용해서 간단하게 구할 수 있습니다. 어떤 한 원소가 x이면, N-x보다 크거나 같은 수의 갯수를 std::lower_bound 등을 이용해 간단하게 세어 줄 수 있습니다. 제 구현은 후자를 사용했고 코드는 다음과 같습니다.

코드: https://atcoder.jp/contests/arc092/submissions/3832874

문제: A와 B가 주어졌을 때, 흰색 connected component의 갯수가 A개, 검정색 connected component의 갯수가 B개인 격자를 아무거나 찾아서 출력하시오.

풀이: 이것은 저의 풀이고, 다양한 풀이가 존재할 수 있습니다.

  A가 1인 경우를 풀려고 해 봅시다. 일단 B가 0이면, 흰색으로 전체를 덮으면 됩니다. 여기서 B가 매우 크다고 해 봅시다. 그러면 흰색 component에 검정색 component 여러개를 끼워넣는 방법이 되어야 합니다. 그래서 우리는 흰색 component에 검정색 component를 서로 영향을 주지 않게 흰색끼리 연결되어있는 상태로 추가할 수 있습니다. 마치 수박에 있는 수박씨 처럼 흰색에다가 검정색으로 점을 서로 띄어서 찍어주면 됩니다. 이럴 경우에는 A가 1인 경우를 풀 수 있습니다. B를 추가하는게 점을 찍는것 입니다.

  마찬가지로, 하얀색을 한 칸 추가할 수 있는 환경을 만드려면, 검정색으로 전체를 덮으면 됩니다.

  저는 하얀색과 검정색을 반 반 나눠서 칠한 후 (A = B = 1),  검정색과 하얀색으로 점을 B-1, A-1개 각각 찍는데 서로 최소 2씩 거리가 나게 찍었습니다. 이렇게 찍은 경우에는 하얀색도 검정색도 배경은 연결되어 있다는 것을 알 수 있습니다.

  이 문제는 다양한 풀이가 존재하고, 우리가 만들어야하는 격자의 크기가 작을 경우에 만들 수 있는가? 를 물어보는 문제도 재밌을 것 같습니다.

코드: https://atcoder.jp/contests/arc093/submissions/3832898