2021.05.31 problem solving

사실 지금 쓰고 있는 글이 더 있긴 한데 일단 이 정도만 공개합니다.

USACO FEB20 Silver. Triangles

일반성을 잃지 않고, 빗변이 직각 모서리의 우상향에 존재한다고 가정하자. 다른 방향들은 점들을 축에 대칭시킨 후 똑같이 해보면 된다.

직각인 점 $(x_1, y_1)$ 를 하나 고정시켰다면, 우리가 원하는 것은 이 점의 위에 있는 점 $(x_1, y_2)$ 과 오른쪽에 있는 점 $(x_2, y_1)$ 을 골라서 $(x_2 - x_1) (y_2 - y_1)$ 을 모두 합하는 것이다. 이 때 곱해지는 두 항이 독립이기 때문에, 모든 가능한 $(x_2 - x_1)$ 을 합하고, $(y_2 - y_1)$ 을 합한 후 이 값을 곱해줘도 된다.

이렇게 되면, 모든 점에 대해서 이 점 위에 있는 점들의 $y$ 좌표 합, 이 점 오른쪽에 있는 점들의 $x$ 좌표 합을 계산하면 된다. 각 점들을 $(x, y)$ 그리고 $(y, x)$ 순으로 정렬하고, $x$ 혹은 $y$ 좌표가 같은 점들만 모아서 합을 관리해 주는 식으로 이 정보를 모든 점에 대해 구해줄 수 있다.

USACO FEB20 Platinum. Equilateral Triangles

어떠한 점과 거리 $d$ 에 있는 점들을 그려보면 넓이가 $2d^2$ 인 다이아몬드 형태로 점들이 분포함을 알 수 있다. 두 점을 고정시키고 다이아몬드를 그려가며 다른 점의 위치를 찾아 보자. 특수 케이스를 제외한 대부분의 경우, 세 번째 점은 두 점 중 하나와 같은 대각선 ($x+y$ 혹은 $x-y$ ) 에 속함을 알 수 있다. 특수 케이스는 두 점이 같은 대각선에 속할 때 발생하기 때문에, 결국 우리가 찾는 점 쌍에서 2개의 점은 하나의 대각선에 속한다. 이러한 점 쌍은 $O(N^3)$ 개 있다.

하나의 대각선에 속하는 점 두개를 고정하면, 다른 점이 있을 수 있는 위치는 어떠한 대각선 형태의 선분 위이다. 우리는 이 선분 안에 몇 개의 점이 있는 지 세어야 하는데, 대각선 사선을 따라서 부분합 배열을 만들면 이를 $O(1)$ 에 셀 수 있다.

마지막으로 문제가 되는 것은, 세 번째 점 역시 첫번째 혹은 두번째 점과 같은 대각선에 속할 경우이다. 즉, 어떠한 점을 기준으로 ^ v < > 와 같은 형태의 직각삼각형이 생겼음을 뜻한다. 직각삼각형의 개수는 $O(N^3)$ 에 쉽게 셀 수 있으니, 따로 세 주고 중복해서 센 횟수만큼 빼 주자.

USACO OPEN20 Platinum. Circus

상태 중에서 모든 새들이 ${1, 2, \ldots, K}$ 번 정점에 위치하고 있는 상태만을 생각합시다. 임의의 상태에서 그러한 상태로 변환할 수 있습니다. 이 경우 어떠한 두 새는 적절한 연산을 통해서 둘 간의 위치를 바꿀 수 있고, 다른 새는 위치를 바꿀 수 없을 것입니다. 이 위치를 바꿀 수 있는 관계는 추이적 (transitive) 한 성질을 띄기 때문에, 이 관계를 어떻게 알아낸다면 연결 컴포넌트를 구해서 문제를 해결할 수 있습니다. (사실은 그렇지 않습니다: 위치를 바꾸는 것의 연속으로 표현되지 않는 완전히 새로운 연산이 등장해서 새들의 위치를 아예 바꿀 수도 있기 때문입니다. 필자가 알고 있는 이에 대한 엄밀한 증명은 없고, 직접 증명을 다수 시도했으나 모두 실패했습니다. 고로 이 사실에 대한 증명은 생략합니다. 실제로 시행착오를 거쳐 보면, 직관적으로 별로 말이 되지 않음을 알 수 있습니다.) 각 연결 컴포넌트의 크기가 $c_1, c_2, \ldots, c_m$이라면, 답은 $\frac{K!}{c_1!c_2!\ldots c_m!}$ 이 됩니다.

