20200814 problem solving

Petrozavodsk Winter 2020 Day9D. Data Structure Quiz

$O((n + q_1 + q_2) \log^2 n)$ 풀이도 있고, $O(n^{5/3} + (q_1 + q_2) n^{1/3} \log n)$ 풀이도 있습니다. 두 번째는 통과를 하고, 첫 번째는 구현은 안 해 봤지만 아마 통과를 못 할 것 같습니다 :) 여기서는 $O((n + q_1 + q_2) \log^2 n)$ 풀이를 소개한 후 $O((n + q_1) \log^2 n + q_2 \log n)$ 풀이를 소개합니다.

$x, y$ 축에 대한 2차원 세그먼트 트리 같은 것을 사용할 수 없으니, $x$ 축은 분할 정복, $y$ 축은 1차원 세그먼트 트리를 사용해서 관리하는 식의 접근을 사용합니다. 전반적인 철학은 Offline dynamic connectivity에서 사용하는 분할 정복과 같습니다. Offline dynamic connectivity는 시간 축에 대한 일종의 세그먼트 트리로 생각하는 경우가 많은데, 세그먼트 트리와 다른 점은 어떠한 노드의 "값" 을 정의할 수가 없다는 것입니다. 값으로 그래프의 연결성을 사용하는 것은 너무 복잡하고 비싼 연산이기 때문입니다. 이러한 점 때문에, Offline dynamic connectivity에서는 각 노드에 값을 배정해 주는 대신 DFS를 사용해서 오프라인으로 각 노드에서 필요한 값을 구해줍니다. 여기서도 접근은 비슷합니다. 1차원 세그먼트 트리를 각 노드에 매달아주는 접근이 실패했기 때문에 DFS를 통해서 오프라인으로 각 노드에서 필요한 세그먼트 트리를 제공해 줍니다.

구간 최댓값 쿼리는, $O(\log n)$ 개의 세그먼트 트리에 대한 구간 최댓값 쿼리로 바꿀 수 있습니다. (실제로는 이렇게 하면 $\log^2$ 가 나오지만 여기서는 넘어갑니다). 위 최댓값 쿼리를 진행하는 방식에 의하여, 구간 덧셈 쿼리는, 해당 구간과 교집합이 있는 모든 세그먼트 트리에 덧셈을 해야 합니다. 세그먼트 트리의 구간 $T$ 와 쿼리 구간 $Q$ 에 대해서, $Q \cap T$ 가 비지 않지만, $Q \cap T = T$ 는 아닌 노드는 $O(\log n)$ 개 입니다. 이들 노드에 닿았을 경우에는 나이브하게 더해줍니다. $Q \cap T = T$ 인 노드는 $O(n)$ 개가 될 수 있지만, $O(\log n)$ 개의 서브트리로 표현할 수 있습니다. 고로 이들 서브트리에 들어갈 때 더해주고, 나올 때 빼주는 방식을 사용하면 각 서브트리에 일일이 더해줄 필요가 없습니다 (오프라인으로 트리를 관리하는 장점이 여기 있습니다). $y$ 축에 대해서 일반적인 lazy segment tree를 관리하면 전체 문제가 $O((n + q_1 + q_2) \log^2 n)$ 에 풀립니다. 통과하는 지는 확인을 안 해봤는데 되면 알려주세요.

최댓값 쿼리에 대해서 log를 하나 떼기 위해서는, 분할 정복 과정에서 쿼리를 $\log$ 개로 나누지 말고 두개로 나눕시다. 세그먼트 트리를 타고 내려가다가, 처음으로 해당 구간이 두 위치로 갈리는 시점을 만나면, 해당 노드에서 계속 타고 내려가는 것이 아니라 prefix / suffix 쿼리로 간주해서 진행합시다. 구간 덧셈 쿼리를 다시 리뷰합시다. $Q \cap T$ 가 비지 않았고 $Q \cap T = T$ 는 아닌 노드는 많아야 $O(\log n)$ 개 입니다. 이 노드들에 대해서는 해당 직사각형을 그냥 직사각형 자체로 두고 생각해도 $O(q_1 \log n)$ 개의 이벤트만 형성됩니다. $Q \cap T = T$ 인 노드들은 전체 트리에 영향을 끼치는데, 위에서 사용한 대로 세그먼트 트리를 오프라인으로 공유하는 방법을 그대로 사용합니다.

