ICPC WF 연습 (2/6)

Chess Puzzle

2분 30초 AC.

전성기 때 나라면 1분 안에 풀었을 텐데... 열심히 해야지.

Squared Word

길이 $N$의 문자열 $S$가 주어진다. 제곱 문자열 $L^2$가 $S$에 포함될 때, 문자열 $L$의 최대 길이를 구하는 문제이다.

$L^2$가 $S$에 포함된다는 것은, 어떤 $1 \le i < N$가 존재하여, $S[1 \cdots i]$와 $S[i+1 \cdots N]$ 모두에 각각 $L$가 포함됨과 동치이다.

따라서, 모든 $i$에 대하여, $S[1 \cdots i]$와 $S[i+1 \cdots N]$의 LCS를 구한 후, 이 값의 최댓값이 문제의 답이 된다.

나는 $O(N)$번 LCS를 계산하는 과정을 $O\left( N^2 \right)$로 최적화하려고 고민을 아주 많이 했었다... tlwpdus도 이렇게 풀었고...

그런데, bitset을 이용하면, LCS를 $O\left( \frac{ N^2 }{32} \right)$에 해결할 수 있다고 한다. Naive 알고리즘이 $O\left( \frac{N^3}{32} \right)$인데 $O\left( N^2 \right)$ tlwpdus 풀이랑 시간이 똑같다. 상당히 큰 충격.

응급센터

대충 뚝딱뚝딱 선형에 풀리는 것 같은데 증명을 못 하겠다.

Cliquers Strike Back

두 자연수 $N$, $M$가 주어진다. Labeling이 되어 있는 $N$개의 정점을 몇 개의 그룹으로 나누는 경우의 수를 '지수'로 가지고, 밑이 $M$인 수를 $P := 10^9 - 401$로 나눈 나머지를 구하는 문제이다.

이 문제는 옛날 폴란드 문제이다. 풀이를 만들고 어떻게든 끼워넣어서 문제를 만들었겠구나 생각하면서 문제를 풀었다.

먼저, $P$는 소수이다. $N$-Labeling 경우의 수가 $D_N$라고 하자. 우리는 $M^{D_N} \mod P$를 구해야 한다. 페르마 소정리에 따라, $D_N \mod P-1$을 알아내면 된다.

이제, 가장 어려운 접근을 해야 한다. $P-1$의 소인수분해를 시도하자. $P-1 =2 \times 13 \times 5281 \times 7283$. 소인수가 모두 만 이하로 적당히 작고, 네 개의 소인수가 모두 다르다는 점을 주목해야 한다. 네 개의 소인수를 $Q_i$라고 하자. $D_N \mod Q_i$의 값을 모두 알아낸 후, 중국인의 나머지 정리를 통해 원래의 값을 복원하자.

$D_N$에 대한 점화식은 쉽게 세울 수 있다. $D_0 = 1$, $D_{N+1} = \sum_{k=0}^{N} \binom{N}{k} D_k$. 어디서 많이 본 형태가 나온다. $f(x) := e^{e^{x-1}}$로 정의한다면, $f(x) = \sum_{k = 0}^{\infty} \frac{x^k}{k !}$임을 알 수 있다. 즉, 열심히 잘 하면, $D_N$의 값을 $O( N \lg N )$에 알아낼 수 있다.

이제, 적당히 작은 소수 $Q$에 대하여, $D_N \mod Q$의 값을 효율적으로 계산하는 방법을 알아내보자. 점화식을 열심히 관찰하면, $D_{N + Q} \equiv D_N + D_{N+1} \mod Q$임을 알 수 있다. 이제, 아주 열심히 식 전개를 하면, $D_N$의 값을 $D_0, \cdots, D_{Q-1}$의 선형 결합으로 표현할 수 있다. 이 과정의 시간 복잡도는 $O\left( \frac{ Q \lg_Q^2 N }{ 2 } \right)$이다.

이 긴 관찰을 모두 해냈다면, TL가 1초인 문제를 960ms의 실행 시간으로 해결할 수 있다. 역시 폴란드..! 2시간 40분 AC.

Glorious Brilliance

정점 $N$개, 간선 $M$개인 그래프가 주어진다. 각 정점의 색칠 여부가 주어진다. 하나의 간선을 선택하면, 그 간선 양 끝의 정점을 서로 바꿀 수 있다. 같은 색을 가지는 정점이 서로 이웃하지 않도록 하기 위하여, 필요한 '간선 Swap' 연산의 최소 횟수를 구하고, 그러한 방법을 출력하는 문제이다.

그래프가 bipartite하지 않는다면, 답은 없다. 그래프가 $V_1 - V_2$ bipartite graph라고 하자. 색칠된 정점을 모두 $V_1$로 옮기는 문제로 바꿀 수 있다.

$V_1$의 각 정점에서 $V_2$의 각 정점으로 가는 최단 경로의 길이를 행렬로 나타내자. 이 행렬에서 Hungarian algorithm을 돌리면 문제를 해결할 수 있다. 역추적도 힘들지만 된다.

하지만, 시간 복잡도가 $O\left( N^3 \right)$이라서, 시간 초과 판정을 받을 것 같다. 입력의 크기 제한이 있고, 이 크기는 $O\left( N + M \right)$기 때문에, $O \left( NM \right)$으로 풀어야 하는 것 같은데, 잘 모르겠다.