2020.12.06 problem solving

NAC 2020 F. Hopscotch 50

간단한 DP 입니다. $dp[i][j]$ 를 $(i, j)$ 셀에 도착하는 최소 비용이라고 합시다. 만약 이 셀에 1이 적혀 있으면 답은 0입니다. 아니면, 이 셀보다 적힌 숫자가 1 작은 모든 셀 $(k, l)$ 이 이 셀로 들어오는 것이 가능한 후보가 됩니다. 모든 후보 중 $dp[k][l] + |k-i| +|l-j|$ 값의 최소를 취해주면 됩니다. 이대로 구현하면 시간 복잡도는 $O(N^4)$ 입니다.

Ptz Winter 2019 Day7 G. Permutant

주어진 순열이 2개 이상의 사이클을 포함하고 있다면, 답은 0이 됩니다. 주어진 순열이 “정확히 2개” 의 사이클을 포함하고 있을 때에 대해 증명하면, 두 사이클의 길이가 a / b라고 할 때, 행렬의 위쪽 a개 벡터의 합과 아래쪽 a개 벡터의 합이 동일하기 때문에 선형 독립이 아니라서 성립합니다. 2개 초과일 때의 증명은 생략합니다.

고로, 주어진 순열이 정확히 하나의 사이클로 이루어져 있다고 가정합시다. 열의 순서를 적당히 바꿔줌으로써 (이 과정에서 행렬식에 -1이 곱해질 수 있음에 유의) 행렬을 다음과 같이 아래 행이 위 행의 cyclic shift인 형태로 바꿔줄 수 있습니다.

$C = \begin{pmatrix} c_0 &c_1& \ldots& c_{n - 1} \newline c_{n - 1}& c_0 &\ldots &c_{n - 2} \newline \ldots & \ldots & \ldots & \ldots \newline c_1 & c_2 & \ldots & c_0 \end{pmatrix}$

행렬식은 모든 고윳값의 곱이 되니, 이 행렬의 고윳값을 구해봅시다. $C_{i, (i+1)\mod n} = 1$ 인, 다음과 같은 행렬을 정의합시다.

$C = \begin{pmatrix} 0 & 1& 0&\ldots& 0 \newline 0 & 0 &1 &\ldots &0 \newline \ldots & \ldots & \ldots & \ldots & \ldots \newline 0&0&0&\ldots&1 \newline 1&0&0&\ldots&0\end{pmatrix}$

정의에 의해 자명하게 $C = c_0I + c_1P + c_2P^2 + \ldots + c_{n- 1}P^{n-1}$ 입니다.

또한 $P$ 의 특성방정식은 $x^n - 1$ 이니, 고윳값은 $\omega^0, \omega^1, \ldots, \omega^{n-1}$ 이 됩니다. 만약 P의 고윳값이 $\omega^0, \omega^1, \ldots, \omega^{n-1}$ 이면, $c(x) = \sum_{i = 0}^{n - 1}{c_i x^i}$ 이라 할 때 $C$ 의 고윳값은 $c(\omega^0), c(\omega^1), \ldots, c(\omega^{n-1})$ 이 됩니다. 고로 답은 $\Phi_{i = 0}^{n - 1} c(\omega^i)$ 입니다. 이제 이것을 계산하면 되겠지만, roots of unity를 실제로 다룰 수 없다는 것이 문제입니다.

이것을 해결하기 위해 종결식(resultant) 라는 개념을 도입합니다. 먼저, $\omega^0, \omega^1, \ldots, \omega^{n-1}$ 을 근으로 가지는 다항식은 정의에 따라 $x^n - 1$ 입니다. $\lambda_1, \lambda_2, \ldots, \lambda_n$ 을 근으로 갖는 다항식 $A(x) = \sum_{i = 0}^n a_i x^i$ 와 $\mu_1, \mu_2, \ldots, \mu_m$ 을 근으로 갖는 다항식 $B(x) = \sum_{i = 0}^{m} b_i x^i$ 에 대해, 종결식 $R(A, B)$ 는

$R(A, B) = b_m^n\Pi A(\mu_i) = a_n^mb_m^n\Pi_{i \in [n], j \in [m]}(\phi_i - \mu_j) = (-1)^{mn}a_n^m\Pi B(\lambda_i)$

으로 정의됩니다. 여기서 우리가 구하는 것이 정확히 $R(c(x), x^n - 1)$ 임을 알 수 있습니다.

이제 $R(A, B)$ 를 계산해봅시다. 다음과 같은 성질이 있습니다.

• $R(B, A) = (-1)^{nm}R(A, B)$
• $R(A, B) = a_n^mb_m^n$ if $n = 0$ or $m = 0$
• $b_m = 1$ 일 때 임의의 다항식 $C$ 에 대해서 $R(A, B) = R(A - CB, B)$ ($B(\mu_i) = 0$)
• 같은 이유로 $R(A, B) = b_m^{deg(A) - deg(A - CB)}R(A - CB, B)$