이제 각 노드들에 대해서 필요한 직사각형 정보는

• 부모로부터 상속받은 $Q \cap T = T$ 직사각형 정보들: 불변량으로 가지고 다니고, 재귀함수를 나올 때 정확히 저 값들만 저장되도록 합시다.
• 해당 노드와 교집합이 있지만 전체를 덮지는 않는 직사각형 정보들: 그냥 이벤트 전체로 들고 다닙시다.

그리고 쿼리는, 한쪽 끝이 $x = m$ 에 붙어 있는 직사각형 영역의 최댓값입니다. 라인 스위핑에 뭔가 적합해 보입니다.

각 노드를 처리하기 위해서 이제 진짜 라인 스위핑을 사용합시다. $Q \cap T = T$ 인 직사각형 정보가 모두 저장되어 있는 세그먼트 트리를 받아서, 스위핑에 사용합니다. 구간 덧셈/뺄셈, 그리고 그동안 해당 트리에 저장된 적이 있는 모든 값 중 최댓값 (historical max) 을 가지고 있어야 합니다. 이 값을 가진다면, 쿼리는 그냥 구간에서 historical max의 최댓값을 취해주는 식으로 할 수 있습니다.

historical max를 관리하는 것은 굉장히 복잡해 보이지만, 저는 historical max는 시간 축에 대한 prefix sum 최댓값이다 라는 관점을 견지함으로써 관리 방법을 비교적 쉽게 이해하고 유도할 수 있었습니다. 단순한 접근은, 각 시간에 대한 갱신 정보를 모두 저장하고, 그리고 갱신 결과에 대한 prefix sum 최댓값을 들고 다니는 것입니다. 그런데, prefix sum 최댓값만이 필요하다면, 전체 정보가 필요하지 않습니다. 어떠한 시간 구간에 대해서 관심있는 정보가 (전체 합, prefix sum 최대) 두개 뿐이기 때문에, 관심있는 시간에 대한 정보를 2개의 정수로 저장할 수 있습니다. 두 시간 정보를 더하는 것은 간단하게 할 수 있으니, 덧셈 연산자를 overloading시켜두면 일반적인 Lazy propagation과 다를 바가 없습니다.

최종적으로, 위 구현의 상수가 생각보다 크니 주의하시기 바랍니다. 특히 롤백을 구현할 때 효율적으로 구현해야 합니다.

AMPPZ 2012 J. Do It Tomorrow

첫 $X$ 일을 놀았다는 것은 모든 일의 데드라인이 $X$ 일 앞당겨졌다는 것과 동일합니다. 고로 $X$ 를 결정하면, 일을 하는 데 걸리는 기간과 데드라인이 주어질 때 주어진 일을 모두 처리할 수 있는지 확인하는 문제가 됩니다. 이는 deadline-first scheduling으로, 일을 데드라인 증가 순으로 정렬하고 순서대로 하면 됩니다. 정당성은 Exchange argument를 사용하여 증명할 수 있습니다. 고로 고정된 $X$ 에 대해 $O(n \log n)$ 시간이 걸립니다.

이제 전체 문제를 해결하기 위해서는,

• $X$ 에 대해서 이분 탐색을 하여 답이 존재하는 가장 큰 $X$ 를 찾습니다. 일 하는 순서가 똑같기 때문에 정렬은 한 번만 해도 됩니다. $O(n \log n + n \log X)$ 정도입니다.
• 우리는 $X$ 가 뭐가 됐든 일을 데드라인이 이른 순서대로 진행할 것입니다. 고로 순서를 찾은 후, 가장 데드라인이 늦은 일부터 역산해가면 $X$ 로 가능한 최댓값은 $O(n)$ 에 계산 가능합니다. 총 $O(n \log n)$ 입니다.

BOI 2018. Paths

