2025.07.05 problem solving

티스토리 뷰

공부/Problem solving

BOJ 33365. Password

최댓값은 $n$ 입니다. 최솟값은, 비밀번호의 중앙에 비알파벳 문자를 배정한 후, 중앙에서 왼쪽 / 오른쪽으로 세 문자마다 비알파벳 문자를 배정하면 됩니다.

$\sum_{i = 1}^{n}\lfloor \frac{n}{i} \rfloor$ 을 $O(\sqrt n)$ 시간에 계산할 수 있으면 전체 문제를 이분 탐색으로 $O(\sqrt n \log n)$ 시간에 해결할 수 있습니다. 그 방법을 소개합니다.
$\sum_{i = 1}^{n}\lfloor \frac{n}{i} \rfloor$ 를 계산할 때는, 항상 $\lfloor \frac{n}{i} \rfloor \leq \sqrt n$ 혹은 $i \leq \sqrt n$ 중 하나가 성립합니다. 고로, $i \leq \sqrt n$ 에 대해서는 brute force를 통해서 계산해 주고, $i > \sqrt n$ 에 대해서는 몫인 $k = \lfloor \frac{n}{i} \rfloor$ 을 고정시킨 후, $k = \lfloor \frac{n}{i} \rfloor$ 가 만족되는 $i > \sqrt n$ 의 개수와 $k$ 를 곱해서 합해줍니다. $k = \lfloor \frac{n}{i} \rfloor$ 라는 조건은 $\frac{n}{k+1} < i \leq \frac{n}{k}$ 와 동치이니, 그러한 $i > \sqrt n$ 의 개수는 단순 수식을 사용하여 계산 가능합니다.

BOJ 26700. Sumy

특정한 메기가 모든 메기를 잡아먹을 수 있는지를 판별하는 것은, 모든 메기를 무게 순으로 정렬한 후 작은 메기부터 차례차례 먹는 것이 가능한지 확인하는 식으로 가능합니다. 이를 단순하게 구현하면 $O(n^2)$ 시간에 문제를 해결할 수 있습니다. 이 판별 과정은 초기 메기의 무게에만 의존하기 때문에, 무게 $x$ 의 메기가 모든 메기를 잡아먹을 수 있으면 무게 $x+1, x+2, \ldots$ 에 대해서도 해당이 되고, 무게 $x$ 의 메기가 모든 메기를 잡아먹을 수 없으면 무게 $x-1, x-2, \ldots$ 에 대해서도 해당이 됩니다. 고로, 모든 메기를 잡아 먹을 수 있는 메기의 최소 무게를 이분탐색으로 찾아주면, 전체 메기에 대해서 효율적으로 판별할 수 있습니다. 시간 복잡도는 $O(n \log n)$ 입니다.

BOJ 33367. Poor Students

이 문제는 Min-cost Max-flow 문제로 아래와 같이 모델링될 수 있습니다:

정점: source, $k$ 개의 과목, $n$ 명의 학생, sink.
Source에서 $i$번 과목으로 용량 $a_i$, 비용 $0$ 의 간선
$i$ 번 과목에서 $j$번 학생으로 용량 $1$, 비용 $c_{j, i}$ 의 간선
$i$ 번 학생에서 Sink로 용량 $1$, 비용 $0$ 의 간선

Source에서 Sink로 가는 증가 경로를 $n$ 번 흘려주면 전체 문제를 해결할 수 있습니다. 이를 단순히 시뮬레이션하면 느리니, 증가 경로를 빠르게 찾는 방법을 생각해 봅시다.