한 가지 알 수 있는 사실은, 두 새가 바꾸는 것을 막는 장치는 차수 2의 노드들로 구성된 긴 path라는 것입니다. 만약에 트리 전체가 하나의 긴 path라면, 답은 항상 $K!$ 입니다. 하지만, 트리에 차수 2인 노드가 없는 경우, $K \le N - 3$ 일 경우 항상 답이 1이 됩니다. 증명은 다음과 같습니다: 일반성을 잃지 않고 $1 \ldots K$ 번 정점의 induced subgraph가 연결되어 있다고 할 때, 이 induced subgraph에서 인접한 두 노드를 항상 스왑할 수 있습니다. 다른 새들을 두 노드 $u, v$ 에서 가능한 멀리 배정하고 다음과 같이 케이스를 나눠서 각 케이스를 증명하면 되는데, 각각에 대한 증명은 어렵지 않아 케이스만 나누고 설명은 생략합니다.

• Case 1. $u, v$ 중 한 정점에 두 개의 빈 노드가 인접.
• Case 2. $u, v$ 중 한 정점에 하나의 빈 노드가 인접하고, 다른 한 정점에 하나의 빈 노드가 인접하며 그 노드에 또 다른 빈 노드가 인접.
• Case 3. $u, v$ 중 정확히 한 정점에만 세 개의 빈 노드로 이루어진 컴포넌트가 인접.

이제 Path가 새들을 떼어놓는 역할을 함을 눈치챘으니, 하나의 Path가 정확히 어떠한 식으로 새들을 떼어놓는지 확인해 봅시다.

두 정점 $u, v$ 를 잇는 path $p$ 를 생각해 봅시다. $u, v$ 의 차수는 2가 아니며, $u, v$ 를 제외한 $p$ 상의 모든 노드의 차수는 2입니다. $v$ 를 루트로 했을 때 $u$ 의 서브트리의 크기를 $a$ 라고 하고, $u$ 를 루트로 했을 때 $v$ 의 서브트리의 크기를 $b$ 라고 합시다. 모든 새들을 $p$ 에서 가능한 멀리 보내도록 합시다. (만약 자리가 없다면 $p$ 에 새들이 있어도 괜찮습니다.) 이 때, 만약 $p$ 위에 새들이 있다면, 즉 $K \geq a + b - 2$ 라면, $u$ 를 제외한 $u$ 의 서브트리에 있는 노드들, $v$ 를 제외한 $v$ 의 서브트리에 있는 노드들, 그리고 그 사이에 있는 새들은 서로간의 위치를 바꿀 수 없습니다. 즉, $u$ 밑에 있는 서브트리를 하나의 큰 정점으로 묶고, $v$ 밑에 있는 서브트리를 하나의 큰 정점으로 묶을 경우 일종의 경로와 같은 모양을 한다는 것입니다. 이제 모든 스왑 가능한 쌍은 $u$ 나 $v$ 밑에 있는 "큰 정점" 간에만 존재 가능하며, 그 밖은 각각의 컴포넌트를 이룹니다. 이것을 반복하여서 모든 새들을 서로 다른 집합으로 분리하는 것을 반복하면, 원하는 연결 컴포넌트를 찾을 수 있습니다. (여기까지 내려오는 긴 설명 역시 전부 엄밀한 증명이 필요한 사실이나, 위와 비슷한 이유로 실패하였기 때문에 생략합니다.)

이제 고정된 $K$ 에 대해서, bottom-up으로 이 컴포넌트를 만들어 나갑니다. 위에서 설명한 긴 경로들을 하나의 간선으로 축약합시다. $dp[v]$ 를, $v$ 의 서브트리에 고립된 컴포넌트에 속한 새의 수 합이라고 합시다. 사실 긴 경로가 존재하기 때문에 정확한 정의는 아닙니다. $v$ 의 서브트리에다가 $v$ 에서 $v$ 의 부모로 가는 경로까지 더했다고 보시면 됩니다. 이 때 $v$ 의 부모는 포함하지 않습니다.

두 가지 경우가 있습니다.

