2024.06.09 problem solving

2021.??.?? problem solving이라고 적혀 있는 글이었습니다. 정확히 이 때 이 글을 왜 적었는지는 기억이 안 납니다. 당시에 문제를 몇개 더 풀어서 다른 글과 함께 올리려고 했었는데, 많이 미뤄지기도 했고, 그 문제들은 따로 올리는 게 좋을 것 같아서 그냥 올립니다.

9월까지 알고리즘 글이 최소 5개는 더 올라올 것으로 예상됩니다.

AMPPZ 2019 C. Polygon

수열 $a_1, a_2, \ldots, a_n$ 을 가지고 볼록 다각형을 만들 수 있을 조건은, 가장 긴 변을 제외한 변들의 길이 합이 가장 긴 변보다 길면 됩니다. 수열을 정렬한 후, 가장 긴 변을 $i$ 번이라고 합시다. 그보다 작은 변들은 합만 특정 수 이상이 되면 되니까, 그냥 전부 골라주면 됩니다. 고로 $1 \ldots i-1$ 번 변 의 길이 합과 $i$번 변의 길이를 비교해 부면 됩니다. 이는 왼쪽에서 오른쪽으로 수열을 순서대로 읽으면서 길이 합을 변수에 저장하는 식으로 가능합니다.

JOI Spring Camp 2021 Day 2 A. Escape Route

쿼리의 결과가 하루를 넘어가는 경우에는 문제가 첫 새벽을 기점으로 분리된다. 다음과 같은 두 값을 계산하자.

• 새벽 전에 $i \rightarrow j$ 로 이동하기 위한 최소 출발 시간
• 새벽 이후 $i \rightarrow j$ 로 이동하기 위한 최단 시간

이 값은 $N$ 번의 Dijkstra로 총 $O(N^3)$ 에 계산할 수 있고, 계산 후에는 각 쿼리를 $O(N)$ 에 해결할 수 있다.

쿼리의 결과가 하루 안에 들어오는 경우가 어렵다. 경로를 고려할 때, $T$ 시간에 출발하지 않고 가능한 가장 늦게 출발한다고 하자 (이보다 일찍 출발해도 경로는 여전히 유효하니). 결국 우리가 고려해야 할 최단 경로에서는, 1초 뒤에 바로 파괴되는 간선이 항상 존재한다고 가정할 수 있다. 이러한 간선을 critical edge라고 정의하자.

시작점에 가장 가까운 Critical edge는 항상 존재하며 유일하다. 거꾸로, Critical edge를 고정하고 최단 경로를 나열해 보자. Critical edge $e$ 를 고정하고, 시작점에서는 역방향, 끝점에서는 정방향으로 Dijkstra를 돌리면, $i \rightarrow e \rightarrow j$ 로 가는 경로가 무너지는 시간, 그리고 경로를 따라 가는 데 걸리는 시간을 알 수 있다. 이렇게 하면 $M$ 번의 다익스트라로 유효한 경로를 전부 나열할 수 있다. 경로의 개수는 $O(MN^2)$ 이고, 정렬을 하게 되면 $O(MN^2 \log N)$ 이다. 이를 구현하면 BOJ에서는 AC, oj.uz에서는 TLE가 나게 된다. (실제 대회에서는 TLE가 났을 것이라 본다.)

정렬을 하지 않기 위한 핵심 관찰은, 경로가 무너지는 시간의 서로 다른 경우의 수가 $O(N^3)$ 라는 것이다. 긴 설명은 생략하지만, 적절한 열거 방식으로 정렬 없이 문제를 해결할 수 있다. 사실 어느 정도의 Cache oblivious함도 필요해 보이는데, 쿼리를 오프라인으로 받은 후 귀찮은 정렬을 하면 큰 도움이 되는 것 같다.

BOJ 18544. Incomparable Pairs

$u, v$ 가 모두 $S$ 의 부분 문자열이면서 하나가 다른 하나의 부분 문자열인 경우를 세어 봅시다. $D(S)$ 를 $S$ 의 서로 다른 부분 문자열 집합이라고 하면, 그러한 경우의 수는 $X = \sum_{s \in D(S)} |D(s)|$ 로 표현할 수 있습니다. 문제의 답은 $\frac{|D(S)|(|D(S)| + 1)}{2} - X$ 이니, 결국 $X$ 를 빠르게 세는 문제로 생각할 수 있습니다.

문자열 $S$ 가 주어졌을 때 $|D(S)|$ 의 개수는 $O(n)$ 에 세는 방법이 여럿 알려져 있습니다. 예를 들어 Suffix Array, Suffix Automaton, Suffix Tree를 사용할 수 있습니다. 이러한 자료구조를 사용하면 전체 문제를 $O(n^3)$ 에 해결하는 알고리즘을 얻을 수 있습니다. 아직은 문제를 해결하기에 충분하지 않은 복잡도입니다.