$dp[S][v]$ 를, 현재 고려하고 있는 경로의 끝점이 $v$ 이며 방문한 색깔 집합이 $S$ 인 경로의 개수라고 합시다. 모든 정점의 색이 다 다르기 때문에, $|S|$ 가 경로의 길이가 되고, 이것이 증가하는 순으로 DP를 돌려주면 됩니다. 그러면,

• 기저 조건 ($|S| = 1$) : $dp[{C_v}][v] = 1$
• 귀납 조건 ($|S| \geq 2$) : $dp[S][j] = \sum_{w \in adj(v)}dp[S \setminus {C_v}][k]$ if $C_v \in S$

라는 비교적 간단한 점화식으로 문제를 해결할 수 있습니다. 시간 복잡도는 $O((n + m) \times 2^k)$ 입니다.

경우의 수를 세는 것이 아니라 가중치 합을 최대화하는 문제를 생각할 수도 있고, 이 경우에도 동일하게 풀립니다. 이 문제가 재미있는 점은, 만약 모든 정점의 색이 다르다라는 조건이 제거되고, 단순히 길이가 $k$ 일 때 문제를 푼다 라고 하더라도 비슷한 식의 방법으로 문제를 해결할 수 있기 때문입니다: 단순히 각 정점에 $[1, k]$ 구간의 정수를 랜덤하게 배정해 준 후, 색이 다르다는 조건을 준 문제를 $O((n + m)2^k)$ 에 여러 번 풀고, 찾은 것 중 최댓값을 취해주면 됩니다. Color coding이라고 불리는 방법인데, $k$ 가 작을 때 일반적으로 고려해 볼 수 있는 알고리즘 디자인 방법입니다. 관심 있으신 분들은 찾아보시기 바랍니다.

Petrozavodsk Summer 2019 Day5C. Cloyster

단순하고 비효율적인 접근은, 아무 점이나 잡은 후, 이 점에서 인접한 셀 중 값이 큰 셀을 따라서 계속 움직이는 것입니다. 최댓값에 도달하지 않은 이상 계속 움직일 수 있을 것입니다.

격자를 반으로 가르는 선을 하나 그립시다. 임의의 셀이 움직인 경로는 이 셀을 아주 교차하지 않거나, 한 번 이상 교차할 것입니다. 한 번 이상 교차했다면, 마지막으로 교차한 지점은 모든 교차점 중에서 가장 높이가 클 것입니다.

여기서 거꾸로, 격자를 반으로 가르는 선에서 가장 높이가 높은 점을 잡고 탐색을 시작해 봅시다. 이 점에서 시작하는 경로는 다시는 이 격자를 방문하지 않을 것입니다. 즉, 경로는 해당 선에서 완전히 왼쪽이나 오른쪽에 있다는 것인데, 이것은 최댓값의 방향을 짐작할 수 있다는 뜻이기도 합니다.

이를 통해서 분할 정복을 할 수 있습니다. 격자를 적당히 반으로 가르는 선을 그린 후, 해당 선에서 최댓값을 찾고, 최댓값이 움직이는 반쪽 방향으로 계속 줄여나가면서 탐색을 해 줄 수 있습니다. 이런 식으로 하면, 탐색하는 점의 개수가 $N + N/2 + N/2 + N/4 + N/4 + ... = 3N$ 언저리가 되어서, 문제를 해결할 수 있습니다.

다만 여기에는 함정이 있는데, 처음에는 격자를 반으로 가르는 선이 격자를 완전히 양분하여 최댓값의 방향을 정확히 파악할 수 있게 하지만, 뒤로 가면서 격자를 가르는 선이 최댓값이 이루는 경로와 겹치지 않을 수도 있습니다. 예를 들어서 최댓값이 우상단에 있다고 합시다. 맨 처음 분할 정복 과정에서 이를 토대로 왼쪽 반을 날렸는데, 그 다음에서 찾은 최댓값이 아래쪽 방향에 최댓값이 있다고 보고할 수 있습니다. 이 경우에 이 최댓값을 따라가 보면, 좌하단 쪽으로 왼쪽 반에 들어간 후, 그 다음 좌상단 -> 우상단 으로 해서 가르는 선을 교묘하게 피하면서 탐색을 하게 될 것입니다.