• $v$ 와 $v$ 의 부모로 올라가는 노드가 $K \geq a + b - 2$를 만족하지 않는다면, 여기서 특별히 고립되는 새로운 새는 없으니, 자식의 DP 값의 합을 올려주면 됩니다.
• 그렇지 않다면 이 노드의 서브트리에서 $b - 1$ 개의 노드가 분열됩니다. 이미 고립된 새들을 제외한 새들은 컴포넌트를 형성하니, 여기서 만들어 주면 됩니다. 이 노드의 위에서는 $a - 1$ 개의 노드가 따로 고립되었으니, 서브트리 아래에 $K - (a - 1)$ 개의 노드가 고립되었다고 생각할 수 있습니다.

이는 각 $K$ 에 대해서 $O(N)$ 시간에 구현할 수 있어서 $O(N^2)$ 알고리즘이 됩니다. $v$ 의 부모가 항상 정의되어야 하기 때문에 루트는 리프 정점으로 잡아야 합니다.

위 $O(N^2)$ 알고리즘을 실행했을 때, $K \geq a + b - 2$ 가 성립하는 경우는 총 $O(N)$ 번 밖에 없습니다. 이유는, $a + b - 2 = N - len(p) - 1$ 이기 때문에, 한 노드에 대해서 $K$ 가 충분히 커지는 경우는 $len(p) + 1$ 번 밖에 없고 이를 전체 트리에 대해서 합하면 $O(N)$ 이기 때문입니다. 해당 식이 성립하지 않는 경우에 DP 값은 단순히 자식의 값의 합이 되고, 성립하는 경우에는 이에 특정 수가 더해진 것으로 볼 수 있습니다.

이제 축약된 트리를 DFS ordering으로 관리한 후 Fenwick tree로 DP 값을 관리합시다. 일반적인 경우 DP 값의 합은 서브트리에 있는 DP 값의 합이 됩니다. 그렇지 않은 경우는 $K - (a - 1)$ 이 DP 값이 되는데, 현재 서브트리의 합에서 고립된 새들을 제외한 새의 개수를 셀 수 있습니다. 이를 토대로 해당 위치에서 DP 값이 기존 서브트리 합에서 얼마나 벗어났는지를 Fenwick tree에 갱신해 주면, 이후 부모에서 해당 서브트리를 볼 때 값의 합이 $K - (a - 1)$ 이 됩니다. 이 과정에서 생긴 컴포넌트의 크기 역시 구할 수 있습니다. 고로 각 $K$ 에 대해서, $K \geq a + b - 2$ 를 만족하는 노드의 개수에 비례하는 만큼의 Fenwick tree 호출로, 문제의 정답을 구할 수 있습니다. 최종 시간 복잡도는 $O(N \log N)$ 입니다.

BOJ 20536. 남부순환로

문제에서 원하는 올바른 설치의 조건은 다음과 같습니다.

• 도로의 시점과 첫 가로등 사이에 최대 1개의 빈 블록이 존재할 수 있다.
• 인접한 가로등 사이에 최대 2개의 빈 블록이 존재할 수 있다.
• 마지막 가로등과 도로의 종점 사이에 최대 1개의 빈 블록이 존재할 수 있다.

$K = 1$ 인 경우에는 최솟값만 찾으면 됩니다. 이 경우에는 DP로 문제를 해결할 수 있습니다.

$DP[i][j] = $ ($i$ 번 블록까지 설치 여부를 정했으며, 이 셀 뒤에 $j$ 개의 빈 블록이 들어오는 것이 허용되었을 때의 최적해) 라고 상태를 정의합시다. $i + 1$ 번 셀에 블록을 설치하는 지 여부에 따라서 최대 2개의 새로운 상태로 전이됩니다. 초기 상태는 $DP[0][1]$ 이며 (빈 블록이 하나 가능) 최종 상태는 $DP[N][1], DP[N][2]$ 입니다 (빈 블록 설치 기회를 두번 사용하는 것은 금지).

여기서, DP의 상태 전이는 DAG (Directed Acyclic Graph) 를 이룹니다. $K = 1$ 일 때 우리가 원하는 것은 이 그래프의 최단 경로입니다. 더 나아가서, 우리가 위에서 설계한 DP에서는 각 경로가 가로등을 올바르게 설치하는 경우의 수에 일대일 대응됨을 알 수 있습니다. 편의상, $(N, 2) \rightarrow (N, 1)$ 로 가는 가중치 0의 간선을 만들어서 시작점과 끝점을 고정시킵시다. 상태 $(0, 1)$ 에서 상태 $(N, 1)$ 로 가는 경로 중 $K$ 번째 최단 경로를 찾으면 됩니다. 이는 Dijkstra's algorithm을 약간 변형하면 $O(NK \log N)$ 에 할 수 있으나, 느립니다.