모든 증가 경로는, (source) -> 과목 1 -> 학생 1 -> 과목 2 -> 학생 2 -> ... -> 과목 $m$ -> 학생 $m$ -> (sink) 의 형태를 띕니다. 증가 경로에 등장하는 과목의 리스트가 고정되었을 때 최적 경로를 찾아 봅시다. 먼저 $1$ 번 과목은 남는 용량이 있어야 하고, $m$ 번 학생은 남는 용량이 있어야 하며, 각 과목 사이의 학생은 용량이 있는 학생 중 비용을 최소로 해야 합니다. 한편으로, 이 조건만 만족하면, 각 과목 사이에서 고르는 학생들이 독립적이기 때문에 (단순 경로일테니) 최적의 Augmenting path를 찾을 수 있습니다. 즉, $i$ 번 과목에서 $j$ 번 과목으로 가는 간선의 비용만 계산해 줄 수 있으면 Bellman-Ford로 $O(k^3)$ 증가 경로를 구할 수 있고, 이렇게 하면 MCMF를 돌려주면 되니 전체 문제를 $O(nk^3)$ 에 해결할 수 있다는 것입니다.

$i$ 번 과목에서 $j$ 번 과목으로 이동하려면, 현재 $j$ 번 과목을 듣고 있는 학생 $s$ 중 $c_{s, i} - c_{s, j}$ 의 최솟값을 빠르게 계산해야 합니다. 각 $(i, j)$ 에 대해서 위와 같은 $s$ 를 Heap을 사용하여 관리해주면, 그래프를 $O(k^2)$ 시간에 구성할 수 있으며, 증가 경로를 따라 갱신해 주는 것도 최대 $k^2$ 번의 Heap 연산으로 가능합니다. 이렇게 하면 전체 문제를 $O(nk^3 + n k^2 \log n)$ 에 해결할 수 있습니다.

PA 2021 3-3. Wystawa

답에 대해 이분 탐색을 합니다. 즉, $T$ 이하로 최대 부분합을 유지하면서 $k$ 개의 $A$ 를 고를 수 있는 지를 판정합니다.

먼저 결정 문제를 $O(n^2)$ 에 해결하는 풀이를 소개합니다. $dp[i][j]$ 를, 부분합을 $T$ 이하로 유지하면서 첫 $i$ 개 중 $j$ 개의 $A$ 를 선택하였을 때, maximum suffix의 최솟값이라고 정의합시다. 최대 부분합은 $T$ 이하로 계속 유지한다고 귀납적으로 가정하면, 결국 중요한 것은 maximum suffix 뿐이기 때문에 위와 같은 풀이가 유효합니다. 이 때 점화식은 $dp[i][j] = \max \min(dp[i-1][j-1] + A[i], dp[i-1][j] + B[i]), 0)$ 꼴이고, 추가로 $dp[i][j] > T$ 일 경우 해당 엔트리는 유효하지 않다고 체크해야 합니다 (예를 들어 $\infty$). $dp[n][k] \le T$ 일 경우 결정 문제가 참이며, 역추적도 DP 테이블을 따라가면서 할 수 있습니다.

두 번째로, 일반성을 (거의) 잃지 않고 $A[i] \geq B[i]$ 를 가정할 수 있습니다. $A[i] \leq B[i]$ 인 $i$ 의 개수가 $c$ 개 있고, $c \leq k$ 라고 합시다. 이 경우, 이러한 $c$ 개의 $i$ 에 대해서는 $A[i]$ 를 사용하는 것을 고정하고, $A[i] > B[i]$ 인 $k-c$ 개의 $i$ 를 골라서 답을 최소화하는 문제를 해결하면 됩니다. $c \geq k$ 인 경우는, $A$ 와 $B$ 를 뒤집어서 동일하게 해결할 수 있습니다.

마지막으로, 위 DP를 slope trick을 사용하여 최적화할 수 있습니다. 모든 $B[i] \geq 0$ 이라고 하고, $T$ 가 충분히 크다고 합시다. 우리의 점화식은 $dp[i][j] = \min(dp[i-1][j-1] + A[i] - B[i], dp[i - 1][j]) + B[i]$ 의 형태인데, 사실 이 때 $dp[i][j]$ 의 값은 $\sum_{k \leq i} B[k] + (A[k] - B[k]$ 중 가장 작은 $j$ 개 합) 과 동일합니다. 즉, $dp[i][j] - dp[i][j-1]$ 의 변홧값은 $A[k] - B[k]$ 로 구성되어 있습니다. 고로 이 경우는 $A[i] - B[i]$ 순으로 원소들을 정렬하는 선에서 쉽게 해결됩니다.