이러한 경우를 막기 위해서는, 지금까지 격자를 가르는 선이 찾은 최댓값을 관리한 후, 현재 반으로 가르는 선 상에 있는 최댓값이 이 값보다 큰지를 확인한 후, 만약 크지 않다면 이 최댓값은 무시한 후 그동안 찾은 최댓값이 있는 방향으로 탐색을 진행하면 됩니다.

2018 ICPC East Continent Finals A. Exotic Ancient City

문제에서 특이한 점은 모든 간선의 가중치가 30 이하라는 것입니다. 모든 간선의 가중치가 1이라면 문제의 답은 단순히 컴포넌트의 개수와 동일합니다. 30 이하인 경우에도 비슷한 논리가 적용됩니다. 어떤 MST를 골랐다 하더라도, 임의의 숫자 $x$ 에 대해서 $x$ 이하의 가중치를 가진 간선의 개수는 동일합니다. 고로 각각의 쿼리에 대해서, $F[j] = $(가중치 $j$ 이하의 간선들만 모았을 때 컴포넌트의 개수) 를 계산할 수 있으면, 간선의 개수도 계산할 수 있으니 전체 문제 역시 쉽게 해결할 수 있습니다. 이는 $1, 2, \ldots, 30$ 각각에 대해서, 해당 수 이하의 가중치를 가진 간선만 모았을 때, 쿼리마다 컴포넌트의 개수를 세는 문제를 해결하면 됩니다.

이 문제를 Union-find로 해결해 봅시다. $Q \times N$ 개의 정점에 대한 union-find를 관리할 수 없으니, $i, i + 1$ 번 레이어에 있는 $2N$ 개의 정점에 대한 union-find를 관리하고 이 정보를 $i+1, i+2$ 번 레이어로 움직여주는 식으로 처리합시다. 전체를 관리하지 않고 $2N$ 개만 관리해도 되는 이유는 Connection profile DP에서 마지막 줄에 대한 union-find만 관리해도 되는 이유 (더 간단하게는, 비트 DP에서 마지막 줄에 대한 비트마스크만 관리해도 되는 이유) 와 같은데, $i, i + 1$ 번 레이어 사이를 잇는 간선을 추가할 때 새롭게 merge가 되는 컴포넌트는 항상 $i$ 번 레이어의 정점이나 $i + 1$ 번 레이어의 정점을 포함하기 때문입니다. 이 과정에서 특정 컴포넌트를 대표하는 노드는 가장 깊은 레이어에 있어야 하니, 두 컴포넌트를 merge할 때 인덱스가 작은 쪽에서 큰 쪽으로 합쳐줘야 합니다. (당연한 이야기지만, 의외로 이후 과정에서 중요하게 사용됩니다.)

$i, i + 1$ 레이어에서 $i+1, i+2$ 레이어로 움직이는 것은, 단순하게는 위쪽 레이어를 없애준 다음에 아래쪽에 크기 1인 컴포넌트를 $N$ 개 만들어 주고, $M$ 개의 간선을 추가해 연결해주는 식으로 가능합니다. 이런 접근을 쓰면 $O(QM)$ 의 시간 복잡도를 피할 수 없을 것 같으나, 다음 핵심적인 관찰이 이 접근을 최적화하는데 도움을 줍니다:

• Observation. $G \times Path_i$ 에서 $u, v$ 가 연결되어 있다면 $G \times Path_{i + 1}$ 에서 $u + n, v + n$ 이 연결되어 있다.

이것은, $i, i + 1$ 레이어에 있는 Union-find를 초기화 없이 그대로 들고 다녀도 상관이 없다는 뜻입니다. $i + 1, i + 2$ 로 전이를 할 때 끊어야 하는 연결이 없기 때문입니다. 하지만 단순한 알고리즘을 돌아보면, 아래 ($i + 1$) 레이어에 있는 연결성 정보를 위쪽 ($i + 1)$ 레이어로 옮겨주는 작업이 필요함을 알 수 있습니다. 이를 위해서는, $i + 1$ 번 레이어의 연결성을 바꾼 모든 이벤트를 기억한 다음 이것을 이후 $(i + 1, i + 2)$ 번 레이어로 전이될 때 적용시켜줘야 합니다.

