2020.12.24 problem solving

ABC 159 A. The Number of Even Pairs

$N(N-1)/2+M(M-1)/2$ 를 출력하시면 됩니다.

ABC 159 E. Dividing Chocolate

가로로 초콜릿을 자를 수 있는 모든 $2^{N-1}$ 개의 경우를 다 시도해 봅시다. 세로로 자를 때는 그리디 알고리즘을 사용할 수 있습니다. 왼쪽에서 오른쪽으로 순서대로 봅니다. $K$ 초과의 초콜릿이 생기지 않을 때까지 최대한 초콜릿을 자르지 않고, $K$ 초과의 초콜릿이 생기면 그 전 지점에서 잘라줍니다. 이 알고리즘은 가로로 자르는 방법이 고정되어 있을 때 최적이며, $O(NM)$ 에 구현할 수 있습니다. 고로 시간 복잡도는 $O(2^N NM)$ 입니다.

ARC 110 A. Redundant Redundancy

나머지가 모두 0인 수는 $0, LCM(1, 2, .. N), 2 LCM(1, 2, …, N)$ 입니다. 1인 수는 $1, LCM(1, 2, .. N)+1, 2LCM(1, 2, .. N)+1$ 입니다. 전자는 N보다 무조건 작고, 후자는 N보다 무조건 큽니다.

ARC 110 B. Many 110

만약 S의 1번째 문자부터 시작하는 길이 N의 부분 문자열이 T와 일치하면, 4, 7, 10, … 번째 문자에서 시작하는 부분 문자열도 일치합니다.

만약 S의 2번째 문자부터 시작하는 길이 N의 부분 문자열이 T와 일치하면, 5, 8, 11, … 번째 문자에서 시작하는 부분 문자열도 일치합니다.

만약 S의 3번째 문자부터 시작하는 길이 N의 부분 문자열이 T와 일치하면, 6, 9, 12, … 번째 문자에서 시작하는 부분 문자열도 일치합니다.

고로 이 세 조건을 판별해 준 후, 일치하면 $3k+x$ 번째 문자에서 시작하는 길이 $N$ 의 부분 문자열을 세 주면 됩니다. 개수는 간단한 수식으로 나옵니다.

AGC 023 B. Find Symmetries

$(A, B)$ 에 대해 점대칭과 값이 다른 셀을 불량한 셀이라고 하자. $B - A$ 가 같은 모든 $(A, B)$ 에 대해, 어떠한 셀 $(i, j)$는 전부 불량하거나 전부 불량하지 않다. 이건 식을 써보면 자명할 것이다. $B - A$ 로 가능한 값의 경우의 수는 $O(N)$ 이니, $B - A$ 를 고정하고 문제를 $O(N^2)$ 에 풀 수 있으면 된다. 어떠한 $N \times N$ 정사각형 영역에 불량한 셀이 존재하는 지를 찾아야 하는데, 이는 2차원 부분합을 사용해서 직사각형 영역에 있는 수의 합을 계산하면 된다.

Facebook Hacker Cup 2020 Round 2 B. Elimination

기댓값은 현재 나보다 잘하는 사람의 수와 못하는 사람의 수에 따라 결정됩니다. $dp[i][j]$를 나보다 잘 하는 사람이 i명, 못 하는 사람이 j명일 때의 기댓값이라고 합시다. 가능한 케이스는 다섯 가지입니다.

• 나보다 잘하는 사람 두 명이 경기
• 나보다 잘하는 사람과 못하는 사람이 경기
• 나보다 못하는 사람 두 명이 경기
• 나와 나보다 잘하는 사람이 경기
• 나와 나보다 못하는 사람이 경기

각 경우가 일어날 확률은 간단한 수식으로 계산할 수 있습니다.

각 경우가 일어난 이후의 기댓값은 승패에 따라서 좌우됩니다. 잘하는 사람의 수를 줄이거나, 못하는 사람의 수를 줄이거나, 아니면 내가 경기에서 탈락되거나, 세 가지 경우 중 하나가 가능한 결과입니다.

종합하면 $O(1)$ 에 DP 엔트리 하나를 채울 수 있어서 시간 복잡도 $O(N^2)$ 에 문제가 해결됩니다.

NERC 2019 B. Balls of Buma

연속한 같은 문자들을 한 덩이로 묶었을 때, 덩이들의 중심에 문자를 넣어야지 모든 문자가 사라짐을 관찰할 수 있습니다. 중심에서 시작해야 폭발이 전체 문자열로 다 퍼지기 때문입니다. 이 점을 관찰하면, 대칭된 위치에 있는 덩이들이 같은 색이어야 함도 관찰할 수 있습니다.

고로, 연속한 같은 문자들을 하나의 덩이로 묶은 후, 이것이 대칭적인지 판단해 줍니다. 대칭적이라면 덩이들의 개수는 홀수개입니다. 중앙에 있는 문자를 넣어서 폭발을 시작해 주면 되고, 경우의 수는 중앙에 있는 덩이의 길이와 동일합니다.

NERC 2019 A. Apprentice Learning Trajectory

기본적으로 문제를 그리디하게 해결합니다. 각 시점에서, 하나의 검을 가장 빨리 뽑을 수 있는 대장장이를 찾고, 해당 대장장이가 출근할 때까지 기다린 후 검을 뽑는 것을 반복하면 됩니다.

최적화하기 위해서는, 뽑을 수 있는 대장장이의 후보가 별로 달라지지 않는다는 점을 관찰합시다. 어떠한 위치에서 할 수 있는 일은

• 현재 출근한 $t_i$ 가 최소인 대장장이에게 일을 맡기는 걸, 대장장이가 퇴근하거나 새로운 대장장이가 올 때까지 반복
• 출근 안한 대장장이를 기다리는 것

대장장이가 출퇴근하는 이벤트는 총 $2n$ 번 일어납니다. 이벤트가 바뀌지 않으면 하는 일은 기다리는 일이거나 $t_i$ 가 최소인 대장장이를 계속 부르는 것 뿐이라, 다음 이벤트로 대부분 $O(1)$ 정도에 넘어갈 수 있습니다. 이제 출근 안한 대장장이와 출근한 대장장이를 priority queue로 관리하면, 필요한 정보를 $O(\log n)$ 에 찾을 수 있습니다. 이 정보로 $O(1)$ 에 빠르게 시뮬레이션하면 $O(n \log n)$ 입니다.

Ptz Summer 2019 Day8 G. Cosmic Cleaner

모든 소행성에 대해서, 폭발 영역과 소행성 영역의 교집합의 부피를 더해주면 된다. 즉, 두 구의 교집합의 부피를 더하면 된다. 편의상 교집합이 아니라 합집합의 부피를 구한 후 거기서 교집합의 넓이를 계산해 주자.

합집합을 계산할 때는, 두 구의 실제 위치는 중요하지 않고 중심 간의 거리와 각 반지름만 알면 된다. 두 구의 중심 간의 거리를 $D$ 라고 하자. 한 구가 다른 구의 부분집합이라는 것은 $D \le |R_1 - R_2|$ 라는 것이고, 한 구가 다른 구와 교집합이 없다는 것은 $D \ge R_1 + R_2$ 라는 것이다. 이 경우는 따로 계산해 주자.

두 구의 중심을 잇는 직선을 그렸을 때, 구의 부피는 각 수직선에 직교하는 원의 넓이를 적분하면 된다. 넓이를 적분하기 위해서는 원의 반지름을 알아야 하는데, 두 구 중 어떠한 구의 반지름에 영향을 받는지가 수직선 상의 특정한 위치를 기준으로 나뉘게 된다. 이 위치를 수식으로 계산한 후 적분해 주면 된다.

