Codeforces Round #914 (Div. 2)

Hello 2024 라운드를 대비하기 위해 버츄얼을 돌았다. FD..LH..lloyJ(김도훈이라고 읽는다고 한다..)와 sharaelong님이랑 같이 돌았다.

특이사항으로는 E, F가 모두 난이도 있는 트리 문제였는데, 두 문제 다 예전에 풀어본 문제들 중 하나랑 비슷한 점이 있었는데도 불구하고 대회 시간 내에 해결하지 못했다. 다만 D와 E의 난이도 차이가 커서 그런지 퍼포먼스는 2432가 나왔다.

https://codeforces.com/contest/1905

---

A. Forked! [00:09:46, -1] *900

관점을 바꿔서 생각한다. 두 왕이 이동할 수 있는 칸 중, 몇 개의 칸이 겹치는지 세면 쉽다.

https://codeforces.com/contest/1904/submission/240241771

---

B. Collecting Game [00:13:50] *1100

배열 $A$의 값이 커질수록 답은 단조적으로 증가한다. 따라서 배열 $A$를 정렬한 뒤, 투 포인터를 이용해 각 값에 대해 답을 전처리해 줄 수 있다. 

https://codeforces.com/contest/1904/submission/240242324

---

C. Array Game [00:21:13] *1400

우선 연산을 세 번 이상 할 수 있다면 항상 답은 $0$이 됨을 관찰해야 한다. 같은 인덱스 쌍을 두 번 고르면 두 개의 같은 수가 나오고, 같은 수가 존재한다면 연산을 이용해 $0$을 만들 수 있기 때문이다.

 

이제 연산을 두 번 사용해 답을 최소로 만드는 방법을 알아보자. (한 번은 쉬우니까...) 우선 $O(N^2)$가지 모든 경우를 계산한다. 그러면 두 번째 연산은 $A_i$와 앞에서 만든 $O(N^2)$개 값 중 하나를 연산에 사용할 수 있다. 이분 탐색을 이용하면 각 $A_i$에 대해 가장 절댓값 차가 작은 후보 값을 구해줄 수 있으니, $O(N^2logN)$에 문제를 해결 가능하다.

https://codeforces.com/contest/1904/submission/240243266

---

D1, D2. Set to Max [00:37:00] *1600, *1800

D2 풀이가 먼저 보여서 D1만 통과하는 풀이를 따로 고민해보진 않았다.

 

$B_i$가 작은 위치부터 하나씩 맞춰가는 방식을 사용한다. 어떤 $A_i$를 $B_i$로 만들 수 있다는 것은, 처음부터 $A_i = B_i$ 이거나 $A_i < B_i$ 이면서 $\max$ 쿼리를 이용해 $B_i$에 해당하는 값을 가져올 수 있음을 의미한다.

 

현재 위치 $p$에서 가장 가까우면서 $A$의 값이 $B_p$인 지점을 $pos$라고 하자. $pos$에서 값을 가져오기 위해선 $p$와 $pos$ 사이에 배열 $A$의 값 중 $B_i$보다 더 큰 값이 없어야 하고 ($\max$ 쿼리의 결과가 $B_i$가 되어야 하므로), 배열 $B$의 값 중 $B_i$보다 더 작은 값이 없어야 한다. (이미 조건을 만족한 정점들의 결과가 변하므로)

 

특정 위치에서 가장 가까운 다른 위치를 찾는 것과, 특정 구간에 조건을 만족하는 점이 존재하는지 판별하는 것은 모두 set을 잘 쓰면 $log$ 시간에 가능하다. 따라서 $O(NlogN)$에 문제를 해결할 수 있다.

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

---

E. Tree Queries [Upsolved] *2500

Towns and Roads 라는 문제와 비슷한 아이디어를 사용한다. 모든 정점과의 거리를 세그먼트 트리의 노드에 저장해 두면, Max Range Query를 날려서 가장 멀리 떨어진 정점과의 거리를 구할 수 있음을 이용한다. (이때 저장하는 위치는 오일러 투어의 방문 순서에 해당한다)

 

쿼리를 오프라인으로 처리한다. 루트 정점에서 시작해, 다른 모든 정점으로 DFS로 한 번씩 방문하면서 각 정점에 해당하는 쿼리의 답을 계산한다. 부모 정점에서 자식 정점으로 이동할 때는 자식 정점의 서브트리에 속하는 모든 정점의 거리는 $1$ 감소하고, 이외의 모든 정점의 거리는 $1$ 증가한다. ETT를 이용하면 이를 구간 업데이트로 처리할 수 있다.

 

쿼리를 처리할 때는 어떤 정점이 삭제되었을 때 도달하지 못하게 되는 정점 역시 구간을 이룸을 이용한다. 도달이 불가능한 구간에 -INF 만큼을 더해주는 방식을 이용하면, Range Max Query를 그대로 이용해 가장 멀리 떨어진 정점을 잘 찾을 수 있다. 조상 정점이 삭제되는 경우 처리가 조금 까다로울 수 있는데, 이때는 반대로 도달 가능한 구간에 INF만큼을 더해주는 것으로 유사하게 처리가 가능하다. 시간복잡도는 $O((N + Q + K)logN)$이다.

https://codeforces.com/contest/1904/submission/240294164

---

F. Beautiful Tree [Upsolved] *2800

두 수의 대소 관계를 그래프의 간선을 이용해 나타낸다. 구체적으로는 정점 $n$에 할당해야 하는 값을 $P_n$이라 했을 때, $P_i < P_j$가 되어야 한다면 $i \rightarrow j$ 와 같이 간선을 그어준다.

 

문제는 모든 간선을 그냥 그으면 $O(N^2)$개의 간선을 만들어야 하는데, 간선을 그어야 하는 영역이 구간으로 나타남을 이용한다. 적당한 전처리를 해두면 모든 구간을 $O(log^2N)$개의 정점으로 나눌 수 있고, 이를 이용해 유효한 간선의 개수를 $O(Nlog^2N)$개로 줄일 수 있다. ($O(log^2N)$개인 이유는 HLD를 이용해 트리의 경로를 $O(logN)$개의 구간으로 나눈 뒤, 나눈 구간을 다시 $O(logN)$개의 정점으로 나누기 때문이다.)

 

이렇게 만든 그래프에서 위상 정렬이 가능한지를 판별하고, 가능하다면 방문한 순서대로 정점에 값을 할당해 주면 $O(Nlog^2N)$에 문제를 해결할 수 있다. 구현은 JOISC 2021/2022의 Jail과 비슷했던 것 같다.

https://codeforces.com/contest/1904/submission/240332849