$S$ 를 시작점, $E$ 를 끝점이라고 합시다. $E$ 를 루트로 한 최단 경로 트리 $T$를 잡습니다. 모든 간선은 $E$ 를 방향으로 움직이며, 각 정점의 거리는 해당 정점에서 $T$ 번 정점까지의 최단 경로의 길이입니다. 즉, 일반적으로 하는 $S$ 에서 뻗어 나가는 최단 경로 트리의 반대라고 볼 수 있습니다.

$S - E$ 경로를 단순하게 관리할 경우 길이가 매우 길어질 수 있습니다. 하지만 우리가 관심 있어하는 대부분의 경로는 $T$ 의 간선들을 많이 벗어나지 않습니다. 이 점을 활용하여, 경로의 Canonical Form 을 찾을 것입니다.

트리에 없는 간선 $e \in G - T$ 에 대해서 이 간선을 대체 간선 으로 썼다는 것은, 최단 경로가 $start(e)$ 정점을 만나게 되면 $e$를 따라 가고, $end(e)$ 에 도달함과 동시에 다시 최단 경로 트리를 통해서 $T$ 로 간다는 것을 뜻합니다. 최단 경로는 대체 간선이 아예 없을 것입니다. 두 번째 최단 경로는 대체 간선을 정확히 하나만 사용합니다. (두 번째 최소 스패닝 트리랑 비슷합니다.)

이걸 Canonical Form으로 잡읍시다. $S - E$ 경로 $P$ 상에서 $T$ 에 존재하지 않는 간선을 등장 순서대로 $sidetracks(P) = [e_1, e_2, \ldots, e_k]$ 라고 정의합니다. 다음과 같은 성질이 성립합니다.

• $sidetracks(P)$ 가 정해지면 이에 따라서 $P$ 를 유일하게 복구할 수 있다: $S$ 에서 시작해서 $e_1$ 의 시작점을 만날 때까지 움직이고, 움직이면 $e_1$ 을 타고.. 를 반복한다. $sidetracks(P) = S$ 일 때, $path(S) = P$ 라고 하자.
• 모든 경로 $P$ 에 대해서 $sidetracks(P)$ 가 정의된다. 하지만, $G - T$ 에 속하는 원소로 구성된 임의의 간선 수열 $S$ 에 대해서 $path(S)$ 가 정의되지 않을 수 있다. 1번 항목의 알고리즘이 잘 작동해야만 정의된다.
• $delay(e_i)$ = $dist_T(end(e_i)) - dist_T(start(e_i)) + weight(e_i)$ 라고 정의하자. 이는 $e_i$ 를 탔을 때 최단 경로 길이가 얼마나 증가하는 지를 뜻한다. 이 때 $delay(e_i) \geq 0$ 이며, $P$ 의 길이는 (최단 경로 길이) + $\sum_{e \in sidetracks(P)} delay(e)$ 이다.

마지막 조건이 아주 이상적입니다. 각 에지가 최단 경로에 방해하는 기여도가 독립적이기 때문입니다. 이제 다음과 같은 탐색 트리를 정의합니다. 탐색 트리의 각 노드는 서로 다른 sidetrack에 대응됩니다.

• 루트 노드는 빈 수열이다.
• 어떠한 노드 $[e_1, e_2, \ldots, e_k]$ 에 대해서 해당 노드의 부모는 $[e_1, e_2, \ldots, e_{k - 1}]$ 이다. 즉, 어떠한 노드의 자식은 sidetrack의 뒤에 올바른 대체 간선을 추가한 경우들이 된다.
• 이 트리는 모든 가능한 sidetrack 수열을 열거하고 있다 (무한할 수 있음).
• 이 트리는 Heap이다. (부모 노드의 값이 자식 노드의 값 이하이다.)

이 트리를 탐색할 수 있다면, 루트에서 타고 내려가면서 현재 보이는 자식 중 가장 가중치가 낮은 것을 $k$ 번 반복해서 찾으면 됩니다.