Ptz Summer 2019 Day8 B. Linear Congruential Generator

$X_i$ 는 특정 위치를 기준으로 해서 길이 $m$ 이하의 사이클에 빠지게 된다. 이 사이클은 단순히 $X_0, X_1, \ldots, X_{2m}$ 을 구하고 처음으로 중복되는 시점을 찾아서 계산해 줄 수 있다. 이제, 구간이 주어졌을 때, 해당 구간에서 $X_i = v$ 인 $i$ 의 수가 각각 몇 개인지를 수식으로 계산해 줄 수 있다. 이 계산값을 저장한 배열을 $Cnt[v]$ 라고 하자.

$A_i$ mod $A_j + 1$ 에서, $d = A_j + 1$ 이라고 두자. 모든 $d$ 의 값을 고정하고 문제를 해결한다. 하나의 $d$ 가 전체 답에 기여하는 양은

$\sum_{i = 0}^{m / d} \sum_{j = 0}^{d - 1} Cnt[id + j](id + j) - Cnt[id+j]id$

이는 부분합을 사용하여 $O(m/d)$ 시간에 계산할 수 있다. 모든 $d$ 에 대해서 이런 식으로 계산해 주면 Harmonic sum에 의해 $O(m \log m)$ 에 문제가 해결된다.

Ptz Winter 2017 Day3 J. Kitamasa's Counterattack

Alice는 Bob의 전략을 알지만, Bob은 Alice의 전략을 모릅니다. 큰 틀에서, f(Alice, Bob) 을 Alice와 Bob의 전략에 따른 함수의 반환결과라고 하면, 우리가 원하는 값은

$Min_{i \in Alice의 전략} Max_{j \in Bob의 전략} f(i, j)$

이 때 이 값은 아래랑 동일합니다.

$Max_{j \in Bob의 전략} Min_{i \in Alice의 전략} f(i, j)$

이 값이 동일하다는 정의를 폰 노이만의 Minimax Theorem 이라고 부릅니다. LP Duality와 동치인 개념인데, 이 문제에서는 LP Duality만을 가지고도 어렵지 않게 증명할 수 있으니 관심이 있다면 직접 해 보아도 좋습니다.

Alice가 전략을 정했다면, Bob이 해야 할 일은 각 상점의 가격을 올려서 이득을 최대화하는 일입니다. 어떠한 상점 j의 가격을 X만큼 올렸을 때, Bob이 얻는 이득은 X * (Alice가 해당 상점에서 산 물건 - $b_j$) 입니다. X의 계수가 양수이면 Bob은 $X = \infty$ 을 설정해 줌으로써 이기고, 아니면 Bob은 $X = 0$ 을 취할 수 밖에 없습니다.

고로 최적해에서 Bob은 아예 돈을 쓰지 않거나, 무한한 돈을 써서 게임을 -1로 만들어 버린다는 사실을 알 수 있습니다. 그리고 무한한 돈을 쓰게끔 하는 조건은, Alice가 어떠한 상점 $j$에서 $b_j$ 개를 초과하는 물건을 썼을 때입니다.

이제 문제는 Alice가 Bob이 무한한 돈을 쓰지 않게만 하면서 최대한 싸게 금고를 전부 여는 것입니다. 이는 MCMF를 사용해서 해결할 수 있습니다. 상점 $j$에서 $b_j$ 개를 초과하는 물건을 사지만 않으면 되니, Source -> 상점 -> 키 -> 금고 -> Sink 형태의 플로우 그래프를 만든 후, Source -> 상점간의 간선에 $b_j$ 의 용량 제한을 주고, 상점 -> 키 간의 간선에 $c_i$ 의 가중치를 주면 됩니다.

Ptz Winter 2020 Day4 D. Clique

원호가 아니라 직선이라고 생각하면, 가장 많은 구간이 겹친 지점이 Maximum Clique가 되겠지만, 원호에서는 $[1, 100], [99, 200], [199, 2]$ 와 같이 세 구간 쌍 간에 모두 교집합이 있다 하더라도 이들이 전부 겹치는 구간은 없을 수 있습니다. 고로 위와 같은 접근은 통하지 않습니다.

Maximum Clique 상에 들어가게 될 구간 하나를 고정시키고, 이 구간을 포함하는 최대 크기 클리크를 찾아줍시다. 이 정점과 교집합이 없는 구간은 무시하고, 이 구간을 완전히 포함하는 다른 구간은, 이 구간과 항상 같이 골라 줄 수 있으니 클리크 안에 넣어 줍시다. 이 구간에 완전히 포함되는 다른 구간은 같이 고르지 못할 수도 있습니다. 하지만, 이 구간을 클리크 안에 포함하고 싶다면, 이 구간을 고정시킨 후 다른 구간을 생각해 줘도 무방합니다. 정의를 살짝 바꿔서, Maximum Clique 안에 들어가며 다른 구간을 포함하지 않는 구간 i 를 고정시켰다고 생각하면 완전히 포함된 구간들을 전부 무시해 줘도 됩니다. 물론, 모든 최대 클리크 안에는 저러한 구간이 존재하기 때문에 (예를 들어 길이가 가장 짧은 구간) 위 정의도 올바릅니다.

이제 모든 구간들은 $i$ 를 포함하지도, $i$ 에 포함되지도 않으며, 그럼에도 $i$와 교집합이 존재합니다. 이러한 구간들은, $i$ 의 왼쪽 끝이나 오른쪽 끝점을 항상 포함합니다 (그렇지 않다면 교차하지 않거나 부분구간이 됩니다). 만약 이러한 구간이 왼쪽 끝과 오른쪽 끝점을 모두 포함한다면 이 구간은 가져가도 됩니다. 이 구간과 교집합이 없는 구간은 $i$ 의 부분구간이라 없다고 가정해도 되기 때문입니다. 고로 이 구간들은 왼쪽 끝 혹은 오른쪽 끝을 포함한다고 생각할 수 있고, 이 기준을 토대로 구간을 두 집합으로 나눕시다.

왼쪽 끝을 포함하는 구간과 오른쪽 끝을 포함하는 구간은 서로 클리크를 이룹니다. 이제 이 둘이 교차하면 간선을 이어줍시다. 이 때 교차 조건을 간단하게 써 봅시다. 왼쪽 끝과 오른쪽 끝을 중심으로 원을 찌그러뜨리면, 원은 왼쪽에서 오른쪽으로 시계방향으로 도는 위쪽 체인과 반시계로 도는 아래쪽 체인으로 분리됩니다. 각 구간은 위 / 아래 체인의 앞 부분, 혹은 뒷 부분을 차지하고 있습니다. 이제 각 구간이 위쪽 체인과 겹치는 길이를 $x_i$, 아래쪽 체인과 겹치는 길이를 $y_i$ 라고 하면, $x$ 의 합이 위쪽 체인의 길이 이상이거나, $y$ 의 합이 아래쪽 체인의 길이 이상이면 겹친다고 생각할 수 있습니다.

우리는 클리크 두 개의 합집합으로 이루어진 그래프에서 최대 클리크를 찾아야 합니다. 간선 존재 여부를 뒤집으면, 이분 그래프에서 최대 독립 집합을 찾는 문제와 동치입니다. 이 때 간선이 있을 조건은, 둘이 교차하지 않는다는 것입니다. 한편, 최대 독립 집합은 최소 정점 덮개의 여집합입니다. 최소 정점 덮개는 Konig's Theorem에 의해서 이분 그래프의 최대 매칭과 똑같으니, 우리는 두 선분 집합이 교차하지 않을 때 간선을 이은 그래프에서, 최대 매칭을 찾아야 합니다.

