Codeforces Round #915 (Div. 2)

지난번에 있었던 코포 라운드에서 뜻하지 않게 탑레를 갱신하게 되었다. 다운보트를 무려 4000개나 받은 역대급 셋이었지만 내가 많이 올랐으면 된 게 아닐까..?

 

아무튼 레드가 갑자기 가시권으로 다가오게 돼서 버츄얼을 시간 날 때마다 돌기로 했다. kongum과 leo020630과 함께 돌았다.

 

문제 셋 퀄리티는 좋았고, 난이도 밸런스도 적당했다. 아쉬웠던 점은 1시간 정도 남기고 E, F를 둘다 못 풀었다는 점인데, 둘 다 그렇게 어려운 문제가 아니었어서 조금 아쉽게 느껴진다. 예상 퍼포먼스는 2305가 나왔다.

https://codeforces.com/contest/1905

---

A. Constructive Problem [00:02:01] *800

초기 배치하는 칸을 대각선으로 이어지게 잘 배치해주면 된다. 따라서 답은 $\max(N, M)$이다.

https://codeforces.com/contest/1905/submission/239892230

---

B. Begginer's Zelda [00:06:01] *1100

당연히 합칠 수 있다면 더 많은 정점들을 한 번에 합치는 게 최적이다. 따라서 항상 리프 노드 두 개를 골라서 합친다고 생각해도 문제가 없다.

문제의 목표는 리프 노드의 개수를 $0$개로 만드는 것이다. 현재 리프 노드가 세 개가 아니라면, 항상 두 리프 노드를 합쳤을 때 만들어진 노드가 리프가 아니도록 만들 수 있다. 따라서 리프 노드의 개수를 두 개씩 감소시켜 가되, 개수가 세 개일 때만 예외적으로 처리를 해주면 된다.

위 시뮬레이션 결과를 일반화하면, 주어진 트리의 리프 노드 개수를 $L$이라 했을 때 답은 $\lceil \frac{L}{2} \rceil$이 된다.

https://codeforces.com/contest/1905/submission/239892645

---

C. Largest Subsequence [00:27:36, -2] *1400

문제에서 주어진 연산을 반복적으로 적용한 결과는 결국 주어진 문자열에서 Largest Subsequence를 찾고 그 문자열을 뒤집는 것과 동일하다. 단, 연산을 계속 진행하다가 Largest Subsequence가 같은 문자로만 구성되어 있을 경우에는 연산을 적용해도 결과가 동일하므로 더 진행할 필요가 없다. 따라서 답은 (Largest Subsequence의 길이) - (Largest Subsequence를 구성하는 사전순으로 가장 큰 문자의 개수)가 된다. 스택 같은 걸 써서 Largest Subsequence를 $O(N)$에 구할 수 있으니, 전체 문제도 $O(N)$에 해결할 수 있다.

구현을 조금 절어서 두 번 틀렸다.

https://codeforces.com/contest/1905/submission/239894998

---

D. Cyclic MEX [00:43:06] *2000

Prefix $\text{mex}$가 가지는 성질에 대한 관찰이 필요하다.

• $1 \le k < N$일 때 구간 $[1, k]$에서의 $\text{mex}$는 $[k + 1, N]$ 구간의 최솟값과 같다.
• $k = N$일 때는 주어진 수열이 순열이므로 항상 $\text{mex}$가 $N + 1$이다.

 

이에 따라 Cyclic Shift를 한 번 하게 되면 $\text{mex}$에는 다음과 같은 변화가 일어난다는 것을 알 수 있다.

• $k = 1$에 해당하는 $\text{mex}$가 사라진다.
• 현재 $\text{mex}$가 $P_1$보다 큰 값들은 모두 $P_1$로 변한다.
• $k = N$에 해당하는 $\text{mex}$가 생긴다.

 

따라서 매번 옮길 때마다 값의 변화를 직접 추적해줄 수 있다. map에 ($\text{mex}$ 값, 원소 개수)를 저장한 뒤, Cyclic Shift를 할 때마다 이분 탐색으로 값들을 옮겨주면 된다. 이렇게 값들을 묶어서 관리하게 되면, 값들을 옮기는 횟수의 총합은 $O(N)$에 바운드되기 때문에 $O(NlogN)$에 문제를 해결할 수 있다.

$\text{mex}$가 단조적이라는 점을 이용하면 덱을 사용해서 $O(N)$에 문제를 해결할 수도 있다.

https://codeforces.com/contest/1905/submission/239896694

---

E. One-X [Upsolved] *2400

트리가 재귀적으로 정의되므로, DP를 이용해서 잘 비벼보면 될 것 같다는 생각이 든다.