실제로는 $B[i]$ 가 음수일 수 있어 $dp[i][j]$ 의 값이 음수로 떨어졌을 때 $0$ 이상으로 보정해 주어야 하고, $dp[i][j]$ 의 값이 $T$ 를 넘어가면 불가능함도 체크해 주어야 합니다. slope trick에서 함수의 개형은, $dp[i][0] = \ldots = dp[i][k] = m$ 과 같이 첫 $k$ 개 항은 최솟값과 동일하다가, 그 이후부터 convex 하게 함수가 증가하는 꼴을 띕니다. $0$ 이상으로 보정해 주는 것은, $m < 0$ 일 경우 $k$ 를 늘려가며 가장 작은 기울기들을 제거하는 식으로 할 수 있습니다. $T$ 초과를 잘라 주는 것은, 기울기의 합이 특정 수를 넘어가지 않게 가장 큰 기울기들을 제거하는 식으로 할 수 있습니다. 기울기를 std::set 에 관리하면 이 모든 연산들을 $O(n \log n)$ 에 구현할 수 있고, 전체 문제는 $O(n \log n \log X)$ 에 해결됩니다.

CCC 2017 S2. High Tide Low Tide

입력으로 들어온 수열을 정렬한 후, 만조때는 중앙값부터 감소하는 순서대로, 간조일때는 중앙값부터 증가하는 순서대로 출력합니다.

$n = 2k + 1$ 이면: a[k+1] a[k+2] a[k] a[k+3] ... a[2] a[2k+1] a[1]

$n = 2k$ 이면: a[k] a[k+1] a[k-1] a[k+2] ... a[1] a[2k]

VKOShP 2017 A. Tourism

웬만하면 굉장히 큰 답을 찾을 수 있다는 게 핵심 포인트입니다.

만약 $S[1] = S[N]$ 이면 답은 $[1, N-1], [2, N]$ 입니다.

아니면, $S[1] = S[2] = \ldots = S[i]$ 가 만족하는 최대 $i$ 와 $S[N-j+1] = S[N-j+2] = \ldots = S[N]$ 이 만족하는 최대 $j$ 를 찾습니다. 답은 $[i+1, N-1], [i+2, N]$ 혹은 $[1, N-j-1], [2, N-j]$ 입니다.

이보다 더 좋은 답이 존재한다면, 두 구간 모두 $S[1, i], S[N-j+1, N]$ 에 걸치게 될 건데, 그러한 구간 중 길이가 같은 구간에서의 관광지의 개수는 항상 달라질 수 밖에 없습니다. 같은 길이의 구간을 왼쪽에서 오른쪽으로 움직여 보면 항상 관광지의 개수가 1씩 증가할 것이기 때문입니다.

Latin America Regional 2024 B. Biketopia's Cyclic Track

입력으로 주어진 그래프의 DFS 트리를 구합시다. DFS 트리 위에서 각 Back edge는 사이클을 하나씩 유도합니다. 만약 제거한 back edge가 $(u, v)$ 이고, $u$ 의 깊이가 $v$ 의 깊이보다 작다면, $u$ 의 깊이를 최대화하는 back edge가 유도한 사이클을 지웠을 때, 남은 그래프가 여전히 연결되어 있음을 증명할 수 있습니다. back edge에 대응되는 path가 $(p_0 = u) - p_1 - p_2 - \ldots - (p_k = v)$ 일 경우, DFS 트리는 path의 각 정점에 대응되는 컴포넌트들로 분리됩니다. 모든 $p_1, p_2, \ldots, p_k$ 에 대해,

$p_i$ 가 이루는 컴포넌트의 크기가 $1$ 이면, DFS 트리 상 차수가 $2$ 이니, Back edge가 있고, 이 Back edge는 $p_0$ 과 $p_i$ 를 연결합니다. (아닐 경우 $u$ 의 깊이가 최대화되는 back edge라는 가정에 모순입니다.)
$p_i$ 가 이루는 컴포넌트의 크기가 $2$ 이상이면, 해당 컴포넌트의 서브트리 아래에 리프가있습니다. 고로 이 리프에서 나오는 Back edge가 $p_0$ 과 $p_i$ 를 연결합니다.

