2024년 3-5월 알고리즘 문제풀이

일종의 Coupon Collector’s Problem 변형 문제입니다.

1부터 3까지의 카드가 $a, b, c$ 장만큼씩 있고, $a + b + c = M$이라고 할 때, 두 장을 뽑는 경우는 다음의 경우들이 있습니다.

• (1, 1), (2, 2), (3, 3) 을 뽑는 경우: $a(a - 1) + b(b - 1) + c(c - 1)$ 가지 경우의 수가 있습니다.
• (1, 2), (2, 3), (3, 1) 을 뽑는 경우 (또는 그 반대 순서): $2(ab + bc + ca)$ 가지가 경우의 수가 있습니다.

종합하여 $a^2 + b^2 + c^2 + 2(ab + bc + ca) - M = (a + b + c)^2 - M = M(M - 1)$ 가지 경우를 이루게 됩니다.

이때, 전자는 성공 했지만, 후자는 더 뽑아야 합니다. $k$장을 뽑았을 때 실패할 확률을 $p_k$라고 한다면, 구하고자 하는 답은 성공할 때까지 필요한 반복의 기댓값 이므로, $1 + (\sum_{i = 1}^{\infty} p_i)$ 가 우리가 원하는 답이 됩니다. (실패한다는건 다음 실행을 해야 한다는 의미가 되므로) 여기서, $n + 1$ 장을 뽑으면 반드시 성공하므로, 우리는 $\infty$가 아닌 $n$까지만 더하면 됩니다.

각각의 $p_i$를 구하기 위해, 위 예시로 돌아가 보겠습니다. 일반화해서, 2장을 뽑아서 실패할 확률을 \(p_2 = \frac{1}{M(M - 1)}\sum_{i \neq j} x_i x_j = \frac{2}{M(M - 1)}\sum_{i < j} x_i x_j\) 로 쓸 수 있습니다. 비슷한 방법으로 $k$ 장을 뽑았을 때 실패하는 확률을 생각해 보면, 전체 경우의 수가 $M(M-1)\dots(M-K+1)$ 가지고, 서로 겹치지 않게 무엇을 뽑을지 정하고 나면 경우의 수는 그냥 곱해지기 때문에, \(p_k = \frac{k!}{M(M-1)\dots(M-k+1)}\sum_{1 \leq j_1 < j_2 < \dots < j_k \leq n} x_{j_1} x_{j_2} \dots x_{j_k}\) 이렇게 구해다는 것을 알 수 있습니다.

위 $p_k$ 항에서, 앞부분은 미리 팩토리얼값을 전처리해두면 되기 때문에 구하기 어렵지 않습니다. 뒷부분은 하나의 $k$를 구하기 위해 $\binom{n}{k}$ 시간이 들기 때문에 약간의 생각을 더 해야 합니다. 뒷부분의 합이 근과 계수의 관계 에서 얻어지는 항과 비슷함을 관찰할 수 있습니다. 구체적으로, \(S_k = \sum_{1 \leq j_1 < j_2 < \dots < j_k \leq n} x_{j_1} x_{j_2} \dots x_{j_k}\) 에 대해, 다음이 성립함을 알고 있습니다. ($S_0 = 1$로 생각합니다) \((t + x_1)(t + x_2) \dots (t + x_n) = \sum_{i = 0}^{n}t^n S_{n - i}\) 따라서, 좌변의 다항식을 전개하여 그 계수를 알아낼 수 있다면 $S_1$부터 $S_n$까지의 모든 $S$를 구할 수 있습니다.

그러나 $d$차 다항식을 곱셈하는 것은 그냥 곱셈하면 $d^2$ 시간이 걸리고, FFT를 이용하더라도 $d \log d$ 시간이 걸립니다. 구체적으로, $a$차와 $b$차 다항식을 곱하면 FFT를 사용하더라도 $(a + b) \log (a + b)$ 시간이 걸리므로, 앞에서부터 순서대로 곱한다면 전체 시간 복잡도는 $n^2 \log n$ 시간이 걸리게 됩니다.

이러한 형태의 다항식을 빠르게 전개하기 위해서는 FFT를 이용하되, 이진 트리 형태로 곱셈해 나가는 방법을 쓸 수 있습니다. 다항식들을 이진 트리의 리프노드에 배치했다고 생각하고, 분할정복식으로 첫번째부터 $n / 2$ 번째까지의 다항식들의 곱과 $n / 2 + 1$ 부터 $n$번째까지의 다항식들의 곱을 따로 구하여 FFT로 합치는 방법입니다. 이렇게 하면, $n$개의 $t + x$ 형태 다항식을 곱하기 위해 \(T(n) = 2T(n / 2) + O(n \log n)\) 시간이 들기 때문에, 이를 마스터 정리로 전개하면 $O(n \log^2 n)$ 시간이 됩니다.

따라서, $O(n \log^2 n)$ 시간에 모든 $S_i$ 들을 구하고, 이걸로 $p_i$들을 구하면 전체 문제를 해결할 수 있습니다.

현의 개수가 최대 50개임을 생각하고, 주어진 각 점은 많아야 한 현의 끝점이 될 수 있다는 것을 생각하면, 반드시 선분 $(i, i+1)$이 주어진 현이 아닌 $i$를 생각할 수 있습니다. 그 점에서 원을 끊어서, 선형으로 문제를 변형할 수 있습니다.

일반성을 잃지 않고, 끊은 지점이 $(N, 1)$ 사이라고 하겠습니다. 현의 끝점이 아닌 점들은 필요 없으므로 잊어버리고, 좌표압축을 수행합니다.

• $D(i, j)$ 를 $(i, j)$ 번 점까지만 보면서 고를 수 있는 최대 현의 개수라고 하고, 이를 DP를 이용하여 찾습니다.
• $(i, j)$가 주어진 현이면 $c = 1$, 아니면 $0$이라고 생각합니다.
• 임의의 $i \leq k \leq j$ 인 $k$에 대해, $D(i, j) \geq D(i, k) + D(k, j) + c$ 가 성립합니다. 어떤 $k$에서 끊어서 그 왼쪽과 오른쪽 구간을 따로 계산한 후, $(i, j)$ 현을 끼워넣을 수 있기 때문입니다.
• 선택한 현들이 겹칠 수 없기 때문에, $D(i, j)$ 들은 반드시 저러한 $k$에 의해 정해져야 하므로, 실제로는 $D(i, j) \geq D(i, k) + D(k, j) + c$ 로 계산할 수 있습니다.
• 잘 알려진 행렬 곱셈 순서 와 같은 느낌의 DP로, $O(N^3)$ 시간에 해결할 수 있습니다.