$(1, 2)$ 번 레이어에 대해서, 2번 레이어의 연결성을 바꾼 이벤트를 전부 기록해 봅시다. 인덱스를 작은 쪽에서 큰 쪽으로 합쳤기 때문에, 2번 레이어에 속한 두 정점이 합쳐졌다면, UF에서 merge한 두 정점의 번호가 모두 $n$ 초과입니다. 이렇게 합쳐지는 이벤트 $(u, v)$ ($n < u, v$) 들을 전부 따로 기록해 둔 후, 나중에 $(2, 3)$ 번 레이어로 넘어갔을 때 $(u - n, v - n)$ 을 합치는 데 사용하면 됩니다.

이제 $(2, 3)$ 번 레이어에 대해서, 아래쪽 레이어의 연결성을 바꾼 이벤트를 생각해 봅시다. 이 중 $(1, 2)$ 레이어에서 연결성이 바뀐 정점들은 고려할 필요가 없습니다. 이들은 이미 $(2, 3)$ 번 레이어로 넘어오는 과정에서 $(u - n, v - n)$ 을 합치는 데 사용하였고, 다시 이들을 고려해 봤자 이미 Union-find 상에서 합쳐진 정점들만 있기 때문입니다. 고로 $(2, 3)$ 번 레이어로 넘어오는 과정에서 합쳐진 간선들만 신경쓰고, 이들을 $(u - n, v - n)$ 을 합치는 데 사용하면 됩니다.

다시 일반적인 그림으로 돌아오면, $(i + 1, i + 2)$ 번 레이어로 넘어오는 과정에서 우리는 $(i, i + 1)$ 번 레이어의 아래 줄의 연결성을 위쪽 줄로 옮겨줘야 합니다. 아랫 줄의 연결성을 바꾼 시점이 여러 가지가 있겠지만, 만약 그 시점이 $(i - 1, i)$ 번 레이어 처리 단계 이전이라면, 신경 쓸 필요가 없습니다: 이미 $(i, i + 1)$ 번 레이어로 넘어올 때, 혹은 그 이전에, 이들은 $(u - n, v - n)$ 을 합치는 데 사용되었기 때문입니다. 고로 맨 처음에 $u, v > n$ 이었던 연결 이벤트들만 추리고, 이들로 $(u - n, v - n)$ 을 합치며, 이 과정에서 $u, v > n$ 이었던 연결 이벤트를 또 추리고... 를 $Q$ 번 반복하면 됩니다. 이렇게 되면 복잡도가 $O(QM)$ 이라고 볼 수 있지만, 각 간선을 처리하는 과정에서 컴포넌트의 개수를 줄이지 못한 간선은 다시 고려되지 않습니다. 고로 각 간선은 이벤트 리스트에서 삭제되거나, 컴포넌트의 개수를 하나 줄이는데, 컴포넌트의 최대 개수가 $2N$ 개이니, $O((N + M + Q) \alpha(N))$ 시간에 $(i, i + 1)$ 레이어의 컴포넌트를 관리할 수 있습니다.

이제 모든 것이 끝난 것 같으나.. 사실 컴포넌트의 개수를 세는 방법을 말하지 않았습니다. $(i, i + 1)$ 번 레이어의 컴포넌트의 개수는 Union-find에 추가 변수를 두는 식으로 쉽게 알 수 있습니다. 그 전에 사라진 컴포넌트의 개수는, Union-find에서 다음 레벨로 넘어갈 때 인덱스가 $n$ 이하인 컴포넌트의 개수들의 합입니다. 이것도 위와 비슷하게 추가 변수를 두면 관리할 수 있습니다. 그래서 쿼리마다 컴포넌트의 개수를 $O((N + M + Q) \alpha(N))$ 시간에 관리할 수 있고 이것을 30번 호출해 주면 전체 문제가 해결됩니다.