이제 DFS를 통해서 위에서 설명한 back edge를 찾고 사이클을 출력하면 전체 문제를 $O(n + m)$ 시간에 해결할 수 있습니다.

Ptz Summer 2023 Day7 D. HearthStone

어떠한 수열 $A$ 가 $max(A) \leq mex(A)$ 를 만족한다는 것은 $1, 2, \ldots, max(A)$ 가 모두 등장하는 것과 동치입니다. 다시 말해서, 수열을 정렬했을 때 $A[i] - A[i-1] \le 1$ 이라는 조건이 모든 $i$ 에 대해 만족되면 ($A[0] = 0$ 이라 가정) $A$ 는 $max(A) \leq mex(A)$ 를 만족합니다. 여기서 $O(n^2)$ 시간에 작동하는 DP를 유도할 수 있습니다. 초기 수열 $A$ 와 목표 수열 $B$ 가 있을 때, $B$ 를 얻기 위해 필요한 최소 연산 수는, $A$ 와 $B$ 를 정렬한 후 $\sum |A[i] -B[i]|$ 를 구하는 것이기 때문에, 입력 수열 $A$ 를 정렬해 놓은 후 $0 \leq A^\prime[i] - A^\prime[i-1] \leq 1$ 을 만족하는 수열 $A^\prime$ 을 DP로 열거할 수 있습니다. 이 때의 점화식은 $dp[i][j] = \min(dp[i-1][j-1], dp[i-1][j]) + |A[i] - j|$ 가 됩니다.

이 DP 식은 Slope trick을 사용하여 최적화 할 수 있습니다. $dp[i][*]$ 의 최솟값과, 최솟값을 기준으로 왼쪽 / 오른쪽으로 기울기가 1씩 증가하는 시점들을 priority queue에 관리하면, 수열의 중간값을 관리하는 것과 굉장히 비슷한 방식으로 상태 전이를 간단하게 처리할 수 있습니다. 각 원소를 $O(\log n)$ 시간에 더해줄 수 있어서, 전체 시간 복잡도는 $O(n \log n)$ 이 됩니다.

Ptz Summer 2018 Day8 A. Automorphism

문제에서 제시된 함수를 보통 automorphism 이라고 합니다. 이 글에서도 이와 같은 이름으로 부릅니다.

먼저, 고정된 트리에서 automorphism의 개수를 세는 법을 찾아봅시다. Bottom-up 방식으로 계산합니다. 어떠한 노드 $v$ 의 자식 $w_1, w_2, \ldots, w_k$ 의 서브트리들에 대해, automorphism의 개수를 계산하고 모두 곱해줍니다. 서브트리의 automorphism이 고정되었을 때 $v$ 에서 새롭게 만들 수 있는 조합은, isomorphic한 서브트리들에 대해서 automorphism을 섞어주는 방식입니다. 즉, $v$ 의 서브트리들을 isomorphism에 대해 같은 것들끼리 묶었을 때 나오는 집합이 ${w_1, w_2}, {w_3, w_4}, {w_5, w_6, w_7}, {w_8}$ 와 같다면, 총 $2! \cdot 2! \cdot 3! \cdot 1!$ 가지의 경우로 각 isomorphic한 서브트리들에 대해서 순열을 나열할 수 있고, 나열한 순열대로 automorphism의 치역을 보내주는 방식으로 계산할 수 있습니다.

각 노드 $v$ 에 대해 $value_v$ 를, 각 isomorphic한 서브트리 클래스들의 크기 팩토리얼 곱으로 정의합시다. 즉, 위의 $2! \cdot 2! \cdot 3! \cdot 1!$ 에 대응됩니다. $u$ 를 서브트리로 한 트리의 automorphism의 개수는, $u$ 의 서브트리의 $value_v$ 의 곱과 동일합니다. 고로, tree isomorphism을 해결하면 automorphism도 해결할 수 있습니다.