이 결과가 놀라운 점은 재귀적이라는 것입니다. $C(x) = A(x) / B(x)$ 로 두면 이 식은 재귀적으로 최대차항을 하나씩 줄여나갑니다. 고로 유클리드 호제법과 비슷한 느낌으로 $O(n^2)$ 에 구현하실 수 있습니다.

Ptz Summer 2018 Day3 G. Gnutella Chessmaster

생성 함수에 대한 지식을 가정한다. 먼저 $O(n^2)$ 알고리즘을 유도하자.

첫 번째 관찰은 체스판을 흑백으로 칠했을 때 서로 다른 색의 칸에 있는 룩은 서로를 공격하지 못한다는 것이다. 흑백으로 판을 분리한 후 체스판을 45도 기울이면 각 색의 칸들이 일종의 격자를 이루기 때문에 대각선을 본다는 귀찮은 조건을 깔끔하게 바꿔줄 수 있다. 답을 찾을 때는, 흑색 셀에 $i$ 개의 룩을 넣는 생성함수와 백색 셀에 $j$ 개의 룩을 넣는 생성함수를 FFT로 곱해주면 된다.

이렇게 되면 다이아몬드 형태로 테두리가 쳐진 격자 모양이 된다. 행의 순서를 바꿔도 문제가 되지 않으니, 가진 셀이 많은 순서대로 행을 정렬하면 삼각형 모양으로 격자가 바뀐다. 이 상태에서 열의 순서도 동일하게 정렬해 주면 대략 직각삼각형과 비슷한 형태의 모양을 얻을 수 있다. 혹은, 오른쪽으로 갈 수록 막대의 높이가 늘어나는 히스토그램 (Young diagram) 이라고 생각해 줄 수도 있다. 이제부터는 이를 히스토그램이라고 보고, 각 막대의 높이 수열을 ${a_0, a_1, \ldots, a_{n-1}}$ ($a_1 \le a_2 \le \ldots \le a_n$) 으로 표현하자.

이제 여기에 $k$ 개의 원소를 넣는 것은, 왼쪽에서 오른쪽부터 원소를 채우는 식으로 가능하다. {$f_{i, j}$ 를, $i$ 번 행까지 고려했으며 지금까지 채운 원소가 $j$ 개인 경우의 수로 두면:

$f_{i, j} = f_{i-1, j} + f_{i-1, j-1} \times (a_i - j + 1)$

이며 $f_n$ 배열이 우리가 원하는 결과가 된다. $g_{i, j} = f_{i, i - j}$ 라고 두면,

$g_{i, j} = g_{i - 1, j - 1} + g_{i - 1, j} \times (a_i - (i - j))$

$g_i(x)$ 를 $g_i$ 의 생성 함수라고 하면,

$g_i(x) = x g_{i - 1}(x) + (a_i - i) g_{i - 1}(x) + x g^\prime_{i - 1}(x) $

$b_i = a_i - i $ 으로 두자.

$g_i(x) = x g_{i-1}(x) + b_i g_{i - 1}(x) + x g^\prime_{i - 1}(x)$

믿고 싶지 않겠지만 $\prime$ 은 미분 연산자가 맞다. 당연하게도 생성함수 역시 미분할 수 있다. 이제 생성함수에 대한 미분방정식을 유도했으니 풀어보자.

$g_i(x) e^{x} = x g_{i - 1}(x) e^{x} + x g^\prime_{i - 1}(x) e^{x} + b_i g_{i - 1}(x) e^{x}$

$= x(g_{i-1}(x) e^x)^\prime + b_i g_{i-1}(x) e^x$

$h_i(x) = g_i(x) e^{x}$ 라고 두면

$h_i(x) = xh^\prime_{i-1}(x) + b_i h_{i-1}(x)$

$h_{i, j} = h_{i - 1, j} b_i + h_{i - 1, j } j = h_{i - 1, j} (b_i + j)$

$h_{i, j} = h_{0, j} \Pi_{i = 0}^{n - 1} (b_i + j)$ 이라는 간단한 식을 얻을 수 있다. 그런데 $g_0(x) = 1$ 이니, $h_0(x) = e^x$ 이고, 고로 $h_{i, j} = \frac{1}{j!} \Pi_{i = 0}^{n - 1} (b_i + j)$ 이다.

$\Pi_{i = 0}^{n - 1} (b_i + j)$ 는 $P(x) = \Pi_{i = 0}^{n - 1} (b_i + x)$ 라는 다항식의 $P(0), P(1), \ldots, P(n)$ 값을 구하면 알 수 있다. 일반적으로 이는 분할 정복, FFT, Multipoint evaluation등을 조합해서 $O(n \log^2 n)$ 에 할 수 있지만, $b_i$ 가 거의 $0, 1, 2$ 로만 이루어졌다는 것을 관찰하면 단순 제곱으로 $O(n \log n)$ 에 해결할 수 있다 $h_i(x)$ 가 있으면 다시 $e^{-x}$ 를 FFT로 곱해서 $g_i(x)$ 를 얻을 수 있고, 문제가 $O(n\log n)$ 에 해결된다.