$dp_n$: $n$개의 리프 노드가 있고, 루트의 번호가 $1$일 때의 답이라고 하자.

리프 노드가 $n$개인 트리는 리프 노드가 $\lceil \frac{n}{2} \rceil$, $\lfloor \frac{n}{2} \rfloor$개인 두 개의 서브 트리를 자식으로 갖는다. 그래서 $dp_{\lceil \frac{n}{2} \rceil}$과 $dp_{\lfloor \frac{n}{2} \rfloor}$를 잘 조합하면 $dp_n$의 값도 구할 수 있을 것 같다.

 

서브트리의 루트는 $1$이 아니므로, 값을 합칠 때 차이를 잘 보정해줘야 한다. 차이가 얼마나 생기는지는 트리를 좀 끄적이다보면 알 수 있는데, 다음과 같은 값들을 정의하자. 모두 루트의 번호는 $1$이라고 가정한 값들이다.

• $L_{n, k}$: $n$개의 리프가 있는 트리에서, $k$번 정점을 루트로 하는 서브트리에 포함된 리프의 개수
• $C_n$: $n$개의 리프가 있는 트리에서, 루트를 LCA로 가지는 리프 집합의 개수
• $T_n$: $n$개의 리프가 있는 트리에 포함된 정점 번호의 집합
• $d_k$: $k$번 정점과 루트와의 거리

이제 $up_n: \sum_{k \in T_n} {2^{d_k}C_{L_{n, k}}}$라 하자. 그러면 루트가 $a$일 때 모든 LCA의 합은 $dp_n + (a - 1) \times up_n$이 됨을 알 수 있다. 이제 다음 식들을 잘 조합하면 구하고자 하는 $dp_n$의 값을 구할 수 있다. 실제로 구해야 하는 $dp$ 값의 개수는 $log$개 이므로, 메모이제이션을 잘해주면 시간복잡도는 $O(log^2N)$이다.

• $C_n = 2^n - 1 - (2^{ \lceil \frac{n}{2} \rceil } - 1) - (2^{ \lfloor \frac{n}{2} \rfloor } - 1)$
• $up_n = 2 \times up_{ \lceil \frac{n}{2} \rceil } + 2 \times up_{ \lfloor \frac{n}{2} \rfloor } + C_n$
• $dp_n = dp_{ \lceil \frac{n}{2} \rceil } + up_{ \lceil \frac{n}{2} \rceil } + dp_{ \lfloor \frac{n}{2} \rfloor } + 2 \times up_{ \lfloor \frac{n}{2} \rfloor } + C_n$

https://codeforces.com/contest/1905/submission/240070755

---

F. Field Should Not Be Empty [Upsolved] *2600

처음에 good인 인덱스의 수가 $N$개라면 항상 답은 $N - 2$이다.

이외의 경우에는 swap을 해서 답을 증가하도록 만들 수 있다. 따라서 swap을 할 수 있는 $O(N^2)$가지 경우의 수 중, 답에 유효한 영향을 미치는 몇 개의 경우만 잘 따져보면 된다.

 

swap에 의해 간접적으로 good이 되는 경우와 직접적으로 good이 되는 경우로 나눠서 생각해 보자. 직접적이라는 것은 swap 한 값이 good이 되는 것을 말하고, 간접적이라는 것은 swap 하지 않은 값이 good이 되는 것을 말한다.

 

어떤 인덱스 $k$가 간접적으로 good이 되려면 적어도 다음 세 가지 조건을 만족하고 있어야 한다. swap은 Point Update 이므로, 양쪽에서 최대 하나씩의 값만 변화시킬 수 있기 때문이다.

 

1. $P_k = k$
2. $[1, k)$ 구간에서 $k$보다 큰 수가 최대 한 개
3. $(k, N]$ 구간에서 $k$보다 작은 수가 최대 한 개

2, 3번 조건에 해당하는 수가 모두 한 개라면, swap을 했을 때 답이 증가하는 경우가 유일하다. 따라서 이 경우에 해당하는 swap은 $O(N)$개가 존재한다.

 

직접적으로 good인 인덱스를 만들기 위해서는 또는 $P_i$와 $i$를 swap해야 한다. 이 경우에 해당하는 swap도 $O(N)$개 존재한다.

 

이제 어떤 swap이 유효한지 알았으니, 가능한 경우를 모두 해보고 그 중 최대가 되는 경우를 찾으면 된다. 에디토리얼에서는 세그를 썼는데, set이랑 map 떡칠을 해도 문제를 해결할 수 있다. 내 풀이는 이분 탐색을 사용하고 있어서 $O(NlogN)$이다.

https://codeforces.com/contest/1905/submission/240085316