Tree isomorphism은 다양한 방식으로 해결할 수 있습니다. 이 문제에서는 해시 함수를 써서 해결하고, 구체적으로 다음과 같은 해시 함수를 사용합니다. $X, Y$ 를 적당한 랜덤 수열이라고 하였을 때, $v$ 를 루트로 한 서브트리의 해시 $h_v$ 는

서브트리 크기가 $1$ 일 때 $h_v = Y_d$
아닐 때 $h_v = \prod_{u \in child(v)} (X_d + h_u)$

와 같이 정의됩니다. ($d$ 는 $1$ 번 정점으로부터의 거리입니다). 이러한 해시는 $O(n)$ 에 계산해 줄 수 있으니, 고정된 트리에서 automorphism의 개수는 $O(n \log n)$ 에 계산할 수 있습니다. 사실 isomorphism을 해결하는 해시는 이 외에도 다양하지만, 이 해시 함수가 가장 간단하고, 무엇보다 현재 문제 상황에서 자료구조로 최적화하기 가장 적합합니다. 위에서 소개한 해시의 증명은 rng_58의 블로그에서 찾아볼 수 있습니다.

이제 쿼리 버전을 해결합시다. 중요한 관찰은, 한 정점이 추가되었을 때 바뀔 수 있는 $value_v$ 의 개수가 최대 $O(\log n)$ 개라는 것입니다. 어떠한 정점이 추가되었을 때 $value_v$ 가 바뀌려면, $v$ 는 해당 정점의 조상이어야 하며, $v$ 에서 해당 정점 방향의 간선이 light edge여야 합니다. (heavy edge면 어차피 isomorphic subtree가 없기 때문입니다.) $v$ 에서 조상으로 가는 길에 light edge는 $O(\log n)$ 개이니, $value_v$ 의 총 업데이트 횟수는 $O(n \log n)$ 번입니다.

고로, $value_v$ 의 업데이트 기록을 모두 저장할 수 있으면, 전체 문제는 DFS 오더링을 추가한 세그먼트 트리를 사용하여 $O(n \log^2 n)$ 에 해결할 수 있습니다. 이제 문제는 $value_v$ 의 업데이트 기록을 구하는 것으로 귀결됩니다.

모든 정점 $v$ 에 대해서, $h_v$ 는 처음에 $Y_d$ 이고, 서브트리에 자식이 생기면서 값이 바뀔 것입니다. 각 자식이 추가되면서 $h_v$ 가 어떻게 변화하는지를 Treap에 기록해 둡니다. 이제 각 노드에서 해야 하는 일은

서브트리의 treap을 토대로 $value_v$ 의 변화 기록을 구하기
서브트리의 treap을 합치기

가 있습니다.

가장 큰 Treap을 제외한 모든 다른 treap의 해시 값 변화 기록을 배열로 바꾸어서 정렬합시다. 가장 크지 않은 Treap에 대해서 이벤트들을 순서대로 나열해도 그 개수가 총 $O(n \log n)$ 개 입니다. $value_v$ 의 변화 기록은, 각 이벤트에 대해서 $value_v$ 가 바뀌었는지를 확인하고, 추가적으로 가장 큰 Treap이 majority가 아니면 그 부분의 변화 기록도 시뮬레이션해주면 모두 구할 수 있습니다.

Treap을 합치는 것은, 서브트리 개수 크기의 곱 세그먼트 트리를 만들어서 각 시점의 전체 해시값을 구하면 작은 이벤트에 대해서 $h_v$ 를 구할 수 있고, Treap 안에서 $h_v$ 를 구하는 것은 구간에 $x \leftarrow Ax + B$ 를 적용하는 꼴이라 Lazy Propagation을 사용하면 가능합니다.

전체 시간 복잡도는 $O(n \log^2 n)$ 입니다.

PA 2021. Areny

다항 시간 풀이