이제 이 트리를 탐색해봅시다. 루트 노드는 빈 수열이니, Priority queue에 빈 수열을 넣습니다. 현재 보고 있는 노드의 sidetrack이 $[e_1, e_2, \ldots, e_k]$ 라고 하면, $e_{k + 1}$ 의 조건은, $start(e_{k + 1})$ 이 $end(e_k)$ 의 조상이어야 한다는 조건입니다. 고로, $O(KM\log M)$ 풀이는, $end(e_k)$ 에서 트리를 일일이 위로 타고 올라가면서, 각 노드에서 시작하는 대체 경로들을 모두 우선순위 큐에 넣는 것입니다.

이를 최적화하기 위해서는, 어떠한 노드 $v$ 에 대해서, $v$ 와 그 조상에서 시작하는 모든 대체 노드들을 $delay(e)$ 의 크기 순으로 잘 나열한 자료 구조가 필요합니다. 조상의 값을 빌려서 자식의 값을 형성하는 것은 일반적으로 Persistent한 자료구조를 통해서 해결할 수 있습니다. Leftist Heap, Randomized Meldable Heap 등을 Persistent하게 구현하면 됩니다. Persistent Heap을 구성하였다면, Heap의 루트 포인터를 넣고 우선순위 큐로 단순하게 탐색해주면 됩니다.

여담으로, 이상의 작업은 Persistent Segment Tree로도 할 수 있으나, 이때는 구현이 약간 복잡해집니다.

시간 복잡도는 $O(N \log N + K \log K)$ 입니다.

BOJ 17937. 수열과 쿼리 34

수열 $A$ 는 쿼리를 통해서 변경할 수 있으나, 수열 $B$ 는 초기 입력으로 주어진 후 변하지 않습니다. 3번과 4번 종류의 쿼리는, 수열 $B$ 만 알면 풀 수 있습니다. 이 두 쿼리를 해결해 봅시다.

• 3번 쿼리는 수열 $B$ 의 LCP를 빠르게 찾는 문제로, 잘 알려진 문제입니다. $B$ 에 대해서 Suffix array를 만들면 해결할 수 있습니다.
• 4번 쿼리 역시 비슷한 형태의 문제가 잘 알려진 편입니다. $B[i - (q - p) - 1 \ldots i + (r - s)]$ 가 $B[p \ldots q] + B[r \ldots s]$ 에 대응된다고 합시다. $B[i \ldots i + (r - s)] = B[r \ldots s]$ 인 $i$ 는, suffix array에서 $r$ 과의 LCP가 $s - r + 1$ 이상인 접미사들로 표현할 수 있습니다. 고로 이들은 $B$ 의 Suffix array에서 구간을 이룹니다. $B[p \ldots q]$ 도 비슷한데, 여기서는 $B$ 를 뒤집은 문자열의 SA 상에서 구간을 이룬다는 점이 차이입니다. ($i$ 의 $SA(B)$ 상 위치, $i$ 의 $SA(B^R)$ 상 위치) 를 점으로 표현하면, 결국 문제는 2차원 직사각형 안에 점이 있는지를 판별하는 문제가 되어서 Persistent Segment Tree로 on-line에 해결 가능합니다. PST를 사용할 시 온라인일 뿐만 아니라, 답이 되는 실제 $i$ 가 무엇인지 역시 알 수 있습니다.

3, 4번 쿼리는 언뜻 보았을 때 1, 2번 쿼리와 전혀 상관이 없어 보입니다. 그래서 완전히 다른 두 문제가 합쳐졌다고 생각할 수 있지만, 사실은 1, 2번 쿼리를 해결하는 데 3, 4번 쿼리가 중요한 역할을 합니다.

일단 업데이트가 없다고 가정하고, 2번 쿼리만 해결해 봅시다. 초기 전처리 단계에서, 수열 $A$ 를 앞에서부터 시작해서 그리디하게 분할합니다. 이 때 분할 조건은, 각 분할이 $B$ 의 부분문자열 (substring) 이라는 것입니다. 즉,

• $A[1 \ldots i_1]$ 이 $B$ 의 부분문자열인 최대 $i_1$ 을 찾고
• 그 후 $A[i_1 + 1, i_2]$ 이 $B$ 의 부분문자열인 최대 $i_2$ 를 찾고
• ....