간선을 이을 조건은 $x$ 의 합이 위쪽 체인 길이 이하고, $y$ 의 합이 아래쪽 체인 길이 이하입니다. 즉, 왼쪽에 있는 선분이 $(l_x, l_y)$ 만큼 위/아래 체인과 겹치고, 오른쪽에 있는 선분이 $(r_x, r_y)$ 만큼 위/아래 체인과 겹친다면, 간선이 생기는 조건은 $l_x + r_x < UP$, $l_y + r_y < DOWN$ 이 됩니다. 이를 또 풀어 쓰면 $l_x < UP - r_x, l_y < DOWN - r_y$ 가 됩니다. 오른쪽 끝점을 포함하는 선분에 대해서 $(x, y) \rightarrow (UP - x, DOWN - y)$ 로 변환하면, 다음과 같은 문제를 푸는 것이 됩니다.

• 빨간 점과 파란 점이 평면에 주어진다. 빨간 점보다 파란 점의 $x, y$ 좌표가 모두 크면 둘을 매칭할 수 있다. 최대 매칭은 얼마인가?

이는 그리디 알고리즘으로 할 수 있습니다. $x$ 좌표 기준으로 스위핑하면서, 빨간 점을 적당한 자료구조에 관리합니다. 만약 파란 점이 주어지면, 현재 매칭할 수 있는 모든 빨간 점 중 $y$ 좌표가 최대인 빨간 점을 매칭하면 됩니다. 매칭할 수 있는 상황에서 매칭하지 않을 이유가 없으며, 매칭할 수 있는 상황에서 최대가 아닌 빨간 점을 매칭하지 않을 이유가 없음을 모두 exchange argument로 보일 수 있습니다. std::set 이나 세그먼트 트리등을 사용하여 매칭해 주면 됩니다. 시간 복잡도는 $O(n^2 \log n)$ 입니다.

Ptz Summer 2019 Day8 A. Erase Nodes

문제와 상관 없는 징징이지만, 쓸데없이 무슨 BFS 어쩌구 하는 이야기를 지문에 써놔서 문제에서 구하는 게 뭔지 너무 헷갈렸다. 알아듣지 말라고 일부러 그러는 걸까. 그러면 안 된다.

비용의 합은 각 정점을 지울 때 해당 정점이 속한 연결 컴포넌트의 크기 합이다. 이를 다른 식으로 쓸 수 있는데, 모든 정점 쌍 $(u, v)$ 에 대해서 $u$ 를 지울 때 $u, v$ 상에서 지워지지 않은 정점들로만 이루어진 경로가 존재하면 비용에 1 기여를 하고, 아니면 0 기여를 한다. 이 값의 합을 구하는 식으로 해도 된다.

만약에 트리일 경우, 위 조건이 참이 되기 위해서는 $u, v$ 상의 유일한 경로에서 처음으로 지워지는 정점이 $u$ 여야 한다. 그래서 두 정점의 거리가 $D$ 이면 해당 쌍이 기댓값에 기여하는 값은 $\frac{1}{D + 1}$ 이다. 이를 모든 $1 \le u, v \le N$ 에 대해서 합하면 된다.

사이클이 하나 있다면, 두 정점을 잇는 경로가 하나 혹은 두 개이다. 하나일 경우에는 위 로직이 동일하게 적용된다. 두 개일 경우에는, 두 경로 중 하나의 경로가 존재할 확률을 더하고, 두 경로가 모두 존재할 확률을 빼는 식으로 비슷하게 계산할 수 있다. 고로, 두 정점이 사이클에서의 거리가 $x, y$ 이고, 사이클의 크기가 $D$ 이며, 사이클 상에서의 위치가 $i, j$ 라면

$\frac{1}{x+y+|i - j| + 1} + \frac{1}{x + y + D-|i-j| + 1} - \frac{1}{x + y + D}$

만큼 기여한다. 이를 모두 더해주면 $O(N^2)$ 풀이를 찾을 수 있다.

이제 모든 수 $1 \le i \le N$ 에 대해서 $\frac{1}{i}$ 의 계수가 얼마인지를 잘 계산한 후 이를 합쳐주는 전략을 사용한다. 트리에서 $\frac{1}{i}$ 의 계수는 거리가 $i -1$ 인 쌍의 수이다. 트리를 Centroid decomposition한 후, Centroid의 거리가 $x$ 인 정점의 개수를 배열 등에 세어주면, 이 배열의 Convolution을 구하는 식으로 Centroid를 지나는 경로들의 거리 등장 횟수를 셀 수 있다. 고로 Centroid decomposition에 FFT를 사용하여 문제를 해결할 수 있다.

사이클이 하나 있을 경우, 일단 사이클에서 하나의 간선을 제거한 후 위 방법을 사용해서 첫 번째 항의 계수를 구하자. 두 번째 항과 세 번째 항은 비슷하게 계산할 수 있는데, 여기서는 편의상 두 번째 항만 계산한다. 각 사이클 정점에 대해서, 해당 사이클 정점과 사이클 쪽 서브트리의 정점간의 거리 등장 횟수를 DFS로 전처리해두자. 이제 길이 $D$ 의 배열의 리스트가 있는데, 이 리스트를 가지고 분할 정복을 통해서 문제를 해결한다. $solve(S, E)$ 를 사이클 내 구간 $[S, E]$ 에 대해 모든 계수를 합쳐준 결과라고 정의하자. $i \in [S, (S + E) / 2], j \in [(S + E) / 2 + 1, E]$ 에 대해서만 문제를 해결할 수 있으면 다른 케이스는 재귀적으로 해결이 될 것이다. $x - j, y + i$ 의 등장 횟수를 새로운 vector를 만들어서 마킹한 후, FFT를 사용해서 convolution으로 원하는 답을 구할 수 있다. 고로 이 역시 분할 정복에 FFT로 해결된다. 시간 복잡도는 $O(N \log^2 N)$ 이다.

Ptz Winter 2018 Day2 H. Hung Fu

순열 최소화 조건을 무시하고 문제를 해결해 봅시다. $(a_i, b_i)$ 쌍을 적절한 순서로 골라서 계산 결과를 최소화하는 것이니, 답을 최소화하는 프로시저를 다음과 같이 생각할 수 있습니다.

• $S = \emptyset$ 에서 시작.
• 매 순간 새로운 원소를 하나 찾아서 시작. 새로운 원소 $i \notin S$ 를 넣을 때는, $cost(i, i)$ 라는 비용을 내거나, 이미 있는 원소 $j \in S$ 를 찾아서 $cost(j, i)$ 라는 비용을 낼 수 있음.

이 과정은 프림의 MST 알고리즘과 상당히 비슷합니다. 새로운 원소를 붙여주지 않을 수 있다는 점이 유일한 차이인데, 0번 원소라는 dummy 원소를 만들어서, $cost(0, i) = a[i] \oplus b[i]$ 라고 정의하면, $S = {0 }$ 에서 시작한 후 새로운 원소를 하나 찾아서 붙이는 과정이 됩니다.

