본문 바로가기

Codeforces

Codeforces Round #588 (Div. 1)

https://codeforces.com/contest/1229

https://codeforces.com/blog/entry/70008 (Editorial)

Dasha Code Championship 대회의 open contest이었다. A, B, C, D, E1, E2, F 중 A B C 세 문제 밖에 못 풀었는데도 레이팅이 오른 대회였다. 초반에 서버가 죽는 일이 벌어졌는데도 rated로 진행되었다.

 

 

A. Marcin and Training Camp

다른 A번 문제들에 비하면 어려운 편이었다고 생각한다.

$b_i$가 양수이기 때문에 가능한 많은 수를 넣는 것이 좋다. 따라서 $a_i$가 가장 큰 것부터 그리디하게 보면서, 답에 포함하는 것이 가능하다면 넣고, 그렇지 않다면 넘어가면 된다.

 

 

B. Kamil and Making a Stream

트리에서 gcd를 구하는 문제이다. 트리의 어떤 정점 u와 그 조상 v에 대해, v~u 경로의 수들을 모두 gcd한 결과를 구하여 그 합을 구하는 문제이다. 구해야 하는 수는 총 $N^2$개 이지만, 겹치는 수들이 많기 때문에 수의 종류는 $NlogN$이다. 따라서 u를 dfs 순서로 보며, par(u)에서의 결과를 (gcd결과, 그 수가 나온 횟수)로 가지고 있으면 $O(Nlog^2N)$에 구할 수 있다.

 

 

C. Konrad and Company Evaluation

나는 시간복잡도를 증명하지 않고 풀었는데, $O(N^{3/2})$으로 풀 수 있다. 그래프의 정점들을 세로 한 줄로 정렬해놓았을 때, 모든 정점 v에 대해 (v와 연결돼있으며 v보다 위에 있는 정점의 수)*(v와 연결돼있으며 v보다 위에 있는 정점의 수)를 구하면 된다. 쿼리로는 어떤 정점 v를 가장 위로 올리는 연산이 들어온다. 이 때 갱신되는 정점은 v와, v와 연결돼있으며 v보다 위에 있었던 정점들이다. 이러한 정점들의 개수는 총 $O(N^{3/2})$이기 때문에 시간 안에 동작한다.

증명) 쿼리를 길이 $\sqrt{Q}$의 구간으로 끊어서 생각하자. 각 구간에서, 어떠한 정점이 처음 등장한 경우와 이미 나왔었던 경우를 나누어 생각하자. 처음 등장한 경우, 갱신되는 정점의 개수의 합은 $O(M)$이다. 이미 나왔을 경우, 갱신되는 정점은 그 전에 나온 후 갱신 된 정점들의 개수보다 작다. 따라서 $O(\sqrt{Q})$이다. 총 시간복잡도는 $O((M+Q) \sqrt{Q})$이다.

 

 

D. Wojtek and Card Tricks

{1, 2, 3, 4, 5, 6}의 순열을 섞는 연산이 N개($P_1, P_2, ..., P_N$) 주어졌을 때, $P_l, P_{l+1}, ..., P_r$만을 이용하여 만들 수 있는 permutation의 개수를 구하는 문제이다.

1. [l, r]구간에서 의미 있는 P는 6!개이다.

2. r을 정한 후 l을 왼쪽으로 움직일 때, 가능한 permutation의 개수가 늘어나는 횟수는 $log(6!)$번이다.

2 증명) 가능한 permuation들의 집합을 생각하자. 새로운 permuation이 가능할 경우, 가능한 permutation의 집합의 크기는 2배 이상으로 늘어난다. 이는 라그랑주 정리를 이용해 증명할 수 있다고 한다. 

 

따라서 어떤 r에 대해 의미 있는 P들을 구한 후 r을 오른쪽으로 움직이며 구하면 된다.

 

 

E1. Marek and Matching (easy version)

크기가 2N인 이분 그래프가 있고, 각 간선이 생길 확률이 주어져있다. 이때, 완전매칭이 가능할 확률을 구하는 문제이다. ($1\leq N\leq 6$)

이 그래프의 정점들을 $l_1, ...,  l_6, r_1, ..., r_6$이라 부르자. 간선들을 $l_1, ..., l_6, r_1, r_2, r_3$ 사이를 연결하는 것과 $l_1, ..., l_6, r_4, r_5, r_6$ 사이를 연결하는 것으로 나누자. 각 그룹에 속한 간선의 개수는 18개이다. $2^{18}$개의 경우에 대해, $r_1, r_2, r_3$(또는 $r_4, r_5, r_6$)에서 어떠한 l들로 연결될 수 있는지 구하자. 즉, $\binom{6}{3}=20$가지 경우 중 어떠한 것이 가능한지 구한다. 이를 이용해 $2^{20}$ 크기의 bitmask 배열에 대해, 각 경우(20가지 경우 중 어떠한 것이 가능한지)의 확률을 구한다. 이제 두 그룹에 대한 배열을 합치면 되는데, 이는 SOS dp를 활용해 가능하다. 총 시간복잡도는 $O(2^{N^2/2}poly(N)+2^{\binom{N}{N/2}}\binom{N}{N/2})$이다.

* SOS dp: Sum over Subsets. https://gina65.tistory.com/6 참고.

 

 

E2. Marek and Matching (hard version)