와 같이 $A$ 를 분할합니다. 각각의 분할된 부분문자열을 블록 이라고 부릅시다. $A[l \ldots r]$ 이 $B$ 의 부분문자열인지는 여러 방법으로 알 수 있긴 한데, 귀찮으니까 여기서는 그냥 4번 쿼리를 써서 찾아주면 됩니다. 각 숫자에 대해서, $B$ 에서 어디에 등장하는지를 저장해 놓으면, $A[i \ldots i]$ 를 $B$ 의 부분문자열로 표현할 수 있으니, 판별은 물론 그 부분문자열의 등장 위치까지 알 수 있습니다.

쿼리로 $A[x \ldots y]$ 라는 부분문자열 구간이 들어왔을 때, 다음과 같은 성질을 관찰할 수 있습니다.

• Lemma. $A[x \ldots y]$ 와 $B$의 공통 부분문자열은, $A$ 에서 최대 3개의 블록과만 겹친다.
• Proof. 4개 이상 겹친다고 하면, 2개의 인접한 블록을 완전히 포함하는데, 그렇다면 2개의 인접한 블록을 합친 것은 $B$ 의 부분문자열이다. 그렇다면, 초기 구성 때 이들이 같은 블록에 속하도록 계산되어야 한다.

이제 풀이 방향을 다음과 같이 설계할 수 있습니다. $A$ 의 연속된 3개 블록에 대해서, $B$ 와의 답을 적절히 전처리합니다. 그렇다면 각 쿼리에 대해서 고려해야 할 것은, 부분 문자열의 시작점과 끝점 앞뒤에 붙은 블록 뿐입니다. 이들에 대해서 적절한 방법으로 잘 해결해 두면, 그 사이에 있는 값은 미리 전처리해 둔 것을 Segment tree로 불러오기만 해 두면 되니까, 전체 문제가 해결됩니다.

개요를 설명하기 위해서 적절한 방법 이라고 뭉뚱그려 설명했지만, 사실은 이 방법은 어렵습니다. 일단 위 풀이에 사용할 수 있는 함수를 조금 더 formal하게 제시하겠습니다. $fix([l_1, r_1], [l_2, r_2], [l_3, r_3])$ 은 입력으로 3개의 disjoint한 $B$ 상의 구간을 받습니다. 출력으로, 모든 $l_1 \le t \le r_1$ 에 대해서, $lcp(B[t \ldots r_1] + B[l_2 \ldots r_2] + B[l_3 \ldots r_3], B)$ 의 최댓값과, 그 최댓값의 등장 횟수를 반환합니다. 이 부분은 $F$ 랑 비슷하지만 suffix의 시작점이 한정되어 있다는 점에서 약간 다릅니다.

이 함수를 $O(\log N)$ 시간에 계산할 수 있다고 합시다. 이제 쿼리는 다음과 같이 처리할 수 있습니다.

• 구간의 시작점을 포함하는 블록에 대해서, 해당 위치에서 시작하는 부분문자열의 답을 구하기 위해 $fix$ 함수를 한번 호출해 줍니다. (각 블록이 $B$ 의 무슨 부분문자열에 대응하는 지를 전처리에서 미리 계산했습니다.)
• 구간의 끝점을 포함하는 블록, 그리고 그 옆 3개 정도 블록에 대해서도 동일하게 $fix$ 함수를 호출해 줍시다.
• 그 사이는 $fix(Block[i], Block[i + 1], Block[i + 2])$ 에 해당되니, 초기 전처리를 하면 Segment Tree를 사용하여 구할 수 있습니다.

이제 $fix$ 함수를 $O(\log N)$ 시간에 계산하는 것으로 문제가 바뀌었습니다. 이 부분은 두 가지 케이스를 따로 처리하면 됩니다.