이제 $cost(i, j) = cost(j, i)$ 라면 문제에서 찾는 것은 $cost$ 배열을 인접 행렬로 가진 그래프의 최소 스패닝 트리니, 쉽게 해결할 수 있습니다. 하지만 여기서는 두 배열이 대칭적이지 않습니다. 즉, 간선이 방향성이 있다고 할 수 있습니다. 방향성이 있는 경우에는, 위 프로시저를 통해서 $0$ 번 노드에서 모든 노드를 도달할 수 있는 최소 비용 간선 부분집합을 찾을 수 있습니다 (필요충분을 보이는 과정은 생략합니다). 고로 위 알고리즘은 0번 노드를 루트로 가진 Directed MST를 구한다고 볼 수 있습니다. Directed MST를 구하는 방법은 이 글에 설명되어 있습니다.

순열 최소화 조건을 넣어 봅시다. 어떠한 순열의 prefix $p_1, p_2, \ldots, p_i$ 가 고정되어 있을 때 문제의 최솟값을 비슷하게 찾을 수 있습니다. 한 가지 방법은, prefix를 이루는 노드들을 하나의 슈퍼 루트로 묶은 후 Directed MST를 찾아 주는 것입니다. 또 다른 방법은, prefix가 고정되어 있을 때 어떠한 간선들은 순열에 이미 고정된 순서를 위배하기 때문에 (prefix 밖에서 안으로 들어오는 간선, prefix 내부에서 순서를 어기는 간선), 이 간선들을 빼고 Directed MST를 구해주면 됩니다. 위와 같은 프로시저가 있으면 $p_1, p_2, \ldots, p_n$ 을 순서대로 맞춰나가면서, 최솟값을 주는 순열의 prefix를 그리디하게 정해주면 정답을 찾을 수 있습니다.

이렇게 구하면 Directed MST를 구하는 알고리즘에 따라서 $O(N^5)$ 에서 $O(N^4 \log N)$ 정도의 시간 복잡도가 나옵니다. 어떤 것을 선택하든 충분히 빠릅니다. 잘 구현하면 순열의 원소 하나를 구할 때도 binary search를 사용할 수 있어 최대 $O(N^3 \log^2 N)$ 까지 시간 복잡도를 줄일 수 있습니다.

NERC 2019 H. Help BerLine

삽입이 없이 모든 수가 고정일 때 문제를 해결해 봅시다. 모든 수가 고정일 때 조건을 만족하는지 판별하는 알고리즘은, 구간에서 아무 unique한 원소를 잡은 후 (없으면 만족하지 않음), 이 원소를 포함하지 않는 부분배열만이 조건을 위배할 수 있으니, 이 원소를 기준으로 왼쪽 / 오른쪽 부분배열에 대해서 재귀적으로 판단해 주면 됩니다.

이 알고리즘을 거꾸로 돌리면 $\log N$ 개의 서로 다른 수로 답을 찾을 수 있습니다. 중앙점 $m = (s + e) / 2$ 에다가 새로운 원소 (최댓값) 을 넣고, 왼쪽 오른쪽에 재귀적으로 construction을 해 주면 되기 때문입니다.

여기서, 문제의 제약 조건을 유일 원소가 존재 에서 구간의 최댓값이 유일 원소임 으로 조금 더 어렵게 바꿔줍시다 (사실 별로 어려워지지 않았고 동치에 가까운 조건입니다). 이러한 식으로 바꿔주면 문제의 조건을 다음과 같이 바꿔줄 수 있습니다:

• Theorem. 어떠한 배열 $A$에서, $A[i] = A[j], 1 \le i < j \le N$ 을 만족하는 모든 $(i, j)$ 에 대해, $i < k < j, A[k] > A[i]$ 를 만족하는 $k$ 가 존재하면, $A$의 모든 구간의 최댓값은 유일 원소이다.

증명은 $A[i]$ 에 대한 귀납법이고 생략합니다. 이렇게 조건을 바꾸면 시간 개념이 도입된다 하더라도 생각하기 조금 간편해집니다.

이제 주파수를 크기 순서대로 채워 나갑시다. 주파수 1을 채운다고 합시다. 다른 수는 다 1보다 크니까, 문제의 제약 조건은, 어느 시점에도 1이 채워진 두 원소가 인접하지 않아야 한다는 조건입니다. 새로운 기지국이 건설되면, 현재 이 기지국의 양 옆에 있는 두 원소와 새로운 인접 관계가 생깁니다. 이 인접 관계를 그래프로 그리면 결국 1은 독립 집합을 이뤄야 한다는 뜻이 됩니다. 이 때 이러한 그래프는 스택을 사용해서 $O(N)$ 에 만들 수 있습니다.

모든 기지국에 대해서, 해당 기지국보다 먼저 건설된 기지국 중 간선으로 이어진 기지국은 많아야 2개입니다. 시간 역순으로 기지국을 건설하면, 하나의 기지국에 주파수 1을 임의로 채우면 최대 두 개의 기지국을 잃게 됩니다. 이렇게 시간 역순으로 그리디하게 독립 집합을 채우면, 전체 원소의 1/3을 색칠하게 됩니다.

남은 원소들을 색칠해야 하는데, 남은 원소들은 그 사이에 1이 있든 없든 조건에 아무 상관이 없습니다. 고로 1을 지워주고 $2/3n$ 개의 남은 원소들에 대해서 2, 3, 4,... 를 재귀적으로 칠해주면 됩니다. 고로 $ \log_{1.5} N$ 개의 서로 다른 수로 문제를 해결할 수 있습니다.

CERC 2013. 역사 시간

답이 $k$ 이하인지를 판별하는 결정 문제를 해결해 봅시다. 전체 답은 이분 탐색을 통해서 이 결정 문제를 $O(\log N)$ 번 해결하면 구할 수 있습니다.

답으로 가능한 구간의 순열을 순서대로 만들어 나갈 것입니다. 어떠한 구간이 순열의 $i$ 번째 위치에 들어가게 된다면, 이 구간과 교차하는 구간은 모두 $i + k$ 번 위치 이전에 등장해야 한다는 것을 알 수 있습니다. $level(X)$ 를, 어떠한 구간이 순열 상에서 등장해도 되는 가장 늦은 시점이라고 정의합시다. 이 경우 다음 알고리즘을 통과하는 순열 $p$ 가 있다면 답이 존재함을 알 수 있습니다.

• $p_i$ 번 구간 $[a(p_i), b(p_i)]$ 를 $i$ 번 위치에 배정. 만약 $level([a(p_i), b(p_i)])$ 가 $i$ 미만이라면 실패.
• $p_i$ 번 구간과 교차하는 모든 구간에 대해서 $level(X) := min(level(X), i + k)$ 를 배정
• 배정을 다 하고 교차하지 않는 구간의 순서가 알맞은지 확인

이것만으로 문제에서 필요한 정보는 충분합니다. 다음과 같은 그리디 알고리즘을 설계합니다.

• $countLevel(i)$ 를 $level(X) = i$ 인 구간의 개수라고 하자.
  • $countLevel(i) + countLevel(i + 1) + \ldots + countLevel(j) > j - i + 1$ 인 $j$ 가 존재한다면 답이 $k$ 를 초과한다.
  • 그렇지 않다면, $countLevel(i) + countLevel(i + 1) + \ldots + countLevel(j) = j - i + 1$ 을 만족하는 최소 $j \geq i$ 를 찾는다. ($j = n$ 이 이를 만족해서, 이러한 $j$ ㄱ)가 항상 존재한다.
• 이제 $i \le level(X) \le j$ 인 구간 $X$ 중 끝점이 최소인 구간을 $i$ 번 위치에 배정한다.
• 교차하는 모든 구간에 대해서 $level(X) := min(level(X), i + k)$ 를 배정한다.