이 문제에서 활용할 수 있는 성질은 구하고자 하는 $|D(S)|$ 가 모두 고정된 문자열의 부분 문자열이라는 것입니다. 잠시 문제를 바꿔 $(i, j)$ 가 쿼리로 주어질 때 $D(S[i\ldots j])$ 를 빠르게 구하는 자료구조를 구성하는 문제를 풀어 봅시다. Suffix tree를 $O(n)$ 에 구성하면, $S$ 의 모든 문자열을 표현하는 자료 구조를 얻을 수 있습니다. 각 쿼리를 $j$ 가 증가하는 순으로 정렬한 후 해결해 봅시다. 길이 $j - 1$ 의 Prefix를 길이 $j$ 의 Prefix로 확장할 때 다음과 같은 연산을 처리하면 됩니다.

• $j$ 에서 끝나는 모든 부분 문자열을 나열합니다.
• 해당 부분 문자열의 마지막 등장 위치 를 $j$ 로 갱신합니다.

이후 (마지막 등장 위치) - (길이) + 1 이 $i$ 이상인 부분 문자열의 개수를 각 쿼리마다 세어주면 이 문제를 해결할 수 있습니다.

Suffix tree를 조금 더 명시적으로 사용해서 위 과정을 표현해 봅시다. 편의상 뒤집은 문자열의 Suffix tree를 기준으로 설명합니다. Suffix tree에서 길이 $j$ 의 prefix에 대응되는 노드에서 시작해서 나이브하게 부모 쪽으로 올라가면, 최대 $O(n)$ 개의 간선을 만나게 됩니다. 각 간선의 마지막 등장 위치는 같으며, 연속한 구간의 길이를 표현합니다. 고로 이 간선의 마지막 등장 위치를 갱신하는 것은 (마지막 등장 위치) - (길이) + 1 이 $i$ 이상인 부분 문자열의 개수 $cnt[i]$ 에 구간 업데이트를 하는 것과 동일합니다. $cnt[i]$ 를 세그먼트 트리 등으로 관리하면, 이를 $O(n^2 \log n)$ 에 처리할 수 있습니다. 처리 이후 각 쿼리를 처리하는 것은 $O(\log n)$ 시간이 걸립니다.

시간에 병목이 걸리는 것은 Suffix tree를 나이브하게 타고 올라가면서 새로운 값을 배정해 주고, 값의 차이만큼 구간을 옮겨주는 과정 때문입니다. 이는 일반적인 트리 자료구조 문제를 해결하듯이 최적화 할 수 있습니다. Suffix tree에 대한 Heavy-light decomposition을 구성하면 위 문제를 전부 배열에 대한 문제로 생각할 수 있습니다.

배열에서 이 문제는 어떠한 Prefix에 대해서 새로운 값을 칠하고, 그 과정에서 갱신된 구간들을 모두 찾는 형태의 문제가 됩니다. 각 배열에 대해서 스택을 만들어서, 현재 어떠한 Prefix에 어떠한 값이 칠해졌는지를 관리합니다. 스택의 위에 있을 수록 더 작은 Prefix에 대해 칠해졌고, 더 최근에 칠해졌다는 조건을 만족합니다. 새로운 값을 칠하게 될 때, 현재 길이보다 작은 Prefix에 대해 칠한 것들을 모두 스택에서 뽑아주고, 그 다음 주어진 Prefix에 대해서 칠한다는 것을 스택에 넣어주면 됩니다. 이 과정에서 갱신된 색들은 모두 $cnt[i]$ 에 대해 구간 업데이트를 하면서 관리합니다. 각 Prefix마다 총 $O(\log n)$ 개 의 배열에 대해 이러한 업데이트를 하니, 전체 구간으로 보았을 때 $O(n \log n)$ 개의 업데이트가 됩니다. $cnt[i]$ 를 효율적으로 관리만 하면 전체 문제를 풀기 충분한 정도입니다.

$X = \sum_{s \in D(S)} |D(s)|$ 를 구하는 원래 문제로 넘어갑시다. Suffix Automaton을 사용하면, $j-1$ 까지의 문자열을 처리했을 때, 뒤에 $j$ 번 문자가 들어오게 되면서 새롭게 얻게 되는 부분 문자열이 몇 개인지를 계산할 수 있습니다. 이러한 문자열이 $t$ 개라고 하면, 각 $j$ 가 답에 기여하는 바는

$\sum_{1 \le i \le t} \sum_{k = i}^{j} cnt[k] = \sum_{1 \le i \le j} min(i, t) cnt[i]$

가 됩니다. 즉, 다음과 같은 자료구조가 필요합니다:

• 구간에 $cnt[i] = cnt[i] + v$ 처리
• 구간에서 $cnt[i]$ 합 계산
• 구간에서 $i \times cnt[i]$ 합 계산

이는 모두 Lazy propagation을 사용한 세그먼트 트리로 처리할 수 있습니다. 해당 세그먼트 트리에 최대 $O(n \log n)$ 번 쿼리를 물어보니 전체 시간 복잡도는 $O(n \log^2 n)$ 이 됩니다.