• $fix(x, y, z)$ 에서 $B[t \ldots r_1] = B[1 \ldots (r_1 - t + 1)]$ 인 경우. 제일 중요한 것은, 이것을 만족하는 $t$ 는 $r_1$ 에서 Failure function을 타고 내려가면서 열거할 수 있다는 것입니다. Failure function 상에서 마주친 $t$ 들에 대해서 답을 계산하는 것은, $lcp(B[(r_1 - t + 2) \ldots], B[l_2 \ldots r_2] + B[l_3 \ldots r_3])$ 를 계산하는 것으로 가능하고, 이는 Suffix array에 대한 LCP를 전처리하면 $O(1)$ 에 계산할 수 있습니다.
  • 이것을 최적화하기 위해서는, Failure function이 가진 주기성을 잘 활용합니다. $Gap(i) = i - Fail(i)$ 라고 하면, $Fail(i) > i / 2 \rightarrow Gap(i) = Gap(Fail(i))$ 임이 알려져 있습니다. 즉, 어떤 위치에서 Failure function을 타고 내려갔을 때 나온 Gap 수열을, 인접한 같은 값들끼리 묶었을 때, 최대 $\log N$ 개의 그룹이 나온다는 것을 뜻합니다. 한 그룹에서 빠르게 문제를 해결할 수 있으면 전체 문제가 해결됩니다.
  • Failure function을 타고 내려갔을 때의 결과가 $[x - kG, x - (k-1)G, \ldots, x]$ 라고 하고, $x \leq r_1 - l_1 + 1$ 을 만족한다고 합시다. (아니면 구간을 잘 자릅시다.) $P = B[x - G + 1 \ldots x]$ 라고 했을 때, 우리는 $B[x - kG + 1 \ldots ] = PPPPPPPP \ldots X$, $B[l_2 \ldots r_2] + B[l_3 \ldots r_3] = PPPPPPP\ldots Y$ 의 형태로 문자열을 표현할 수 있습니다. 이 때, $lcp(P, X) < |P|, lcp(P, Y) < |P|$ 입니다. ($lcp(X, Y) \geq |P|$ 일 수는 있습니다.)
  • $PPPPP \ldots Y$ 의 앞에 $x$ 개 이상, $y$ 개 이하의 $P$ 를 추가해서 lcp를 최대화해야 하고, 최대화된 개수를 알아야 합니다. $P^k X$, $P^l Y$ 라고 표현합시다.
    • $k > l$ 일 경우 무조건 $lcp(P^k X, P^{l + 1}Y) > lcp(P^k X, P^l Y)$ 가 성립합니다.
    • $k < l$ 일 경우 무조건 $lcp(P^k X, P^{l + 1}Y) = lcp(P^k X, P^l Y)$ 가 성립합니다.
  • 이 조건을 잘 조합하면 고려해야 할 위치가 많지 않음을 관찰할 수 있고, 문제를 해결할 수 있습니다. $k$ 는 $lcp(x - kG, x - (k - 1)G)$ 로 직접 계산할 수 있고, $l$ 은 안 구해도 됩니다. 구현 디테일이 이것 저것 있지만 구태여 언급하지 않습니다. 이 쯤 되면 알아서 할 수 있으리라 믿습니다.
  • 사실은 전 귀찮아서 이를 구현하지 않고 naive하게 따라갔는데 현재 test에서는 잘 통과했습니다..;
• 그렇지 않은 경우에는 $lcp(B, B[t \ldots r_1])$ 의 최댓값을 계산하면 됩니다. 단순하게는 $LCP(1, t)$ 를 취한 후 $r_1$ 을 넘어가면 잘라주면 되겠습니다.$LCP$ 만 계산하면 자료구조로 최적화 가능하지만, $r_1$ 을 넘어갔을 때 자르는 것이 까다롭습니다. 위 알고리즘에서 $B[t \ldots r_1] = B[1 \ldots (r_1 - t + 1)]$ 를 만족한 가장 큰 $t \ge l_1$ 을 기록합시다. 이를 $t_{max}$ 라고 하면, $t > t_{max}$ 일 경우 $t_{max}$ 보다 잘 할 수 없고, $t < t_{max}$ 일 경우 가정에 의해서 자를 필요가 없습니다. $t$ 자체는 위 알고리즘에서 계산되었으니 신경쓸 필요가 없습니다. 단순하게 세그먼트 트리로 최댓값을 계산해 주면 됩니다.

마지막으로 업데이트 쿼리를 지원해야 합니다. 맨 처음 만든 블록을 처음부터 재구성하는 것은 어려워 보입니다. 하지만 Lemma에서 사용한 성질은, 두 개의 연속된 블록이 합쳐지지만 않으면 항상 성립합니다. 업데이트를 통해서 쪼개진 블록들과 그 양 옆에 있는 블록을 모은 후, 초기 initialize 단계와 똑같이, 인접한 블록을 합칠 수 있을 때 합쳐줍니다. 이런 식으로 할 경우 전체적으로 블록을 업데이트 할 필요가 없고, 업데이트 된 위치 근처에 있는 $O(1)$ 개의 블록만 업데이트하면 됩니다. 세그먼트 트리는 이에 맞춰서 잘 갱신해 줍시다. 시간 복잡도는 $O((N + M + Q) \log (N + M))$ 입니다.