알고리즘이 교차하지 않는 구간의 순서가 알맞은지 확인하지 않음 에 유의하십시오. 위 알고리즘을 사용하면 자연스럽게 교차하지 않는 구간들은 번호가 증가하게 나열됩니다. 구간들이 모두 그래프로 보았을 때 연결되었다고 생각하면, 어떠한 교차하지 않는 구간 $a < b$에 대해서 $b$ 의 레벨을 제한시킨 구간의 리스트를 쭉 따라가보면, 그 중 $a$ 를 교차하게 되어 있습니다. 리스트에서 처음 뽑게 되는 구간은 전체 컴포넌트에서 가장 끝점이 작은 구간이기 때문입니다.

알고리즘이 찾는 배정이 항상 올바른 배정임은 위에서도 보았듯이 자명합니다. 왜 이 알고리즘이 항상 답을 찾는지, 즉 알고리즘이 실패할 경우에 정말 해가 존재하지 않는 것인지를 판별하는 것은 어렵습니다. 이에 대한 완벽한 정리는 다음 논문 에 나와있으나, 그 내용은 어려운 편입니다. 다만 직관적으로 이해하는데 도움을 주는 사실은 다음과 같은 것이 있습니다:

• 어떠한 구간에 대해서 $level(X)$ 를 갱신해주는 일은 단 한번 발생하며 이 때 갱신의 방향은 $n \rightarrow i + k$ 입니다. 이 과정에서 최대한 적은 구간을 교차시키고 싶습니다. 그렇다면 왼쪽 오른쪽으로 폭이 좁아야 합니다. 고르는 구간의 왼쪽에 교차하지 않는 구간이 생길 경우 아예 조건이 망가지니 고려해 줄 필요가 없습니다. 오른쪽에 교차하지 않는 구간을 최대한 많이 만들려면 끝점이 최소여야 합니다.
• 교차하지 않는 구간들은 $a < b$ 순서대로 뽑아줘야 하는 것이 문제의 조건입니다.

이제 시간 복잡도를 최적화해 봅시다. 알고리즘을 그냥 구현할 경우 복잡도가 $O(N^2)$ 이기 때문입니다.

• 위에서 보았듯이 $level$ 배열이 갱신되는 횟수가 $O(N)$ 이기 때문에 $countLevel$ 배열에 생기는 변화를 모두 추적할 수 있습니다. $countLevel(i) - 1$ 의 prefix sum을 세그먼트 트리로 관리하고, prefix sum이 최대가 되는 지점, 그러한 지점이 여러개라면 그 중 가장 왼쪽 지점을 관리하게끔 하면 $j$ 를 추적할 수 있습니다.
• $i \le level(X) \le j$ 인 구간 중 끝점이 최소인 구간을 찾아야 합니다. 각 레벨에 대해서 priority queue로 모든 구간을 끝점 증가순으로 관리한 후, 해당 레벨의 대표 구간을 끝점 최소 구간으로 정합시다. 이 대표 구간들을 끝점을 value로 하는 min segment tree로 관리하면 구간 $[i, j]$ 의 최솟값을 찾듯이 찾을 수 있습니다.
• $i + k < n$ 일 때 $level(X) = i + k$ 를 교차하는 구간들에 배정하면 됩니다. 해당 구간의 시작점이 내 구간의 끝점 이하면 교차합니다. 그래서 전체 구간을 시작점으로 정렬한 후 two pointer로 교차하는 구간을 하나씩 뽑아가면 됩니다. level 값이 갱신되면서 이런 저런 자료구조가 바뀌는 것에 유의하십시오.

이 최적화로 결정 문제가 $O(N \log N)$ 에 해결되어 전체 문제가 $O(N \log^2 N)$ 에 풀립니다.

IOI 2009. 양궁

가장 단순한 알고리즘은, 모든 시작점을 다 시도해 본 후 각 시작점에 대해서 $R$ 번 주어진 과정을 시도해 보는 것입니다. 이 때의 시간 복잡도는 $O(N^2R)$ 입니다.

첫 번째 과제는 시간 복잡도에서 $R$ 을 줄이는 것입니다. 알고리즘은 실력이 낮은 궁수의 위치를 보존하려는 경향이 있기 때문에, 반복을 충분히 많이 하면 어느 순간부터는 실력이 낮은 궁수들이 (1번 표적을 제외하고) 제자리에 있을 것이라고 유추할 수 있습니다. 이렇게 되면 이후 토너먼트는 실력이 $2 \ldots N+1$ 인 궁수들의 위치가 한 칸씩 회전하는 것일 뿐이기 때문에, $N$ 번마다 주기성을 띄게 됩니다.

이러한 시점이 생기는지, 그리고 생긴다면 언제 생기는지가 관건인데, 위에서 언급한 단순한 알고리즘을 여러 데이터에서 실험해 볼 경우, 최대 $2N$ 번이 지난 후에는 이러한 주기성이 관찰됨을 유추할 수 있습니다. 고로 $R := 2N + (R \mod N)$ 으로 설정할 수 있습니다. 이렇게 하면 아주 단순한 코드 만으로 복잡도가 $O(N^3)$ 으로 줄어듭니다. 전체 문제를 풀려면 이 사실을 증명해야 하기 때문에, 아래에 그 증명을 적도록 하겠습니다.

Theorem. $2N$ 번 라운드를 할 경우 랭크가 $N+2 \ldots 2N$ 인 궁수들은 $2 \ldots N$ 번 위치를 하나씩 차지하게 되며 이후 토너먼트에서 그 위치가 바뀌지 않는다.

Proof sketch. $N-1$ 번 라운드를 하게 되면, 1번 궁수는 1번 타겟에 도달하게 되며 그 위치에 계속 있게 된다. 이 경우 $1, N+2, N+3, \ldots, 2N$ 번 궁수를 수동적 궁수, $2 \ldots N+1$ 번 궁수를 능동적 궁수 라고 하자. 수동적 궁수와 능동적 궁수가 붙게 되면, 항상 능동적 궁수가 왼쪽으로 가고 수동적 궁수는 자리를 유지한다. 그 외 경우는 두 궁수 중 하나가 왼쪽으로 가게 된다. 이 과정을 진행하는 것은, 수동적 궁수가 두 명 있는 셀을 원형 배열에서 왼쪽으로 밀다가, 0명 있는 셀을 만나면서 해체시키는 것으로 볼 수 있다. 이 과정을 $N$ 번 반복했을 때 2명 있는 셀은 가만히 있는 0명 있는 셀을 무조건 만나게 되기 때문에, $2N-1$ 번 라운드를 할 경우 각 셀에는 수동적 궁수가 정확히 한 명 있고 증명이 종료된다. $\blacksquare$

위 단순한 알고리즘을 돌려보면서 알 수 있는 점은, 시작점을 설정하는 위치가 오른쪽으로 가면 갈 수록 도착점 역시 오른쪽으로 간다는 것입니다. 이 때 오른쪽으로 간다는 건 원형 배열에서 오른쪽으로 가는 것이기 때문에, 한 바퀴 돌아서 가장 왼쪽 지점으로 위치가 바뀔 수 있습니다. 알고리즘을 변형해서, 시뮬레이션을 원에서 하는 것이 아니라 동일한 패턴이 반복되는 무한한 직선에서 한다고 생각합시다. (원형에서 (도착 지점) - N * (한 바퀴 돌아간 횟수) 를 반환한다고 생각할 수도 있습니다.) 이렇게 한 후 알고리즘의 반환 결과를 관찰해 보면 이는 증가 수열을 띕니다. 고로 이 위치를 $N$ 으로 모듈러한 값이 0에 가장 가까운 위치를 찾고 싶습니다.