먼저 $k = n$ 이라고 가정하고, $y$ 를 고정한 상태에서 $(x, y)$ 가 좋은 쌍인 $x$ 의 개수를 세어 봅시다. 편의상 $(y, y)$ 를 좋은 쌍이라고 정의합니다. 어떠한 정점 $v$ 에 대해서, $v$ 에서 나가는 모든 정점 $w$ 에 대해 $(w, y)$ 가 좋은 쌍이라면, $(v, y)$ 는 무조건 좋은 쌍입니다. 여기서 어떠한 방식으로 배지를 얻어도 해당 배지를 통해서 $y$ 를 풀 수 있기 때문입니다. 이러한 식으로 가능한 좋은 쌍들을 모두 찾으면, 남은 모든 정점에 대해서, $y$ 를 피해갈 수 있는 토큰을 발급할 수 있습니다. 고로, 운이 안 좋을 경우 이러한 토큰들만을 발급받으면 $y$ 를 풀 수 없기 때문에, 위 알고리즘은 모든 좋은 쌍을 찾습니다.

위 알고리즘은 큐 등을 사용하여 $O(n + m)$ 시간에 시뮬레이션할 수 있기 때문에, $k = n$ 의 경우 문제가 $O(n(n+m))$ 정도에 해결됩니다. $k < n$ 인 경우는 $k = n$ 인 경우로 환원이 되기 때문에, 전체 문제는 $O(n^2 (n+m))$ 에 해결됩니다. 일단 한동안은 $k = n$ 이라고 가정하고 문제를 해결합시다.

$k = n$ 인 경우를 효율적으로 해결하기

$y$ 를 고정하지 않은 상태에서 위 시뮬레이션을 반복합시다. 위에서 반복하는 연산의 형태는, "모든 나가는 정점이 특정 조건을 만족하면 나 역시 그 조건을 만족" 과 같은 형태입니다. 목표는, 어떠한 방향성 관계 $R$ 을 만들어서, "$(u, v)$ 가 좋은 쌍" 임과 "$R$ 에서 $u \rightarrow v$ 로 가는 경로가 존재함" 이 동치가 되도록 하는 것입니다. $(u, u)$ 는 항상 좋은 쌍이고, $(u, v), (v, w)$ 가 좋은 쌍이면 $(u, w)$ 가 좋은 쌍이니까, 저러한 관계 $R$ 자체는 항상 존재합니다.

초기에 관계 $R$ 은 $n$ 개의 정점과 $0$ 개의 간선을 이룹니다. 어떠한 노드 $u$ 의 모든 나가는 정점이 $v$ 를 향한다면, $u \rightarrow v$ 로 가는 간선을 $R$ 에 추가합니다. 위 시뮬레이션을 생각해 보면, 좋은 쌍이 형성되는 시점은 나가는 정점의 집합이 하나가 될 때이니, 이 관계 $R$ 은 pseudo-forest를 이룰 것입니다. 일단 사이클을 만들지 않는 선에서 관계를 최대한 채워 봅시다. 어떠한 정점 $u$ 에 대해서, $u$ 에서 나가는 정점이 하나의 컴포넌트에 모여있으며, 이 컴포넌트는 $u$ 를 포함하지 않는다면, $u$ 에서 이 컴포넌트의 LCA 로 향하는 정점을 이어줄 수 있습니다.

이를 반복하다 보면, $R$ 은 directed forest의 형태를 이룰 것이며, forest의 모든 루트 노드들은 두 개 이상의 서로 다른 컴포넌트로 나가는 간선이 있거나, 모든 간선이 자신의 컴포넌트를 향합니다. 전자의 경우는 $u$ 에서 나가는 좋은 쌍이 존재하지 않습니다 (항상 원하는 컴포넌트를 피할 수 있기 때문입니다). 후자의 경우는, 자신의 컴포넌트 상 LCA를 향해서 간선을 이어주는 식으로 사이클을 만듭니다. 더 이상 $R$ 을 확장하는 것이 불가능하고, 위 알고리즘에서 찾은 좋은 쌍은 모두 $R$ 에 표현되기 때문에, 이 알고리즘은 올바릅니다. 고로, $R$ 을 만든 이후 좋은 쌍의 개수는 pseudoforest에서 도달 가능한 정점 쌍의 개수를 세어서 해결할 수 있습니다.

