문제 링크
- http://icpc.me/18349
풀이
문제를 천천히 읽어보면 문제를 풀기 위해 필요한 작업은 쉽게 알 수 있고, 이 작업들을 효율적으로 처리하는 것이 문제의 핵심입니다. 구체적으로, 다음과 같은 작업을 빠르게 수행해야 합니다. 각각의 개념을 모두 설명하는 것은 너무 어렵기 때문에, 문자열 파트를 제외한 다른 부분은 필요한 알고리즘과 설명 링크로 대신하겠습니다.
- Voronoi Diagram
- Minimum Spanning Tree
- Path Maximum Query on Dynamic Tree
- Nearest Point Search
- Longest Common Substring Query (Offline)
보로노이 다이어그램은 Fortune’s Algorithm을 이용해 $O(N \log N)$에 구할 수 있습니다. (설명, 코드)
보로노이 다이어그램의 듀얼 그래프는 들로네 삼각분할이므로 $O(N \log N)$에 들로네 삼각분할을 구해도 됩니다.
이 문제에서 최소 스패닝 트리를 만들 때, 한 정점에서 시작해 트리 하나를 유지하는 방식으로 만들기 때문에 Prim’s Algorithm을 사용해야 합니다. 들로네 삼각분할(평면 그래프) 상의 간선만 사용하기 때문에 $O(N \log N)$에 구할 수 있습니다.
다이나믹 트리에서 경로의 최댓값은 링크컷 트리를 이용해 amortized $O(\log N)$에 구할 수 있습니다. (설명&코드)
가장 가까운 점을 찾는 것은 보로노이 다이어그램에서 스위핑을 해도 되고, k-d tree를 사용해도 됩니다. (설명&코드)
평면을 쪼갤 때 반평면으로 쪼개면 주어진 점의 좌표가 작고 쿼리로 주어지는 점의 좌표가 클 때 시간 초과가 발생합니다. 반평면이 아닌 직사각형으로 쪼개야 시간 초과를 피할 수 있습니다. (thanks to @jh05013)
문자열 (최장 공통 부분 문자열 쿼리)
일반적으로 두 문자열 $S, T$의 최장 공통 부분 문자열을 찾는 것은 $S+T$의 LCP 배열을 구한 다음, $T$의 모든 접미사에 대해 LCP 배열 상에서 가장 가까운 $S$의 접미사까지의 구간 최댓값을 구하면 됩니다. 투포인터를 이용하면 $O(\vert S\vert + \vert T\vert)$ 시간에 구할 수 있습니다.
고정된 $S$에 대해 $T_i$와의 최장 공통 부분 문자열을 찾는 것도 $S+T_1+T_2+\cdots+T_k$에서 비슷한 방식으로 할 수 있습니다. LCP 배열을 구하는데 $O(\vert S\vert + \sum \vert T_i\vert)$, 쿼리는 각각 $O(\vert S\vert +\vert T_i\vert)$에 처리할 수 있으므로 전체 시간 복잡도는 $O(k\vert S\vert + \sum \vert T_i\vert)$입니다.
만약 $\vert S_i\vert < \vert S_j\vert$일 때 쿼리를 $O(\vert S_i\vert)$에 처리할 수 있다면, 문제에서 요구하는 $Q$개의 쿼리를 $O((Q+S)\sqrt S)$에 모두 처리할 수 있습니다. 이때 $S = \sum\vert S_i\vert$입니다.
먼저, $S_1+S_2+\cdots+S_n$의 LCP 배열을 $O(S)$에 구합시다. 세 가지 경우로 나눠서 처리합니다.
- $\vert S_i\vert,\ \vert S_j\vert \leq \sqrt S$
- 투포인터를 이용해 각 쿼리를 $O(\vert S_i\vert+\vert S_j\vert)$에 처리할 수 있습니다. 이 케이스는 최대 $Q$번 발생하고, $\vert S_i\vert,\ \vert S_j\vert \leq \sqrt S$이므로 전체 시간 복잡도는 $O(Q\sqrt S)$입니다.
- $\vert S_i\vert \leq \sqrt S,\ \vert S_j\vert > \sqrt S$
- 길이가 $\sqrt S$보다 긴 문자열은 최대 $\sqrt S$개 존재합니다. 그러므로 접미사 배열에서 $S_j$의 접미사의 위치를 모았을 때, 임의의 지점에서의 lower bound를 $O(S\sqrt S)$에 모두 전처리할 수 있습니다.
- 전처리된 lower bound를 이용하면 쿼리를 $O(\vert S_i\vert)$에 처리할 수 있고, $\vert S_i\vert \leq \sqrt S$이므로 전체 시간 복잡도는 $O(Q\sqrt S)$입니다.
- $\vert S_i\vert,\ \vert S_j\vert > \sqrt S$
- (2)에서 전처리된 배열을 사용하면 쿼리를 $O(\vert S_i\vert)$에 처리할 수 있습니다.
- 길이가 $\sqrt S$보다 긴 문자열은 최대 $\sqrt S$개 존재하므로, 서로 다른 $(i, j)$ 순서쌍은 최대 $(\sqrt S)^2 = S$개 존재합니다. 전체 시간 복잡도는 $O(S\sqrt S)$입니다.
- 쿼리 결과를 캐싱해야 합니다.
접미사 배열과 LCP 배열을 선형 시간에 구하고, 구간 최댓값 쿼리를 선형 시간 전처리 + 상수 시간에 처리하면 $O(Q+S\sqrt S)$에 모든 쿼리를 처리할 수 있습니다.
Suffix Automaton을 사용해도 동일한 시간 복잡도로 쿼리를 처리할 수 있습니다. ($S$의 suffix automaton을 만드는데 $O(\vert S\vert)$가 걸리고, $T$와의 최장 공통 부분 문자열을 구하는데 $O(\vert T\vert)$가 걸립니다.)
설명 링크 모음