백준 9819번: Color Change of Go Game Pieces

https://www.acmicpc.net/problem/9819

9819번: Color Change of Go Game Pieces

---

단순히 문제를 그대로 시뮬레이션 하는 것으로 풀리는 문제이지만, $k$가 충분히 클 때 복잡도를 떨어트릴만한 방법으로 exponentiation by squaring이 있어 이 문제를 포스팅하게 되었습니다.

 

우선 문제를 읽어보면, white와 black을 각각 1과 0, 또는 0과 1로 나타냈을 때 consecutive한 두 piece를 xor한 것이 그 두 piece 사이에 놓일 새로운 piece가 됩니다. 예시를 보면 이해가 쉬울 것입니다.

 

그런데 white와 black을 1과 0으로 나타내면, 이제부터 piece들의 상태를 $n$비트의 정수 $X$로 깔끔하게 표현할 수 있습니다. ($n \leq 128$)

 

$X$에서 한 번 transition을 거쳐 나온 상태가 $X'$일 때, $X$의 $j^{th}$ bit을 $X[j]$라고 하면, 다음이 성립합니다.

$$X'[j] = X[j] \oplus X[j-1] \;\; (1 \leq j \leq n-1)$$

$$X'[0] = X[0] \oplus X[n-1]$$

그러면 테스트케이스 당 $O(k)$ 솔루션은 다음과 같게 나옵니다.

$$X' \; \oplus = \left ( X < < 1 \right ) | \left ( X > > (n-1) \right )$$

그런데.. 위 식의 정당성과 별개로 C/C++은 128-bit integer 관련 이슈가 구현 난이도를 증가시킵니다. 가장 쉬운 방법은 위에서 말한 각 비트에 대한 점화식을 쓰는 것으로, 테스트케이스당 $O(nk)$ 복잡도에 약 8ms가 나옵니다. (제출번호 56743460)

 

128-bit integer을 쓴다면 0ms에 통과시킬 수 있지만, 다음을 신경써야 합니다. (제출번호 56853400)

1. left shift 결과를 truncate해주기 위해 $n$ 비트의 mask가 필요합니다.
2. 왜인지는 잘 모르겠으나 unsigned type을 써야 WA를 피할 수 있습니다.

---

$n,k$가 충분히 작아서, 테스트케이스 당 $O(nk)$도 훌륭한 복잡도이고, 점화식은 cache hit 면에서도 좋은 편이지만 $k$가 충분히 큰 경우를 생각할 수 있습니다.

 

다행히 이 문제에서 요구하는 연산은 exclusive-or이고, 이는 $\mathbb{Z}/2\mathbb{Z}$ 상에서의 덧셈으로 대체될 수 있음이 알려져있습니다.

 

그런 점에서 위 점화식을 살짝 다음처럼 바꿔줄 수 있습니다.

$$\begin{bmatrix} X'[0] \\ X'[1] \\ X'[2] \\ X'[3] \\ \vdots \\ X'[n-1] \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & \cdots & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & \cdots & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & \cdots & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots &\vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} X[0] \\ X[1] \\ X[2] \\ X[3] \\ \vdots \\ X[n-1] \end{bmatrix}$$

이제 테스트케이스당 $O(n^{3}\log k)$ 인데, 행렬 거듭제곱치고는 $n$이 큰 편이라 상수 커팅을 거쳐도 300ms 정도가 나왔습니다.

 

한편, 위 점화식을 나이브하게 그대로 쓰면 WA를 받는데, $n=1$의 엣지 케이스가 고려가 안 됐기 때문입니다. $n=1$일 때의 답은 고정되어 있으니 그 부분만 따로 처리해주면 되겠습니다. 제 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 2

typedef struct {
	unsigned int array[128][128];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size);
Matrix matrix_power_modular (Matrix A, int size, long long P);

int main() {
	while(1) {
        int n, m, k;
		scanf("%d,%d,%d", &n, &m, &k);
		if (n == -1) break;
		
		if (n == 1) {
			printf("%d,%d,%d: 0\n", n, m, k);
			continue;
		}
		
		Matrix X = {{{}}};
		for (int i = 0; i < m; i++) {
			X.array[i][0] = 1;
		}
		
		Matrix Y = {{{}}};
		Y.array[0][0] = Y.array[0][n-1] = 1;
		for (int i = 1; i < n; i++) {
			Y.array[i][i] = Y.array[i][i-1] = 1;
		}
		Y = matrix_power_modular(Y, n, k);
		X = matrix_multiply_modular(Y, X, n);
        
		int count = 0;
		for (int i = 0; i < n; i++) {
			count += X.array[i][0];
		}
		printf("%d,%d,%d: %d\n", n, m, k, count);
	}
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size) {
	Matrix result = {{{}}};
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			for (int k = 0; k < size; k++) {
				result.array[i][j] += A.array[i][k] * B.array[k][j];
			}
			result.array[i][j] %= mod;
		}
	}
    return result;
}

Matrix matrix_power_modular (Matrix A, int size, long long P) {
	Matrix result = {{{}}};
	for (int i = 0; i < size; i++) {
        result.array[i][i] = 1;
    }
	while (P) {
		if (P % 2) {
			result = matrix_multiply_modular(result, A, size);
		}
		A = matrix_multiply_modular(A, A, size);
		P /= 2;
	}
	return result;
}

(C11, 304ms, 1568KB, 제출번호 56801377)

---

위 코드에서 matrix multiplication 부분을 보면, $result[i][j]$에 1이 짝수 번 더해지면 0, 홀수 번 더해지면 1이 할당된다는 걸 알 수 있습니다. Parity는 xor을 통해 쉽게 파악할 수 있는 정보입니다. 특히, $result[i][j]$의 초기값은 0이고, 0과 xor한 값은 자기 자신이므로, matrix multiplication을 다음과 같이 조정할 수 있습니다.

Matrix operation (Matrix A, Matrix B, int size) {
	Matrix result = {{{}}};
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			for (int k = 0; k < size; k++) {
				result.array[i][j] ^= A.array[i][k] & B.array[k][j];
			}
		}
	}
    return result;
}

(272ms, 제출번호 56804811)

 

여기서 분기를 하나 파서 bitwise operation 횟수를 $O(popcount(A[i]))$로 떨구고, row-major 방식으로 array에 접근하도록 하면 다음과 같게 됩니다.

Matrix operation (Matrix A, Matrix B, int size) {
	Matrix result = {{{}}};
	for (int i = 0; i < size; i++) {
		for (int k = 0; k < size; k++) {
            if (A.array[i][k]) {
                for (int j = 0; j < size; j++) {
				    result.array[i][j] ^= B.array[k][j];
			    }
            }
		}
	}
    return result;
}

 

놀랍게도, 이러한 최종 조정끝에 행렬 거듭제곱의 방법론으로도 12ms를 달성할 수 있었습니다! (제출번호 56804844)

 

0ms까지 줄이긴 어려웠지만, 이정도면 테스트케이스가 더 많아지거나 $n,k$가 더 커져도 나름대로 대응할 수 있을 것 같습니다.