본문 바로가기

Codeforces

Codeforces Round #591 (Div. 1)

https://codeforces.com/contest/1240/

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

나는 낮에 버츄얼만 돌렸다. 본 대회는 DDOS 공격으로 인해 unrated 됐다. 나는 대부분의 사람들과 마찬가지로 ABCD를 풀었는데, 푸는데 시간이 오래 걸린 편이었다.

 

 

A. Save the Nature

$N$개의 티켓이 있다. $i$번 티켓은 $p_i$의 가격을 갖는다. $a$의 배수번째에 팔린 티켓 가격의 $x\%$와 $b$의 배수번째에 팔린 티켓 가격의 $y\%$은 환경운동을 위해 쓰일 것이다. 티켓들의 순서를 잘 정하여, 최소 개수의 티켓을 팔아서 $k$이상의 돈을 환경운동에 쓰고 싶다. 팔아야하는 티켓 개수의 최솟값은?

$x>y$라 하자. $t$개의 티켓을 팔 경우, 그 중 $t/lcm(a, b)$개는 $(x+y)\%$만큼을 환경운동에 쓰이고, $t/a-t/lcm(a, b)$개는 $x\%$만큼이 환경운동에 쓰이고, $t/b-t/lcm(a, b)$는 $y\%$만큼이 환경운동에 쓰인다. 따라서 가장 비싼 티켓들의 $(x+y)\%$, 그 다음으로 비싼 티켓들의 $x\%$, 그 다음으로 비싼 티켓들의 $y\%$를 환경운동에 쓰면 된다. 티켓들을 정렬한 후 prefix sum을 구하면 $O(NlogN)$으로 풀 수 있다.

 

 

B. Sequence Sorting

수열 $a_1, a_2, ..., a_n$이 있다. 특정 $x$에 대해 $a_i=x$인 모든 $a_i$들을 수열의 맨 끝으로 옮기는 연산을 할 수 있다. 또는 그러한 $a_i$들을 모두 수열의 맨 처음으로 옮기는 연산도 할 수 있다. 이 두 연산들만을 이용해 수열을 정렬하려고 할 때, 필요한 연산 횟수의 최솟값은?

우선 좌표 압축을 해서 $1, 2, ..., k$의 수가 쓰였다고 하자. $1, 2, ..., k$ 중 연산이 시행되지 않은 수 $a$와 $b$가 있다고 하자($a<b$). 그렇다면 $[a+1, b-1]$의 수들에도 연산이 시행되지 않았을 것이다. 따라서 $[1, A-1]$에는 앞으로 옮기는 연산을 시행하고, $[A, B]$에는 연산을 시행하지 않고, $[B+1, k]$에는 뒤로 옮기는 연산을 했을 것이다. $[A, B]$는 처음부터 정렬된 순서였어야 한다. 각 수가 나온 처음 위치와 마지막 위치를 기록해두면 $O(N)$에 풀 수 있다.

 

 

C. Paint the Tree

정점이 $N$개인 트리가 있다. 각 간선에는 가중치 $w_i$가 있다. 각 정점에 $k$개의 색깔을 칠할 것이고, 한 색깔은 2번까지만 쓰일 수 있다. 이 때, 한 에지의 양쪽 노드에 칠해진 색깔에 교집합이 공집합이 아니라면 그 에지를 saturated edge 라고 하자. saturated edge의 가중치의 합의 최댓값은?

saturated edge들을 고르자. 각 saturated edge에 대해, 그 에지의 양쪽 끝점에 쓰인 색 중에 겹치는 것이 있다. 그 색깔을 $c$라고 한다면, $c$는 다른 정점에서는 쓰이지 않는다. 따라서 saturated edge 1개는 색깔 1개를 차지한다. 한 정점에는 색깔이 $k$개가 있으므로 그 정점과 연결된 saturated edge도 $k$개 이하이다. 따라서 이 문제는 saturated edge를 최대한 많이 고르되, 한 정점에 연결된 saturated edge가 $k$개 이하가 되게 하는 문제가 된다. 이는 트리 dp로 풀 수 있다. 각 정점에 대해 그 서브트리를 칠할 때 얻을 수 있는 최대 가중치와, 서브트리와 부모 간선을 칠할 때 얻을 수 있는 최대 가중치를 알고 있으면 된다. 자식 간선들을 모두 선택하지 않을 수도 있고, 그 중에서 $k$개 또는 $k-1$개 이하를 고를 수도 있다. 자식 간선을 추가할 때 생기는 이득을 정렬하여 가장 큰 $k$개 또는 $k-1$개를 고르면 된다. 따라서 $O(NlogN)$으로 해결할 수 있다.

 

 