$1\leq N \leq 7$이기 때문에 E1과 같은 방법으로 풀려고 하면 $2^{\binom{7}{3}}\simeq 3\times 10^{10}$에서 시간초과가 난다. 이번에는 정점을 1개씩 추가하는 방법을 생각해보자. $r_1, ..., r_k$를 $l_1, ..., l_7$ 중$k$개에 매칭하는 경우를 생각하자. 이 $\binom{7}{k}$가지 경우 중 가능한 것을 체크하자. 이러면 $2^{\binom{N}{k}}$가지 경우가 나올 것 같지만, 그렇지 않다. 예를 들어서 $k=2$일 때 {$l_1, l_2$}와 {$l_3, l_4$}에 매칭하는 것이 가능하다면, {$l_1, l_3$} 또는 {$l_1, l_4$}에 매칭하는 것이 가능해진다. 이처럼 $\binom{N}{k}$가지 상태들이 독립적이지 않기 때문에, 실제 가능한 경우는 30000가지 정도이다. 따라서 $O(N\times 30000\times 2^N)$의 시간복잡도에 해결할 수 있다.

 

 

F. Mateusz and Escape Room

원형으로 저울이 $N$개가 배치되어 있고, $i$번째 저울 위에는 동전이 $A_i$개 있다. 인접한 저울 사이로 동전들을 이동시키는 시행을 할 수 있다. 이 때 $i$번째 저울 위에 $L_i$개 이상 $R_i$개 이하의 동전이 놓이도록 하기 위해서 필요한 시행 횟수의 최솟값을 구하는 문제다. $\sum L_i \leq \sum A_i \leq \sum R_i$이기 때문에 이러한 상태를 만드는 것이 가능하다.

$i$번째 저울에서 $i+1$번째 저울로 이동하는 동전의 개수를 $x_i$라 하자. $L_i \leq A_i + x_{i - 1} - x_i \leq R_i$을 만족하는 $\{ x_0, x_1, ..., x_{N - 1}\}$($x_i \in \mathbf{Z}$)을 잘 골라서 $|x_0| + |x_1| + ... + |x_{N - 1}|$을 최소화해야 한다.

 

$x_0$을 고정시키고 생각해보자. $dp(i, x)$를 $x_1, ..., x_i$를 고려하고 $x_i=x$일 때 필요한 최소 비용이라 하자. 그러면 점화식을 아래와 같다. $$dp(i, x) = \min_{x-A_i+L_i \leq y \leq x-A_i+R_i} (dp(i-1, y)+|x|), dp(0, x_0)=0, dp(0, t)=\infty$$

$dp(N-1, x_0)$이 구하고자 하는 답이다. 위 연산은 함수를 평행이동하거나 두 함수를 더하는 것이므로 한 연산당 $O(logN)$에 할 수 있다. 구체적으로는, 함수의 최솟값을 기준으로 왼쪽과 오른쪽으로 나눈 후 함수의 기울기가 바뀌는 점들을 priority queue로 관리하면 된다. 그러면 매 시행마다 왼쪽 함수는 $A_i - R_i$만큼 이동하고, 오른쪽 함수는 $A_i - L_i$만큼 이동한다. 그 후 $y=|x|$ 함수를 더해주면 된다. 

 

이제 특정 $x_0$에 대한 답을 $O(NlogN)$에 구할 수 있다. $x_0$에 대한 답의 그래프는 아래와 같은 성질이 있다.

1. $x_i$를 정수가 아니라 실수 범위로 확장해도 답은 같다.

증명) 이 문제를 flow로 환원하면 MCMF가 되기 때문에 성립한다.

2. $(a_0, a_1, ..., a_{N-1}), (b_0, b_1, ..., b_{N-1})$이 답(최솟값)에 해당하는 $(x_0, x_1, ..., x_{N-1})$이라면 $(\frac{a_0+b_0}{2}, \frac{a_1+b_1}{2}, ..., \frac{a_{N-1}+b_{N-1}}{2})$도 답에 해당된다.

증명) $L_i \leq A_i+a_{i-1}-a_i \leq R_i, L_i \leq A_i+b_{i-1}-b_i \leq R_i \Rightarrow L_i \leq A_i+\frac{a_{i-1}+b_{i-1}}{2}-\frac{a_i+b_i}{2} \leq R_i$ ($[L_i, R_i]$ 조건 만족)

        $|\frac{a_i+b_i}{2}| \leq \frac{|a_i|+|b_i|}{2}$ (최솟값 만족)

성질 2에 의해 아래 Lemma가 성립한다.

Lemma. $x_0$에 대한 답의 그래프는 convex하다.

따라서 $x_0$에 대한 이분탐색을 진행하면 $O(Nlog^2N)$으로 해결할 수 있다. 이분탐색은, 한 점에서의 기울기의 부호에 따라 최솟값이 어느쪽에 있을지 판별하는 방식으로 진행하면 된다.

 

나는 이분탐색을 할 때, $x_0$가 음수인 경우 구간을 잘못 나눠서 한참 해멨다. 음의 정수에서 나눗셈을 하면 내림이 아니라 올림이 된다는 점을 고려하지 않았기 때문이다.

'Codeforces' 카테고리의 다른 글

Codeforces Round #594 (Div. 1)  (0) 2019.10.28
Codeforces Global Round 5  (0) 2019.10.24
Codeforces Round #591 (Div. 1)  (0) 2019.10.18