1번 점과 $N$ 번 점의 반환 값이 $N$ 정도 밖에 차이가 나지 않기 때문에, 모든 $N$ 의 배수에 대해서 해당 배수보다 크거나 같은 첫 위치를 이분 탐색으로 찾을 수 있습니다. 답이 여러 가지 있으면 그 중 가장 오른쪽을 골라야 하기 때문에, 이 부분에서 추가적인 이분 탐색 역시 필요합니다. 이렇게 하면 $O(\log N)$ 번만 시뮬레이션을 해 보면 되기 때문에, $O(N^2 \log N)$ 알고리즘이 유도됩니다.

이제 이를 최적화하기 위해서는, 시작 위치에서 $R$ 번의 라운드를 거친 후 어느 위치에 도달하는 지 (그리고 그 과정에서 몇 바퀴를 도는지) 를 빠르게 판별해야 합니다. 이 문제에서 사용하는 최적화 전략 중 가장 어려운 것이 이 부분입니다, 먼저 하나의 아이디어가 필요한데, 이제부터는 각 선수의 실력이 중요하지 않고 그 선수가 나보다 잘 하는지 못 하는지 여부만 중요합니다. 잘하는 선수 둘이 경쟁해서 누가 이기는지는 문제의 답에 아무 영향이 없습니다. 고로 선수의 랭크를

• 나보다 잘하는 선수
• 나
• 나보다 못하는 선수

로, 0 이상 2 이하의 정수로 둬서 고려합시다.

이제 세 가지 케이스로 경우를 나눠 문제를 해결합시다.

Case 1. 나의 랭크가 1입니다. 자명한 케이스로, 어디서 시작하든 1번 표적에 갇히게 되어 있습니다.

Case 2. 나의 랭크가 $2$ 이상 $N+1$ 이하입니다. 이 경우 나는 위에서 관찰했던 것처럼 주기성을 띄면서 회전하는 궁수에 속합니다. 여기서 약간 접근을 바꿔 봅시다. $2N$ 번 이후에는 실력이 $2 \ldots N + 1$ 인 궁수들이 도는 그림이 나오기 때문에, $2N$ ~ $3N$ 사이의 턴 사이에 1번 위치에 누가 있는지를 전부 알 수 있으면 그 중에 내가 언제 등장하는지를 알 수 있습니다. 이 정보를 사용하면, 내가 $R$ 번 이후 어디 있는지도 알 수 있습니다.

이제 1번 표적에서 어떠한 궁수가 경쟁하는지를 모든 라운드에 대해서 찾는 알고리즘을 생각해 봅시다. 일단 첫 $N$ 라운드를 생각해 봅시다. 첫번째 라운드에서 1번 표적에서 경쟁하는 궁수는 앞에 있는 두 궁수입니다. 이 라운드에서 패배한 궁수를 다시 보려면 $N+1$ 번 라운드가 와야 하니, 첫 $N$ 라운드 안에서 패배한 궁수를 신경 쓸 일은 없습니다. 2 라운드, 3 라운드를 거치면서 앞에 있는 $i$ 개의 표적에 있는 궁수는 모두 1번 표적으로 들어올 수 있습니다. 이 중 가장 잘 하면서, 이미 1번 표적으로 들어오지 않은 (승리해서 현재 남아있거나, 패배하지 않은) 궁수가 $i$ 번 라운드에서 새롭게 1번 표적으로 들어오는 궁수입니다. 증명은 다음과 같습니다.

• 해당 궁수가 $i$ 번 위치에서 왔다면: 이 궁수를 이길 수도 있는 다른 궁수들은 항상 이 궁수보다 앞서서 움직입니다. 고로 이 궁수는 자기보다 잘 하는 궁수를 본 적이 없으며, 모든 라운드를 이길 것입니다.
• $i$ 번 미만의 위치에서 왔다면: 이는 $i-1$ 번 라운드에서 이 궁수가 가능한 모든 궁수 중 두 번째로 강하다는 뜻입니다. 고로 $i-1$ 번에서 들어온 궁수에게 패배하지만, 그 외 궁수에게 패배하지 않습니다. 이는 이 궁수가 $i-1$번 궁수의 바로 뒤에서 따라 들어왔다는 뜻으로, $i-1$번 라운드에서 2번 위치에 있었음을 뜻합니다.

이후 $N+1$ 번 라운드부터는 패배자가 다시 게임에 들어오게 됩니다. 이는 생각보다 간단하게 처리 가능한데, 패배자를 위한 새로운 셀 $N + i$ 번 위치를 만든 후 거기다가 패배자를 넣는 식으로, 똑같이 처리해 주면 됩니다.

알고리즘을 구현할 때는, 각 위치에 있는 나, 검은 궁수와 흰 궁수의 수를 세어 준 후, 이 카운트를 기준으로 모든 결정을 내리면 됩니다. 이후 $2N$ 번 이후의 라운드에서 내가 1번에 도착하는 시점을 찾아주면 됩니다. 각 라운드가 $O(1)$ 에 계산되기 때문에 시간 복잡도가 $O(N)$ 입니다.

Case 3. 나의 랭크가 $N+2$ 이상입니다. 이 경우 나는 수동적 궁수 에 속합니다. 자동적인 궁수와 1번 궁수를 모두 무시해 줍시다. 1번 위치에 (1번 궁수가 아닌) 수동적 궁수가 가게 되면 무조건 쫓겨납니다. 고로 1번 위치에 있는 수동적 궁수를 모두 밀어내고 1번 위치를 아예 없애 버립시다. 이제 고려해야 할 것은 $2 \ldots N$ 의 위치로, 수동적 궁수 두 명이 있으면 그 중 잘 하는 궁수는 왼쪽으로 밀려납니다. 이 과정을 시뮬레이션해야 하는데, 간단하게 배열을 $2N$ 번 돌면서 수동적 궁수의 리스트를 Case 2처럼 관리할 수도 있습니다. 괄호 문자열을 처리하듯이, (수동적 궁수 수) - 1의 suffix 합이 최소인 가장 짧은 suffix의 왼쪽에서 시작해서 한바퀴 도는 식으로 처리하면, 리스트에서 궁수가 비는 경우가 없어서 한바퀴로 처리 가능합니다. 수동적 궁수 간의 충돌 규칙이 간단한 편이라 이 외에도 여러 방식이 있습니다. 1번 위치만 조심하면 됩니다. 시간 복잡도는 $O(N)$ 입니다.

결국 모든 케이스가 O(N) 에 해결되어 전체 문제는 $O(N \log N)$ 에 해결됩니다.

Ptz Winter 2018 Day4 B. Short Random Problem

최소 지름 스패닝 트리를 구하는 문제와 접근 방식이 비슷하다. 트리의 지름의 중점을 흔히 트리의 중심 (center) 라고 부르는데, 트리의 중심을 알고 있다면, (중심에서 가장 먼 점과의 거리) * 2 를 통해서 트리의 지름을 역으로 추적할 수 있다. 트리의 중심은 간선 위나 정점 위에 있는데, 트리의 중심이 정점 위에 정확히 있을 확률은 0이니, 이것이 어떠한 간선 $e$ 위에 있다고 하자.

$e$ 를 기준으로 트리를 나눠서, 루트 방향 서브트리를 $u$ 라고 하고 자식 방향 서브트리를 $v$ 라고 하자. $e$ 의 $u$ 쪽 끝점에서 가장 멀리 갈 수 있는 거리를 $fu$, $v$ 쪽을 $fv$ 라 하면, $e$ 위에 중심이 있을 조건은 $|fu - fv| \le length(e)$ 이며, 이 때의 지름의 길이는 $fu + fv + e$ 이다. 고로, 이 사건이 일어날 확률을 고정된 $(fu, fv, e)$ 에 대해서 알아줄 수 있는지를 확인하면 문제 해결에 가까워질 수 있다.