$R$ 을 빠르게 구성하는 것은 두 단계로 이루어집니다. 첫 번째 단계는 $R$ 의 각 컴포넌트를 구하는 것입니다. 각 정점에 대해서, 나가는 정점들의 컴포넌트 인덱스를 std::set 에 저장해 둡시다. 이 집합의 크기가 $1$ 이 되는 순간, 이 정점은 나가는 정점의 컴포넌트와 합쳐집니다. 두 컴포넌트가 합쳐질 때, indegree 합이 작은 쪽의 컴포넌트를 순회하면서, 반대쪽 정점의 컴포넌트 인덱스를 갱신해 줍니다. 이를 구현하면 총 $O(m \log^2 m)$ 시간에 각 컴포넌트를 구할 수 있습니다. 각 컴포넌트는, 루트에서 나가는 정점을 모두 지울 경우 사이클이 존재하지 않습니다 (아니면 루트를 향하는 좋은 쌍이라는 가정에 모순입니다.) 이 그래프를 위상 정렬 순서대로 돌면서, 현재 나가는 정점의 LCA에 새 정점을 추가해주는 식으로 트리를 구성할 수 있습니다. (DAG의 Dominator Tree를 구하는 것과 동치인 연산입니다.)

모든 $k$ 에 대해 해결하기

어떠한 $(u, v)$ 가 주어진 $k$ 에 대해서 좋은 쌍이라는 것은, $u$ 에서 시작하는 모든 경로가 결국은 $v$ 를 만나게 되며, 이 과정에서 번호가 $k$ 초과인 정점을 만나는 경로는 없다는 뜻입니다 (끝점 포함). 만약 번호가 $k$ 초과인 정점을 만나는 경로가 있다면, 이 경로를 따라가다가 $v$ 에 도달하지 못하는 경우가 생깁니다. $f(u, v)$ 를, 관계 $R$ 에 속하는 좋은 쌍 $(u, v)$ 에 대해, $u$ 에서 $v$ 로 가는 길에 도달하게 되는 정점 인덱스의 최댓값으로 정의합시다.$R$ 에 새로운 관계 $(u, v)$ 를 추가할 때, $v$ 는 $u$ 에서 나가는 끝 점들의 LCA로 정의되었습니다. LCA를 계산할 때, $v$ 를 도달하는 (관계 상) 경로의 최댓값도 같이 계산하는 식으로 $f(u, v)$ 를 계산할 수 있습니다.

이 알고리즘의 정당성은 $R$이 트리일 경우 귀납적으로 증명할 수 있으나, $R$ 에 사이클이 있는 경우 증명이 깨지게 되며 반례가 존재합니다. 구체적으로는, 우리가 $R$ 을 구성할 때는 모든 관계가 표현되는지에만 집중했지 $(u, v)$ 로 가는 관계가 있을 때 $u$ 에서 출발해서 "처음으로 막히는" 정점이 정말 $v$ 인지는 신경쓰지 않았습니다. $R$ 이 트리일 경우에는 실제로 처음으로 막히는 정점이 $v$ 이지만, 사이클일 경우 그렇지 않으며 반례가 존재합니다.

일단 반례를 잠시 무시하고 $R$ 에 사이클이 있는 경우에도 앞과 같은 방법으로 pseudotree를 계산합시다. Pseudotree에는 유일한 사이클이 있는데, 이 중 간선의 가중치가 최대인 것을 고르고, 해당 간선의 시작점을 새롭게 루트로 설정합니다. 이후 관계 $R$ 을 다시 계산하면, 이 때의 관계는 "처음으로 막히는" 정점을 제대로 표현해서, $f(u, v)$ 를 앞에서 설명한 대로 계산해도 충분함을 증명할 수 있습니다. 여기서는 이에 대한 증명은 생략합니다.

