Intro
Greedy Termite (ICPC Tehran Site 2019)
다음으로 갈 위치를 빠르게 구할 수 있으면 문제를 풀 수 있습니다. 현재 $i$번째 막대기에 있다고 할 때, 다음으로 갈 막대기 $j$의 조건은 다음과 같습니다.
- $H_j - \vert X_i - X_j \vert$가 최대
- $\vert X_i - X_j \vert$가 최소
- $j$가 최소
절댓값 기호는 사회악이므로 $X_i$와 $X_j$의 대소 관계에 따라 식을 조건을 다시 정리해봅시다.
- $X_j < X_i$인 경우 (왼쪽으로 이동하는 경우)
- $H_j + X_j - X_i$가 최대
- $X_i - X_j$가 최소
- $j$가 최소
- $X_j > X_i$인 경우 (오른쪽으로 이동하는 경우)
- $H_j - X_j + X_i$가 최대
- $X_j - X_i$가 최소
- $j$가 최소
이때, $i$는 상수라고 생각할 수 있으므로 $j$에 대한 항만 최대화/최소화하면 됩니다. 그러므로 왼쪽으로 이동하는 경우에는 $H_j + X_j$를 최대화/$-X_j$를 최소화하면 되고, 오른쪽으로 이동하는 경우에는 $H_j - X_j$를 최대화/$X_j$를 최소화하면 됩니다.
어떤 구간에서 우선순위가 가장 높은 원소를 찾는 연산은 세그먼트 트리를 이용해서 $O(\log N)$ 시간에 처리할 수 있습니다. 두 막대기 간의 우선순위 비교는 상수 시간에 할 수 있으므로 가장 우선순위가 높은 막대기를 $O(\log N)$ 시간에 찾을 수 있고, 전체 문제를 $O(N \log N)$에 해결할 수 있습니다.
Confuzzle (2020 SPC Champion)
다양한 풀이가 존재합니다. 이 글에서 소개하는 4가지 풀이 외에도 다양한 풀이가 존재할 수 있습니다.
Sol 1. 센트로이드 분할
트리의 모든 경로를 고려하는 문제의 대부분은 센트로이드 디컴포지션을 이용해서 해결할 수 있습니다.
이 문제는 끝점이 같은 색깔인 가장 짧은 경로를 구하는 문제이므로, 각 색깔 별로 “센트로이드와 가장 가까운” 경로만 저장하면 됩니다. $O(N \log N)$ 시간에 문제를 풀 수 있습니다.
Sol 2. 루트
Naive한 풀이 2가지는 쉽게 생각할 수 있습니다.
- 색깔이 같은 모든 $x \choose 2$가지 정점 쌍에 대해 거리 구하기
- 각 정점에서 시작하는 Multi-Source BFS로 최소 거리 구하기
(1)은 정점이 많아질수록 느려지고, (2)는 색깔의 종류가 많아질수록 느려집니다. 정점의 개수와 색깔의 종류에 대해 유동적으로 두 가지 풀이를 선택해서 사용한다면 문제를 풀 수 있다는 생각을 할 수 있습니다.
각 색깔마다 정점이 $X$보다 적다면 1번 풀이를, $X$보다 많다면 2번 풀이를 적용한다고 생각해봅시다.
정점이 $X$개 이하이므로 각 색깔마다 확인할 정점 쌍은 최대 $X^2$가지입니다. LCA를 $O(\log N)$ 시간에 구하면 $O(X^2 \log N)$, $O(1)$에 구하면 $O(X^2)$만큼 걸립니다. 정점이 $X$개씩 $N/X$묶음 주어지는 것이 최악의 경우이고, 이때 시간 복잡도는 $O(NX \log N)$ 혹은 $O(NX)$입니다.
정점이 $X$개 이상인 색깔은 최대 $N/X$가지 밖에 존재할 수 없습니다. 각 색깔마다 Multi-Source BFS를 수행하는 시간은 $O(N)$이므로 이 경우의 시간 복잡도는 $O(N^2/X)$입니다.
$NX + N^2/X$를 최소화하는 $X$는 $\sqrt N$입니다. 이때 시간 복잡도는 $O(N \sqrt N)$이 되어서 시간 제한 안에 문제를 해결할 수 있습니다. LCA를 $O(\log N)$에 구하는 경우, $X = \sqrt{\frac{N}{\log N}}$으로 잡으면 $O(N \sqrt{N \log N})$이지만, $X = \sqrt N$으로 잡아서 $O(N \sqrt N \log N)$으로 풀어도 큰 차이는 없습니다.
Sol 3. 트리 압축
색깔이 같은 정점끼리 모아서 트리 압축을 합시다. 색깔이 $c$인 정점을 모아서 압축한 트리에서 “현재 정점에서 가장 가까운/두번째로 가까운 색깔이 $c$인 정점”을 구하는 트리 DP를 하면 정답을 구할 수 있습니다.
트리 압축을 하는데 $O(N \log N)$이 걸리고, 트리 DP는 $O(N)$이므로 $O(N \log N)$에 문제를 해결할 수 있습니다.
Sol 4. Small to Large
트리 압축에서의 풀이를 조금 변형하면 색깔 별로 트리를 분리하지 않아도 문제를 풀 수 있습니다.
트리 압축에서 “현재 정점에서 가장 가까운/두번째로 가까운 색깔이 $c$인 정점”을 std::pair로 관리했는데, std::map을 사용하면 모든 색깔에 대해 pair를 모두 저장할 수 있습니다. (D[v][c] : $v$를 루트로 하는 서브 트리에서 $v$와 가장/두번째로 가까운 색깔이 $c$인 정점)
std::map을 합칠 때 작은 컨테이너에 있는 원소를 큰 컨테이너로 옮겨주는 방식으로 합치면 원소들이 최대 $O(N \log N)$번 이동하므로 $O(N \log^2 N)$에 문제를 풀 수 있습니다.
United Cows of Farmer John (USACO 2021 US Open Platinum)
USACO Platinum 문제로 출제된 문제입니다. 이 문제의 풀이를 알아보기 전에, Gold에 출제된 동일한 이름의 문제를 먼저 풀어봅시다. 리더를 2마리 뽑는다는 점이 다릅니다.
소를 차례대로 보면서, $i$번째 소가 두 번째 리더가 되는 경우의 수를 각각 구해서 더할 것입니다. 즉, $i$번째 소가 두 번째 리더일 때 첫 번째 리더가 될 수 있는 소의 수를 구하면 됩니다.
$i$번째 소가 두 번째 리더가 된다고 했을 때, 첫 번째 리더가 될 수 없는 소를 소거하는 방식으로 진행할 것입니다.
- $i$ 보다 왼쪽에 있는 점 중 품종이 같은 가장 오른쪽에 있는 소를 $last_i$라고 합시다. 리더의 품종은 유일해야 하기 때문에 $last_i$를 포함할 수 없습니다. 즉, $1 \cdots last_i$는 리더가 될 수 없습니다.
- 각 품종 별로 가장 최근에 본(아직 누군가의 $last$가 된 적 없는) 소들만 대표가 될 수 있습니다.
아직 누군가의 $last$가 된 적 없는 소를 active 상태라고 하면, $i$마다 구간 $[last_i+1, i-1]$에서 active된 소의 수를 구하는 문제가 됩니다.
다시 원래 문제, 즉 리더 3마리를 선택하는 문제로 돌아옵시다. 소를 차례대로 보면서 $i$가 세 번째 리더가 될 수 있는 경우의 수를 센다는 풀이의 방향은 그대로 유지합니다. 하지만 $i$가 세 번째 리더일 때 가능한 “(첫 번째 리더, 두 번째 리더) 순서쌍의 수”를 직접 세는 것은 어려워 보입니다.
세 번째 리더를 고정한 것처럼, 한 마리를 더 고정해봅시다. 가운데 리더를 고정하는 것보다는 첫 번째 리더를 고정하는 것이 편해보이므로, $X_i(j)$를 $i$가 세 번째 리더 / $j$가 첫 번째 리더일 때 가능한 두 번째 리더의 수라고 정의해봅시다. Gold 문제와 마찬가지로, 두 번째 대표가 될 수 있는 조건은 $last_i$보다 뒤에 있고, 아직 누군가의 $last$가 된 적 없는(active 상태인) 소입니다.
$X_{i-1}(j) \rightarrow X_{i}(j)$의 상태 전이만 빠르게 계산할 수 있다면, 세그먼트 트리를 이용해 $X_i(last_i+1) \cdots X_i(i-1)$의 합을 구하는 것으로 문제를 풀 수 있습니다. 구체적으로 어떤 값이 바뀌는지 생각해봅시다.
- $last_i$와 $i$의 active 여부가 변경되었으니 이 정보를 갱신해야 합니다. (Point Update 2번)
- $last_i$는 더 이상 두 번째 소가 될 수 없으므로 구간 $[last_{last_i}, last_i-1]$의 값을 1 감소시켜야 합니다. (Range Update 1번)
- $i$번째 소를 본 이후부터는 $i$가 두 번째 소가 될 수 있으므로 구간 $[Last_i+1, i-1]$의 값을 1 증가시켜야 합니다. (Range Update 1번)
이 연산들은 세그먼트 트리와 레이지 프로퍼게이션을 이용해서 $O(\log N)$에 처리할 수 있습니다.
% (UCPC 2019 Qualification)
올바른 괄호 문자열은 “괄호가 중첩되어 있다는 점”을 활용해 트리 구조로 나타낼 수 있습니다. 이 문제 역시 트리의 관점에서 바라볼 수 있으며, 이를 활용한 풀이는 UCPC 2019 공식 풀이 슬라이드 61페이지에 자세히 나와있습니다.
이 글에서는 공식 풀이와 다른 관점에서 바라본 풀이를 소개합니다.
길이가 13인 괄호 문자열 .(.()..(.).).는 아래 그림처럼 정점 13개, 가중치가 1인 간선 12개(검은색 간선), 가중치가 2인 간선 3개(보라색 간선)으로 나타낼 수 있습니다. 이때 파란색 괄호(열고 닫는 괄호가 인접한 쌍)를 연결하는 보라색 간선은 만들지 않아도 됩니다.
아래 그림처럼 가중치가 INF인 간선을 몇 개 추가하면 $N$각형을 삼각분할한 형태로 바꿀 수 있습니다. 즉, NEERC 2015 Distance on Triangulation과 동일한 문제로 바꿀 수 있습니다.
Distance on Triangulation (NEERC 2015)
계산 기하를 공부하다보면 삼각분할과 함께 붙어다니는 “듀얼 트리(Dual Tree)”를 볼 수 있습니다. 평면 그래프의 듀얼 그래프와 비슷하게, 각 삼각형을 정점으로, 인접한 삼각형을 간선으로 연결한 트리를 듀얼 트리라고 합니다.
각 정점의 차수가 최대 3이기 때문에 Centroid Decomposition과의 궁합도 좋습니다. 이 문제도 Centroid Decomposition을 이용해서 해결할 수 있습니다. Dual Tree에서 Centroid를 잡고, Centroid에 해당하는 삼각형을 지나는 모든 쿼리를 오프라인으로 처리합니다.
작성 예정…