각 서브트리에서 가장 멀리 갈 수 있는 거리가 $x$ 일 확률을 구하자. 만약에 $x$ 가 정수라는 조건이 있으면, 이는 dp로 쉽게 계산할 수 있다. $dp[u][x]$ 를 $u$ 의 서브트리에서 거리 $x$ 이하로 모든 정점을 도달할 수 있는 확률이라고 하면, 서브트리에서 부모로 올라오는 과정은 부분합으로, 서브트리에서 합쳐주는 것은 단순히 부분합의 곱을 취해주는 것으로 가능하다. (이 때 점화식을 써 보면, 정확히 $x$ 가 아니라 $x$ 이하로 정의하는 이유를 알 수 있다).

$x$ 는 실수이기 때문에 이러한 논리는 먹히지 않으나, 대략 비슷한 방식을 사용할 수 있다. 실수 함수에서 함수의 곱은 당연히 정의되고, 부분합의 개념은 적분의 개념과 동일하다. 고로 $dp[u]$ 를 실수 $x$ 에 대한 함수로 정의하고, 적분과 곱셈을 해 주면 된다.

확인해야 할 것은, $dp[u]$ 를 함수로 관리하는 것이 정말로 가능한지이다. 당연히 저러한 함수는 존재하겠지만, 컴퓨터로 다룰 수 없을 만큼 양이 크거나 함수가 복잡하고 더러울 경우에는 관리가 불가능할 것이다. 하지만 적분 구간이 항상 고정된 수 1이기 때문에, $dp[u]$ 를 각 정수 구간 $[a, a + 1]$ 로 쪼개서 보았을 경우 항상 이것이 유리수를 계수로 가지는 다항함수임을 알 수 있다. 더 나아가서, 봐야 할 정수 구간은 많아야 $n$ 개이며 (자명), 각 항은 최대 $n$ 차식이기 때문에 (귀납), 적분 및 곱셈이 $O(n^3)$ 에 가능하다. 고로 이를 각 에지에 대해서 단순히 계산해 주면 $O(n^5)$ 가 되며, 위 아래로 DP를 해 주면 $O(n^4)$ 가 된다.

이제 이를 토대로 실제 답을 계산해 주자. $f, g$ 를 각 방향으로 멀리 갈 수 있는 거리의 확률 분포라고 하면 ("정확히 x" 가 아니라 이하로 정의되었음에 유의하라) 문제의 정답은

$\int_{0}^{\infty} \int_{0}^{1} \int_{x - e}^{x + e} f^\prime(x)g^\prime(y)(x+y+e) dy dedx$

대충 이런 식으로 된다. 이를 잘 계산해 주면 된다. 아래 어떻게 잘 계산할 수 있는지 유도 과정을 서술한다.

$\int_{0}^{\infty} \int_{0}^{1} \int_{x-e}^{x + e} f^\prime(x)g^\prime(y)(x+y+e) dy dedx$

$=\int_{0}^{\infty} f^\prime(x) \int_{0}^{1} \int_{x-e}^{x + e} g^\prime(y)(x+y+e) dy dedx$

$=\int_{0}^{\infty} f^\prime(x) \int_{0}^{1} [(x+y+e)g(y) - G(y)]^{x+e}_{x-e} dedx$

$=\int_{0}^{\infty} f^\prime(x) \int_{0}^{1} ((x+x+e+e)g(x+e) - G(x+e)) - ((x+x)g(x-e) - G(x-e)) dedx$

$=\int_{0}^{\infty} f^\prime(x) \int_{0}^{1} (2x+2e)g(x+e) - G(x+e) - (2x)g(x-e) + G(x-e) dedx$

$=\int_{0}^{\infty} f^\prime(x) \int_{0}^{1} (2x+2e)g(x+e) - G(x+e) - (2x)g(x-1+e) + G(x-1+e) dedx$

$=\int_{0}^{\infty} f^\prime(x)( \int_{x}^{x+1} (2e)g(e) - G(e) - 2xg(e-1) + G(e-1)de)dx$

$=\int_0^{\infty}f^\prime(x) ([2eG(e) - 3GG(e)-2xG(e - 1) + GG(e - 1)]_x^{x + 1}$

$Fu(x) = ([2eG(e) - 3GG(e)-2xG(e - 1) + GG(e - 1)]_x^{x + 1}$ 라고 정의하자. 전개하면:

$Fu(x) = (2(x+1)G(x+1) - 3GG(x+1)-2xG(x) + GG(x))-(2xG(x) - 3GG(x)-2xG(x - 1) + GG(x - 1)))$

$=2(x+1)G(x+1) - 3GG(x+1)-4xG(x) + 4GG(x)+2xG(x - 1) - GG(x - 1))$

$=2(x+1)G(x+1)-4xG(x)+2xG(x-1)-3GG(x+1)+4GG(x)-GG(x-1)$

이제 우리는 $\int_{0}^{\infty} f^\prime(x)Fu(x)$ 를 계산해야 한다. 그냥 곱해도 되지 않는가라고 생각할 수 있겠지만, $f(x)$ 는 $x = 0$ 에서 연속이지 않아 미분불가능하다. 그래서 저 식은 계산이 안 된다. $(fg)^\prime = f^\prime g + fg^\prime$ 임을 사용하면:

$\int_{0}^{\infty} f^\prime(x)Fu(x) = [f(x)Fu(x)] - \int_{0}^{\infty} f(x)Fu^\prime(x)$

여기서 $Fu$ 이 미분가능함을 보일 수 있다.

$Fu^\prime(x) = 2G(x + 1) + 2(x + 1)g(x + 1) - 4xg(x) - 4G(x) + 2G(x - 1) + 2xg(x - 1) - 3G(x + 1) + 4G(x) - G(x - 1)$

$Fu^\prime(x) = -G(x + 1) + G(x - 1) + 2(x+1)g(x + 1) - 4xg(x) + 2xg(x - 1)$

고로 이대로 적분하여 계산하면 된다. 여담으로 본인이 이런 저런 식을 유도해 봤는데, 적분 범위를 어떻게 잡는가 등등에 따라서 $Fu$ 이 미분 가능할수도 있고 아닐 수도 있다. 예를 들어 적분 구간을 $x, x + e$ 로 잡고 대칭적으로 해결하면 계산이 쉽다고 생각할 수 있지만, 미분이 되지 않아 그냥 처음부터 다시 해야 한다. 본인은 서너번 이상 실패를 겪었는데 독자들도 꼭 직접 계산해 보고 실패의 쓴맛을 겪어보길 바란다.

사실 이 풀이는 본인이 UCPC 2020 애완 트리를 푼 과정과 굉장히 비슷하다. 애완 트리는 함수를 관리하지 않고 수로 관리해도 되며, 괴상한 적분을 하지 않아야 한다는 점에서는 이 문제보다 쉬우나, 정점에서의 확률이 0으로 수렴한다고 무시할 수 없기 때문에 이 케이스를 따로 DP로 처리해야 한다. 이 문제보다 어려운 점도 있고 쉬운 점도 있는데, 그래도 쉬운 편이라고 생각한다. 뭐 하여튼 그 문제는 이보다 간단한 풀이가 있는 문제이다.

Ptz Winter 2020 Day9 K. Knowledge Oriented Problem