D. Stack Exterminable Arrays

길이 $M$의 수열 $\{a_0, a_1, ..., a_{M-1}\}$이 주어지면 스택에 다음과 같은 연산을 시행할 것이다. 스택은 처음에 비어있다. $i=0, ..., M-1$에 대해,
i) 스택이 비어있지 않고, 스택의 top과 $a_i$과 같음 : 스택에서 pop을 한다.
ii) 스택이 비어있거나, 스택의 top과 $a_i$가 다르다 : 스택에 $a_i$를 push한다.
연산을 완료한 후 스택이 비어있다면, 그 수열을 Stack Exterminable Array라고 할 것이다. 길이 $N$의 수열 $\{A_0, A_1, ..., A_{N-1}\}$이 주어졌을 때, 부분수열 $\{a_l, a_{l+1}, ..., a_r\}$ 중 Stack Exterminable Array의 개수를 구하라.

부분수열 $\{A_l, A_{l+1}, ..., A_r\}$을 $A[l, r]$이라 표기하자. 각 $l \in [0, N-1]$에 대해 $nxt_l$을 $min\{r|A[l, r]$이 Stack Exterminable Array$\}$로 정의하자. 그러한 $r$이 없다면 $nxt_l=-1$이라 하자. $l=N-1, ..., 0$에 대해 $nxt_l$을 차례대로 구하자. 

$A_l = A_{l+1}$인 경우에는 $nxt_l=l+1$이다. 그렇지 않다면, $A[l+1, nxt_{l+1}]$을 덧붙인 뒤 $A_l=A_{nxt_{l+1}+1}$인지 확인한다. 그렇지 않다면 $A[nxt_{l+1}+1, nxt_{nxt_{l+1}+1}]$을 덧붙인 뒤 반복한다. 즉, $A_l$이 나올 때까지 부분수열을 덧붙이는 과정을 반복한다. 이 과정을 빠르게 하기 위해서는 $l+1$에 대해, 뒤에 덧붙여지는 블록들 ($A[l+1, nxt_{l+1}]$, $A[nxt_{l+1}+1, nxt_{nxt_{l+1}+1}]$, ...)들에 대해 그 다음에 $A_l$이 나오는 것이 언제인지 기록해야 한다. 각 $l+1, x$에 대해 $l+1$ 뒤에 덧붙여지는 블록 중 $x$가 나오는 것이 언제인지를 $map[l][x]$에 저장하자. $map[l]$는 $map[nxt_l+1]$에서 key = $A_{nxt_l+1}$만을 갱신한 것이다.

 

map의 복사는 느리다. 따라서 한 가지 관찰을 더 하자 : $map[nxt_l+1]$은 더 이상 참조할 일이 없다.

$map[nxt_l+1]$을 참조하기 전에 $map[l]$을 참조하기 때문에 위 명제는 참이다. 이는 $map[nxt_l+1]$을 유지할 필요가 없다는 것을 의미한다. 따라서 $map$을 복사하는 것이 아니라 swap을 하면 $O(NlogN)$에 풀 수 있다.

 

나는 마지막 관찰을 하지 못해서 map 대신 persistent segment tree를 이용했다. 리프 노드들이 $map$의 값을 가지게 하면 $O(NlogN)$에 해결할 수 있다. 대신 공간복잡도가 $O(N)$이 아니라 $O(NlogN)$가 된다.

 

 

E. Wooden Raft