Petrozavodsk Winter 2021 Day 7 M. Number of Colorful Matchings

이분 그래프에서 Perfect Matching의 홀짝성은, 인접 행렬을 $Z_2$ 에서 봤을 때 Determinant를 구하는 것과 똑같다는 사실이 잘 알려져 있습니다. 이 문제의 상위 호환이니, 대수적 접근은 필수적이라고 눈치챌 수 있습니다.

$A, B$ 를 $Z_2$ 로 두고 대수적으로 생각해 보면, 결국 문제는 $x$ 에 대한 $n$ 차 다항식인 $det(Ax+B)$ 를 구하는 것입니다. 여기서 또 상위호환 관계를 찾을 수 있는데, 만약 $A = I_n$ 이라고 하면 이 문제는 $B$ 의 특성 다항식을 계산하는 것과 동일합니다. 특성 다항식은 링크에 있는 알고리즘을 사용하면 이를 $O(n^3)$ 에 계산할 수 있고, $Z_2$ 라서 Bitset을 사용하면 $O(n^3 / 64)$ 에도 계산할 수 있습니다.

만약에 $A$가 invertible하다면 문제는 이 정도로도 해결됩니다. $det(Ax + B) = det(A) det(x + A^{-1}B) = det(x + A^{-1}B)$ 이기 때문에 그냥 위에 있는 알고리즘을 적용하면 됩니다.

$A$ 가 invertible하지 않을 때가 까다롭습니다. 목표는, $C = Ax+B$ 에 적당한 Elementary row operation을 적용해서, 행렬을 $(n-1) \times (n-1)$ 크기로 줄여주는 것입니다. 이를 위해서는 $n-1$ 번째 행 / 열이 모두 0이어야 하고, 예외적으로 가장 우하단에 있는 $C_{n-1, n-1}$ 정도만 0이 아니면 됩니다. 이 경우, submatrix $C^\prime$ 에 대해서 재귀적으로 문제를 해결하고, 그 다항식에 $C_{n-1, n-1}$ 을 곱해서 반환해 주면 됩니다. 이를 위해서는 적당한 ERO를 적용시켜 줘야 하는데, 일단 기본적인 성질을 다시 짚고 넘어가면:

• 두 행을 바꿔주는 것은 $det(C)$ 를 변화시키지 않습니다. ($-1 = 1$)
• 한 행에 어떠한 다항식 $q(x)$ 를 곱해 주면, $det(C)$ 에 $q(x)$ 가 곱해집니다.
• 한 행에 다른 행의 상수배를 더해주면, $det(C)$ 를 변화시키지 않습니다.
• $det(A) = det(A^T)$ 니까 같은 이유로 Column operation도 됩니다.

이제 $C$ 를 변형해 봅시다. 첫 번째로, $A$ 를 RREF로 변환하여 invertible한 경우와 비슷한 상황을 만들어 줍니다. $A$의 $n-1$번째 행 (마지막 행) 은 0이 됩니다. 두 번째로, Column swap을 통해서 $B_{n-1, n-1} = 1$ 로 만들어 줍시다. ($B$ 의 마지막 행이 0이면 자명히 $det(Ax+B) = 0$). 이제, $C_{n-1}$ 은 모두 상수항으로만 이루어져 있고 (정확히는 0 아니면 1), $C_{n-1, n-1} = 1$ 입니다. $C_{i, n-1} \neq 0$ 인 모든 행에 $C_i$ 의 배수를 곱해서 $C_{i, n - 1} = 0$ 으로 만들어 주면, $n-1$ 번 열벡터는 마지막 항만 1이고 나머지는 0입니다. 나머지 열들에 $n-1$ 번 열벡터를 더해주면 우리가 원하는 상태에 도달합니다. $C_{n - 1, n - 1} = 1$ 이니, $n - 1$ 번째 행과 열을 지우고 그대로 재귀적으로 들어가주면 됩니다.

모든 연산은 Bitset으로 구현할 경우 $O(n^4 / 64)$ 입니다.

여담으로 이 풀이에는 빠진 내용이 한 가지 있습니다. 알아서 찾아보시고 해결하시기 바랍니다. :)