Kirchhoff의 Matrix-tree theorem에 의해서, 그래프 $G$ 의 Laplacian matrix $L(G)$ 의 고윳값 $\lambda_0, \lambda_1, \ldots, \lambda_{n - 1}$ 은 다음과 같은 성질을 가지고 있습니다. ($\lambda_0 \le \lambda_1 \le \ldots \lambda_{n - 1}$ 를 가정합니다)

• $\lambda_0 = 0$
• $G$ 의 스패닝 트리의 개수는 $\frac{1}{n} \lambda_1 \lambda_2 \ldots \lambda_{n-1}$

우리는 두 그래프 $G_1, G_2$ 의 Cartesian product $G_1 \times G_2$의 스패닝 트리의 개수를 알고 싶습니다. 두 그래프의 Cartesian product에 대해서 다음과 같은 성질이 알려져 있습니다.

• $G_1$ 의 고윳값을 $\lambda_0, \lambda_1, \ldots, \lambda_{n - 1} $ 이라 하고, $G_2$ 의 고윳값을 $\mu_0, \mu_1, \ldots, \mu_{k-1}$ 이라 하면, $L(G_1 \times G_2)$ 의 고윳값은 ${l_i + \mu_j |0 \le i < n, 0 \le j < k}$ 이다.

고윳값을 직접 구할 수 없다는 것이 문제인데, Resultant의 개념을 사용하면 됩니다. (https://koosaga.com/264) $L(G)$ 의 고윳값을 해로 가지는 다항식은 $L(G)$ 의 특성 다항식 $P_{L(G)}(x)$ 입니다. 고로 $P_{L(G_1)}(x)$ 와 $P_{L(G_2)}(x)$ 의 Resultant를 구하면 $\Pi{(\lambda_i - \mu_j)}$ 를 계산할 수 있습니다. 이를 비틀어서 $P_{L(G_1)}(x)$ 와 $P_{L(G_2)}(-x)$ 의 Resultant를 구하면 $\Pi(\lambda_i + \mu_j)$ 를 계산할 수 있습니다.

이렇게 하면 $L(G_1), L(G_2)$ 의 특성 다항식을 계산한 후에 Resultant를 구하면 비효율적이지만 최소한 정답은 구할 수 있을 것처럼 보입니다. 하지만 위 방법은 두 가지 큰 문제가 있습니다.

• $G$ 의 스패닝 트리를 계산할 때 모든 eigenvalue를 곱하는 게 아니라 non-zero eigenvalue만 곱한다는 것을 기억합시다. $\lambda_0 = \mu_0 = 0$ 이라 Resultant는 계산할 것도 없이 0입니다. 그래서 $\lambda_0 + \mu_0$ 은 빼고 계산해야 합니다.
• 이걸 빼도 문제가 있는데, $\frac{1}{Kn}$ 에서 $K$ 가 $10^9 + 7$ 의 배수이면 0으로 나누게 된다는 것입니다.

일단은 Laplacian은 $\lambda_0 = 0$ 이고 상수항이 0이니까, 단순히 $P_{L(G)}(x) / x$ 를 취해주는 식으로 $\lambda_0 = 0$ 은 뺄 수 있습니다. 이렇게 해서 $\Pi_{1 \le i, 1 \le j} (\lambda_i + \mu_j)$ 를 계산한 후, $\Pi_{1 \le i} \lambda_i, \Pi_{1 \le j} \mu_j$ 를 또 계산해 주고 세 값을 모두 곱하면 답의 $Kn$ 의 배수를 구할 수 있습니다. 여기서 두 번째 포인트가 필요한데, $\Pi_{1 \le i} \lambda_i, \Pi_{1 \le j} \mu_j$ 는 각각 ($G_1$ 의 스패닝 트리 개수 * n), ($G_2$ 의 스패닝 트리 개수 * k)$ 라는 것입니다. 고로

• Resultant로 $\Pi_{1 \le i, 1 \le j} (\lambda_i + \mu_j)$ 를 계산한 후
• $G_1$ 의 스패닝 트리 개수를 곱하고
• $G_2$ 의 스패닝 트리 개수를 곱하는

빌드업이 됩니다. $G_2$ 의 스패닝 트리는, 경로는 트리니까 당연히 1입니다. $G_1$ 의 경우 특성 다항식을 구해주면 부산물로 스패닝 트리의 개수도 알 수 있습니다.

다시 본 문제로 돌아갑시다. 이제 특성 다항식만 구해주고 Resultant를 계산해 주기만 하면 문제를 해결할 수 있습니다. 두 과정 모두 쉽지 않은데, 특성 다항식은 https://rkm0959.tistory.com/141?category=743276 에 구하는 방법이 아주 잘 나와 있습니다. $PAP^{-1}$ 형태의 similar transformation은 특성 다항식을 보존하기 때문에, 가우스가 $O(n^2)$ 에 되는 Hessenberg form으로 변환해 준 후 interpolation을 그냥 하면 특성 다항식을 구할 수 있습니다. 이렇게 $G_1$ 의 특성 다항식은 구할 수 있습니다.

$G_2$의 특성 다항식은 조금 복잡합니다. 행렬이 너무 크기 때문에 그냥 구해줄 수 없기 때문입니다. Determinant의 정의로 들어가서, $(1, 1)$ entry를 선택한 순열의 합과 $(1, 2)$ entry를 선택한 순열의 합으로 두 경우를 나눠서 다항식을 점화식 형태로 써 줄 수 있습니다. $(1, 1), (K, K)$ 엔트리는 $1 - \lambda$ 가 적혀 있고 $(2, 2), (3, 3), \ldots$ 는 $2 - \lambda$ 가 젹혀있어서 케이스가 기하급수적으로 많이 나오지만 그 기하급수적인 케이스를 다 손으로 써보면 ($n \le 7$ 까지 해보면 됨) 그냥 대충 $2 - \lambda$ 라고 점화식을 세워도 잘 된다 (...) 라는 허무한 결론을 얻을 수 있습니다. 그래서 점화식은 사드세요 그냥 $k = 1, k = 2$ 만 base case로 두고 점화식을 써 주면 됩니다. 점화식은 $P_n(x) = (2 - x) P_{n - 1}(x) - P_{n - 2}(x)$ 입니다. 어차피 나눠야 하니 $P_n(x) / x$ 에 대한 점화식을 써 주는 게 좋습니다.

이렇다 하더라도 $G_2$ 의 특성 다항식은 여전히 계산하기에는 너무 큽니다. $G_2$ 의 특성 다항식은 Resultant를 계산하는 데만 사용될 것이고, Resultant 계산의 첫 시작은 $G_2$ 의 특성 다항식을 $G_1$ 의 특성 다항식으로 나눈 나머지를 취하는 것이니까 (그것만 하는 것은 아니지만 잔 과정은 생략합니다) 큰 틀에서는 $G_2$ 의 특성 다항식을 $G_1$ 의 특성 다항식으로 나눈 나머지를 계산할 수 있으면 됩니다. 이렇게 되면 문제가 훨씬 접근 가능해지는데, $P_n(x)$ 는 일종의 피보나치와 같은 선형 점화식으로 두고, 행렬 제곱의 요령으로 계산할 수 있습니다. 행렬 곱을 할 때 수가 커지면 modulo를 하듯이 다항식이 커지면 $G_1$ 의 특성 다항식으로 modulo를 해 주면 $O(N^2 \log K)$ 에 특성 다항식을 구해줄 수 있습니다. 이제 이를 Resultant로 취해주면 문제가 해결됩니다.