통나무가 $N$개가 있고, $i$번 통나무의 길이는 $a_i$이다. 통나무를 자를 수는 있지만 이을 수는 없다. $x\times y$ 크기의 뗏목을 만들기 위해서는 길이 $x$의 통나무 2개와 길이 $y$의 통나무 $x$개가 필요하다($x \geq 2, y \geq 2, x, y \in \mathbf{N}$). $x\times y$ 크기의 뗏목의 넓이는 $xy$이다. 이 때, 만들 수 있는 통나무의 최대 넓이는?

$a_i$의 최댓값을  $A$라 하자. $y\in[2, A]$ 값을 고정한 뒤 가능한 최대 $x$를 $O(A/y)$로 구하자. 그러면 $O(AlogA)$로 문제를 해결할 수 있다. 우선, 크기가 $i$ 이하인 통나무의 개수를 $cnt[i]$에 기록을 해서, 길이가 특정 범위인 통나무의 개수를 $O(1)$에 구할 수 있도록 하자. 이제 특정 $(x, y)$가 가능한지 판단하는 방법을 생각해보자. 통나무들에서 길이 $x$의 통나무를 2개 잘라낸 뒤 나머지 통나무를 길이 $y$의 통나무로 자르자. 그렇게 생긴 길이 $y$ 통나무가 $x$개 이상이면 $(x, y)$ 조합이 가능한 것이고, 그렇지 않으면 불가능한 것이다. 길이 $x$ 통나무 2개를 자르는 방법은 2가지가 있다 : 같은 통나무에서 $2x$를 잘라내는 방법, 두 개의 통나무에서 각각 $x$를 잘라내는 방법. 각 방법에 대해 살펴보자.

 

한 통나무에서 $2x$를 잘라내는 경우를 생각하자. 길이 $x$의 통나무를 고려하지 않을 때, 길이 $y$의 통나무는 $C=\sum_i i(cnt[(i+1)y-1]-cnt[iy-1])$개 잘라낼 수 있다. $2x \in [ky, (k+1)y)$라 하자. $A_i \geq ky$ and ($A_i$ mod $y$) $\geq$ ($2x$ mod $y$)인 $i$가 있다면 그 통나무에서 $2x$를 잘라내면 된다. 그러면 길이 $y$의 통나무를 $C-k$개 얻을 수 있다. $A_i \geq ky$인 $i$에 대해 ($A_i$ mod $y$)의 최댓값을 $mx[k]$라 하자. 그러면 이 경우 $x$의 최댓값은 min$((ky + mx[k])/2, C - k)$이다. 또는 $A_i \geq (k+1)y$ and ($A_i$ mod $y$) < ($2x$ mod $y$)인 $i$에 대해 잘라낼 수도 있다. 그러면 길이 $y$의 통나무를 $C-k-1$개 얻을 수 있다. 그러면 $x$의 최댓값은 min$(((k+1)y + mx[k + 1])/2, C- k - 1)$이다. 

 

이제 서로 다른 두 통나무에서 길이 $x$를 잘라내는 경우를 생각하자. $x \in [ky, (k+1)y)$라 하자. 위에서와 마찬가지로 $A_i \geq ky$ and ($A_i$ mod $y$) $\geq$ ($x$ mod $y$)인 $i$가 있다면 그 통나무에서 $x$를 잘라내면 된다. $A_i \geq ky$인 $i$에 대해 ($A_i$ mod $y$)의 최댓값 두 개를 $mx1[k], mx2[k]$라 하자($mx1[k] \geq mx2[k]$). 그러면 $x$의 최댓값은 max{ min$((ky+mx2[k]),C-2k)$, min$(ky+mx1[k],(k+1)y+mx2[k+1],C-2k-1)$, min$((k+1)y+mx2[k+1],C-2k-2)$}이다.

 

 

F. Football

추가 예정

'Codeforces' 카테고리의 다른 글

Codeforces Round #594 (Div. 1)  (0) 2019.10.28
Codeforces Global Round 5  (0) 2019.10.24
Codeforces Round #588 (Div. 1)  (0) 2019.09.28