이제 문제는, 간선에 가중치가 있는 pseudoforest가 주어졌을 때 경로 최댓값이 $k$ 이하인 정점 쌍 개수를 모든 $k$ 에 대해서 세는 문제가 됩니다. 이는 small-to-large 등으로 해결할 수 있습니다. 전체 시간 복잡도 $O(m \log^2 n)$ 에 문제가 해결됩니다.

BOJ 18932. 트리와 쿼리 16

간선 추가가 없는 문제는 Centroid decomposition으로 풀 수 있음이 잘 알려져 있습니다. Centroid decomposition 구조를 간선 추가를 지원하게 관리할 수 있으면, 쿼리는 간선 추가와 상관 없이 똑같이 응답하면 됩니다. 문제는 Centroid decomposition 구조를 간선 추가가 되는 상황에서도 관리하는 것입니다.

Centroid decomposition에서 Centroid를 잡는 이유는, 입력 트리를 절반 이하로 쪼개서 decomposition의 높이를 한정시키기 위함입니다. 따라서, 굳이 정확히 Centroid를 잡을 필요는 없고, 해당 정점을 제거했을 때 최대 크기 서브트리가 원래 트리의 $3/4$ 이하 (혹은 아무 1 미만의 상수) 이기만 해도 Centroid decomposition 구조를 관리할 수 있습니다. 목표는:

간선이 추가되었을 때, 양 쪽 Forest의 Centroid decomposition 구조를 small-to-large 를 사용하여 잘 합쳐주기
이 과정에서 어떠한 centroid가 unbalanced 된다면 (즉, 최대 크기 서브트리 크기가 $3/4$ 를 초과한다면), 다시 일반적인 Centroid decomposition을 사용하여 리밸런싱하기

첫 번째 과정은, 두 포레스트의 Centroid decomposition을 Top-down으로 타고 내려가면서 구현합니다. 항상 작은 포레스트를 큰 포레스트에 합쳐준다는 원리로 진행하면, 큰 포레스트에서 해당 작은 포레스트를 어느 쪽 자식에 붙일 지 등등은 계산할 수 있습니다. 붙여준 이후에는, 큰 포레스트에서 새로 추가된 간선이 있는 방향의 자식으로 타고 내려가면서 재귀적으로 반복합니다. Small-to-large 논리로 $O(n \log^2 n)$ 정도에 구현할 수 있습니다.

두 번째 과정은 단순히 해당 영역의 트리를 전부 찾은 후 일반적인 Centroid decomposition을 구성해 주면 됩니다. 두 번째 과정을 Naive하게 해도 빠른 이유는, 두 번째 과정이 일어나기 위해서는 해당 서브트리에 초기 상태의 상수배의 정점이 추가되어야 합니다. 정점 하나를 추가할 때마다 해당 정점과 그 부모들에 퍼텐셜을 $1$ 씩 추가하고, 두 번째 과정이 일어날 때 마다 퍼텐셜을 서브트리 크기만큼 제거하면, 총 $O(n \log n)$ 의 퍼텐셜이 추가되고 각 퍼텐셜마다 $O(\log n)$ 의 연산을 사용하니 총 시간 복잡도가 $O(n \log^2 n)$ 임을 증명할 수 있습니다. (Map 등을 사용하여 $O(\log n)$ 이 하나 더 붙어도 큰 상관은 없습니다.)

여담으로, 위와 같은 원리를 사용해서 balanced BST를 구현할 수 있고 이를 Scapegoat tree라고 부릅니다. 이 BBST는 평소에는 특별히 밸런싱 연산을 하지 않지만, 편향된 서브트리가 생기면 다시 절반으로 쪼개서 리밸런싱을 진행하는 식으로 BBST를 관리합니다.

2025.01.05 problem solving (0)	2025.01.06
Faker's algorithm (1)	2024.11.18
IOI 2024 Day 2 (0)	2024.09.15
IOI 2024 Day 1 (0)	2024.09.10
IOI 2018 Problem 6. 모임들 (Meetings) (0)	2024.09.02

구사과

티스토리 뷰