20200809 problem solving

POI 1996. Canoes

먼저 각각의 사람을 몸무게 순으로 정렬해 놓읍시다. 가장 가벼운 사람은 다른 사람과 보트를 태워 보내는 것이 합리적으로 보이니, 가장 가벼운 사람을 보낼 때는, 다른 사람 한 명을 잡아서 같이 보트를 태워 보냅니다. 같이 탈 수 있는 사람이 여럿이면 물론 몸무게가 무거운 사람을 보내는 것이 현명합니다. 두 번째, 세 번째로 가벼운 사람들에게 이를 반복하고, 같이 태워 보낼 수 있는 사람이 없을 때까지 이를 반복합니다.

이 알고리즘의 구현은, 정렬된 배열에서 현재 보낼 무거운 사람의 “포인터” 를 가지고 있으면 간편합니다. 가벼운 사람이 있을 때, 이 사람의 몸무게를 맞출 수 있을 때까지 포인터를 앞으로 (몸무게가 감소되는 쪽으로) 내려주고, 그 사람과 매칭시킨 후, 포인터를 다시 내려줍니다. 시간 복잡도는 $O(N \log N)$ 입니다.

이 그리디 알고리즘의 정당성은 다음 Lemma에 의해 보여집니다.

Lemma. 2인 보트를 T번 보낼 때, 가장 가벼운 T명이 서로 다른 2인 보트에 타는 해가 항상 존재한다.

증명은 귀류법으로 가능합니다. 문제의 난이도에 비해서 증명이 그렇게 쉽지 않습니다. 여기서는 생략합니다.

다른 방법으로는, 답 $T$에 대해서 이진탐색한 후, $a_i + a_{2T-1-i} \le W$ 가 모든 $0 \le i \le T-1$ 에 대해서 성립하는 지 보는 것입니다. 역시 시간 복잡도는 $O(N \log N)$ 이며, 정당성은 위 Lemma에 의해 자명합니다.

AMPPZ 2019 A. Assimilation

문제 조건에 의해, 모든 조건은 “침략” 당하거나 “침략 후 동원” 당해야 합니다. 동원의 과정을 보면, 침략에 사용했던 모든 함선을 보상받을 뿐만 아니라 원래 있던 인구만큼의 추가적인 함선을 받을 수 있습니다. 고로 “침략 후 동원” 을 실시할 경우, 초기 자본금만 있으면 항상 이득을 볼 수 있습니다. 반면 어떠한 행성을 침략만 하는 것은 무조건 현재 함대의 개수를 줄이므로 손해입니다. 결국 어떠한 행성을 동원할 지 안 할 지의 여부가 결정되었다면, 맨 처음 동원하기로 결정한 행성들을 전부 동원한 후 나머지 행성들을 침략하는 것이 최적입니다 (도움이 되지 않는 침략을 서두를 이유가 없습니다).

나머지 행성들을 침략할 수 있다는 것은, 지금까지 남은 행성들의 인구 수 합이 현재 함선 개수 이하라는 뜻입니다. 고로, 이 차이를 최대한 빨리 줄이는 전략을 사용하는 것이 좋을 것입니다. X명이 있는 한 행성을 침략+동원하면, 현재 함선의 개수는 +X, 남은 인구수는 -X가 되니, 침략할 수 있는 행성 중 X가 가장 큰 행성을 침략하는 것이 최적 전략이고, 이를 반복하면 O(N^2) 알고리즘을 찾을 수 있습니다. 이를 $O(N \log N)$ 으로 최적화하려면, std::set 을 사용하면 됩니다.

CERC 2018. Shooter Island

새롭게 물이 차는 점들의 리스트를 알고 있다면 (혹은, 직사각형 영역이 항상 $1 \times 1$ 격자라면) 이 문제는 Union-find를 사용해서 해결할 수 있습니다. 한 점에 물이 차게 된다면, 이 점과 4방향으로 인접한 점들로 이동할 수 있게 됩니다. 고로 정점 1개와 이러한 최대 4개의 간선을 그래프에 추가해 주면 되는데, 정점 추가는 간단하고 간선 추가는 Union-Find를 사용하면 알 수 있습니다.

새롭게 물이 차는 점들의 리스트를 각 쿼리마다 찾는 것이 문제입니다. 한 점에 물이 차면 다시 되돌아가지 않으니, 대략 그러한 점의 개수에 비례하는 시간이면 충분합니다. 50개의 줄을 따로 따로 처리한다고 생각하면, 어떠한 $y$ 좌표 구간에 대해서 물이 안 찬 점들의 리스트를 찾고 지워야 합니다. 이는 std::set으로 할 수 있습니다. 살짝 느리다면 상수 최적화를 하거나 (예를 들어 std::set을 초기화할 때 insert를 5백만번 하지 않게 합시다), 아예 path compression을 사용해서 std::set 구현을 스킵하면 됩니다. Path compression을 사용해서 이 문제에서 std::set을 어떻게 대체할 수 있는지는 소개하지 않습니다.

CERC 2012. The Dragon and the Knights

전체 지역의 개수와, 이 중 기사가 차지하는 지역의 개수를 각각 센 후 두 값을 비교할 것입니다.

먼저 지역의 개수를 세어 봅시다. 맨 처음 지역의 개수는 1개입니다. 이후 직선이 추가되면, 이 직선 자체가 지역 하나를 늘려주며, 직선이 만나는 지점마다 추가적으로 직선이 하나씩 늘어남을 알 수 있습니다. 고로 직선 하나를 추가하면, 1 + (이 직선과 평행하지 않은 직선 수) 만큼 새로운 지역이 추가됩니다. 두 직선이 평행한지, 그렇지 않은 지는 $a_i b_j = b_i a_j$ 식을 통해서 쉽게 판단할 수 있습니다.

이제 기사가 차지하는 지역의 개수를 세어 봅시다. 하나의 직선은 영역을 $Ax+By+C$ 가 0 초과인 영역과, 미만인 영역으로 나눕니다. 기사가 차지하는 지역이 같다는 것은, 모든 직선에 대해서 $Ax+By+C$ 의 부호가 같다는 것과 동치입니다. 고로 부호를 이진수로 저장하면 어떠한 지역은 길이 $N$ 의 이진수로 저장할 수 있고, 이 수가 같을 때만 지역이 같다고 하면 됩니다. $N \le 60$ 일 경우 이 정보는 long long 변수 하나 안에 담을 수 있겠으나, 아쉽게도 여기서는 $N \le 100$ 이라 비트를 쪼개거나 int128을 쓰는 등의 추가적인 노력이 필요합니다. 시간 복잡도는 $O(MN)$ 입니다.

AMPPZ 2019 E. The Great Drone Show

각 간선이 언제 끊기는지를 계산 (안 끊긴다면 $\infty$) 했다면, 쿼리를 처리하는 것은 잘 알려진 문제입니다. $Q$ 개의 시작점과 끝점이 주어졌을 때, 경로 상 최솟값을 최대화하는 문제는, 끊기는 시점을 cost로 한 maximum spanning tree를 찾은 후 경로 최솟값을 구하는 식으로 해결할 수 있습니다. 그래프가 연결되어 있음이 보장되어 있으니 모호한 것도 없습니다. 이는 sparse table을 사용하여 $O(Q \log N)$ 에 할 수 있습니다.

이제 각 간선에 대해서 이 간선이 언제 끊기는 지를 계산해야 합니다. 적당한 수학을 통해서, 간선의 양 끝점의 값이 특정 정수를 넘는 첫 지점을 찾는 문제와 동일함을 볼 수 있습니다. 단순하게는 $O(MK)$ 시간에 계산할 수 있습니다.

이것을 각 간선에 대한 쿼리 문제로 해석해 봅시다. 하나의 쿼리를 볼 때 단순하게 양 끝점에 있는 이벤트를 나열하는 식으로 처리할 수도 있겠지만, 각 끝 점의 이벤트를 전처리 해놓고, 작은 쪽에서 전처리된 구조에 적당한 질의를 날려서 해결할 수도 있습니다. 예를 들어, 일반성을 잃지 않고 간선 $e = (u, v)$ 에 대해서 $u$ 쪽의 갱신 이벤트가 $v$ 쪽의 갱신 이벤트보다 개수가 적다면, $u$ 쪽의 갱신 이벤트를 순회한 후 각 이벤트에 대해서 $u$ 의 높이를 상수라고 생각해 줄 수 있습니다. 그러면 특정 시간 구간에 대해서 $v$ 가 $u$의 높이와 특정 범위 이상 차이가 나는 순간이 있는지를 판별하는 문제가 됩니다. 이는 이 시간 구간에 대한 최솟값/최댓값을 계산해 주면 알 수 있고, 고로 세그먼트 트리를 사용할 수 있습니다. 그 구간에서 어느 시점에 끊기는 지를 찾는 것은 세그먼트 트리를 타고 내려가는 식으로 계산할 수 있습니다 (다만 sparse table을 쓰는 쪽이 더 빠르고 구현이 편할 것 같습니다). 그래서 $|Upd_u| \times \log |Upd_v|$ 시간 정도에 문제가 해결됩니다. 편의상 그냥 $|Upd_u| \log N$ 시간이라고 합시다. 구현도 그렇게 하는 쪽이 훨씬 빠르고 간편할 것입니다.

이것을 토대로 IOI 2009 Regions와 비슷한 복잡도 분석을 하면, 시간 복잡도가 대략 $O((M + K)^{1.5} \log (M + K))$ 정도가 됨 역시 알 수 있습니다. 중복 간선이 없기 때문에 중복 쿼리를 메모이제이션할 필요가 없음을 알아두면 좋습니다. 여기까지 하면 문제를 맞기에는 살짝 느리고, 더 최적화하기도 힘들어 보입니다. 한편으로 저희가 그래프의 성질을 거의 사용하지 않았다는 점도 주목해야 합니다. 그냥 각각의 간선을 하나의 쿼리로 판단하여 처리했을 뿐입니다. 고로 그래프의 성질, 특히 문제에서 주어진 평면 그래프 라는 강력한 성질을 사용해 보고 싶습니다.

평면 그래프에는 항상 degree가 5 이하인 점이 존재합니다. $e \le 3v-6$ 임을 사용해서 귀류법으로 쉽게 보일 수 있습니다 (5색 정리를 증명할 때 자주 나오는 lemma입니다). 이런 식으로 이러한 최소 차수 정점을 반복적으로 제거해서 정점들의 ordering $v_1, v_2, \ldots, v_N$ 을 구성합시다. 구성에 따라서, 어떠한 $i$ 에 대해 $i < j$ 이며 $v_i, v_j$ 간 간선이 있는 $j$ 의 개수는 5개 이하입니다. 이 ordering을 직접 구성해서, ordering 상에서 먼저 나오는 집합을 순회하는 규칙으로 문제를 해결했다고 합시다. 모든 간선에 대해서 쿼리를 전부 처리했을 때, 각 정점에 대해서 해당 정점에 속한 이벤트가 "순회된" 횟수가 최대 5번이고 모두 더하면 $K \times 5 \times \log K = O(K \log K)$ 시간이 소모됩니다. 고로 전체 문제가 $O(K\log K)$ 정도에 해결됩니다.

그런데 ordering을 구할 필요가 있을까요? 처음 생각한 개수가 "작은" 쪽에서 돌리겠다는 전략은 "ordering에서 먼저 나온" 쪽에서 돌리겠다는 전략보다 무조건 우수합니다. 탐색 크기를 절대 늘리지 않기 때문입니다 (어차피 $\log N$ 항이라고 가정했으니). 고로 지금까지 한 얘기는 결국 처음 생각한 알고리즘의 복잡도가 사실 $O(K \log K)$ 라는 증명, 그 이상도 이하도 아니게 됩니다. 그래서 평면 그래프가 주어졌지만, 간선을 그래프에 저장할 필요가 전혀 없이 그냥 쿼리로 받아서 생각해도 시간을 계산하는 데 문제가 없습니다.

Codeforces #620 Div2B. Longest Palindrome

문자열의 길이가 같으니까 많은 문자열을 모아두면 됩니다.

모은 문자열의 개수가 짝수라고 가정하면, 해당 문자열, 그리고 그것을 뒤집은 문자열로 매칭되는 쌍을 최대한 많이 모아주면 됩니다. 모든 문자열이 다 다르고, 제한이 작기 때문에, 그리디하게 매칭해 주면 됩니다.

홀수라고 가정하면, 중간에 팰린드롬이 하나 와야 합니다. 모든 문자열이 다르니까 팰린드롬은 매칭에 들어가지 않습니다. 고로 매칭되지 않은 팰린드롬이 있었다면 중간에 끼워넣으면 됩니다.

NAC 2020 K. Rooted Subtrees

주어진 트리가 $1, 2, \ldots, n$ 까지 번호가 붙은 직선 이라고 생각하면, $r$ 을 루트로 한 서브트리는, 트리 전체이거나, $r$ 을 포함하지 않는데 $1$ 이나 $n$ 을 포함하는 구간이 됩니다. 이 문제는 결국 이러한 두 구간의 교집합으로 가능한 경우를 세는 문제가 됩니다. 교집합이 $n$ 을 포함하는 경우, $1$ 을 포함하는 경우, 둘 다 포함하지 않는 경우로 케이스를 나누면, 결국 답은 두 점의 거리의 제곱에 비례하는 어떤 수라는 것을 알 수 있습니다.

직선을 트리로 일반화해도 비슷한 논리를 펼칠 수 있습니다. 이 경우에는 $1$ 과 $n$ 을 포함한다는 정의 대신, 경로의 왼쪽 끝을 벗어났느냐, 오른쪽 끝을 벗어났느냐는 정의를 사용하면 됩니다. 어쨌든 여기서도 답은 두 점의 거리의 제곱에 비례하는 어떤 수가 됩니다.

최종적으로 문제는 트리에서 두 점간의 거리를 계산하는 문제로 환원되는데, 이는 흔히 Sparse table이나 Binary lifting이라고 하는, LCA를 $O(\log n)$ 에 계산하는 알고리즘을 사용하면 해결할 수 있습니다.

Petrozavodsk Winter 2020 Day9A. Alternative Accounts

4개 이하의 클리크의 합집합으로 이루어진 그래프에서 최소 vertex coloring을 찾는 문제입니다. 각 클리크 집합을 $S_1, S_2, \ldots, S_k$ 로 표현합시다.

$k = 1$ 이면 답은 당연히 $|S_1|$ 입니다.

$k = 2$ 이면 답은 $\max(|S_1|, |S_2|)$ 입니다. 일단 저만큼이 필요한 것은 당연합니다. 실제 배정은, $S_2$ 에 쓴 색 중 $S_1$에 안 쓴 색을 반복적으로 칠해주는 식으로 찾을 수 있습니다.

$k = 3$ 이면 답은 $max(|S_1|, |S_2|, |S_3|)$ 보다 커집니다. ${1, 2}, {2, 3}, {3, 1}$ 을 생각해 보면 됩니다. 일단 $S_1 \cap S_2 \cap S_3$ 에 배정된 색은 다른 곳에서 쓸 수 없습니다. 고로 그래프에서 지우고 색칠 수에 $|S_1 \cap S_2 \cap S_3|$ 을 더해 줍시다. 이제 $S_1 \cap S_2, S_2 \cap S_3, S_3 \cap S_1$ 세 집합은 disjoint합니다. 또한 이 세 집합에 배정된 색도 겹치면 안 됩니다. 이제 이것도 지우고, 각 집합에 남은 색을 칠해주면 됩니다. 굳이 복잡하게 계산해 줄 필요 없고, $max(\text{지금까지 쓴 색}, |S_1|, |S_2|, |S_3|)$ 이라고 하면 됩니다. 이렇게 되면 교집합에 대한 식으로 쓸 수 있습니다.

이런 식으로 보니 $k = 4$ 일 때도 비슷하게 케이스를 나누면 될 것 같습니다. 4개의 교집합에 먼저 색을 배정하고, 3개의 교집합에도 서로 다른 색을 배정합시다. 2개의 교집합에 대해서도 지금까지 배정된 색과 전부 다른 색을 써야 합니다. 하지만 서로 complement 관계에 있는 두 집합 ($S_1, S_4$ 와 $S_2, S_3$) 은 같은 색 집합을 공유해도 됩니다. 그래서 거기서는 max 관계 ($max(|S_1 \cap S_4|, |S_2 \cap S_3|)$) 를 써도 괜찮습니다. 이제 $S_1, S_2, S_3, S_4$ 만 남습니다. 여기에는 이제 남은 색들을 배정하면 되니 위처럼 똑같이 해 주면 됩니다.

집합이 비어도 되어서, 구현할 때 이 4개의 케이스를 전부 구현할 필요가 없이 $k = 4$ 만 구현해도 된다는 점에 유의하세요.

Petrozavodsk Winter 2020 Day7H. Hit

고정된 $K$ 에 대해서, 한 segment에 1개 이상 $K$ 개 이하의 점이 올라오도록 점을 배치하는 것이 가능한지를 판별합시다. 이렇게 하면 $K$ 에 대해서 이분탐색만 하면 되기 때문에, 문제를 거의 해결했다고 생각할 수 있습니다. 좌표압축을 시행해서, 모든 끝점이 $[1, 4N]$ 사이의 정수라고 가정합시다.

$MinEndpoint(i) = $ ($i + 1 \le l_j$ 인 모든 $j$ 중 $min (r_j)$) 라고 정의합시다. 즉, $i$ 번 점 오른쪽에 있는 모든 선분 중 끝점이 가장 작은 선분의 끝점이 됩니다. 예를 들어, 점을 최소로 배치해서 모든 구간에 점을 올리는 문제는

x = 0
while MinEndpoint(x) <= 2*N:
    MinEndpoint(x)에 점 배정
    x = MinEndpoint(x)

과 같이 해결할 수 있습니다.

$K$ 개의 점을 배치하는 문제를 해결하기 위해서, 각각의 셀에 점을 놓았을 때 가능한 해가 있는지를 판별합시다. $Valid[x]$ 는, $x$ 에 점을 배치하였을 때, $x$ 초과의 좌표들에 점을 적당히 배치해서

• $r_i \geq x$ 인 모든 구간이 점을 하나 이상 가지게 하고
• 각 구간에 $K$ 개 이하의 점이 올라오도록

배치하는 것이 가능하면 1, 불가능하면 0이라고 정의합시다. 정의에 의해, $Valid[0]$ 이 참이라면 답이 존재하며, 그렇지 않다면 답이 존재하지 않습니다.

$Valid[x]$ 를 판별하기 위해서, $x$ 의 바로 오른쪽에 배치하게 될 점인 $nxt(x)$ 를 결정합시다.

• 당연하지만, $Valid[nxt(x)] = 1$ 이어야 합니다.
• 첫번째 조건을 만족하기 위해서는, $nxt(x) \le MinEndpoint(x)$ 여야 하고, 그리고 그것만 만족하면 충분합니다.
• 두번째 조건을 만족하기 위해서는, $nxt^{K}(x)$ 와 $x$ 가 같은 구간에 속하면 안 됩니다. 즉, 거리가 가장 멀어야 합니다.

두번째 조건을 만족시키는 것이 어렵습니다. $nxt^{K}(x)$ 가 $x$ 와 같은 구간에 속하지 않기 위해서는 저 값이 최대화되는 식으로 모든 $nxt(x)$ 를 조정해야 하는 것을 알 수 있습니다. 이 때, 모든 점에 대해서 $nxt(x)$ 를 각각의 위치에서 가능한 최대로, 즉, $Valid[nxt(x)] = 1$이며 $nxt(x) \le MinEndpoint(x)$ 인 최대 $x$ 로 설정해 주는 것이 문제를 해결하는 데 충분하다는 것을 증명할 수 있습니다. 이유는, 모든 Valid한 $i$ 에 대해 저러한 최대 $x$ 는 $i$ 가 증가하면서 단조 증가하기 때문입니다. 하나의 $nxt(x)$ 에 대해서 저것이 처음으로 어긋나는 지점이 있으면, 그것을 어긋나지 않게 바꿔주는 것이 문제를 해결하는 데 방해를 하지 않습니다.

마지막으로, 위 조건이 모두 만족한다면, $0$에서부터 $nxt(x)$ 를 역추적하는 식으로 올바른 해를 항상 찾을 수 있기 때문에, 항상 답이 됨을 알 수 있습니다. 고로 필요충분이 성립합니다.

위 알고리즘을 단순하게는 $O(n^2)$ 에 구현할 수 있지만, $nxt(x)$ 는 Two pointers로 찾고, $nxt^{K}(x)$ 와 $x$ 가 같은 구간에 속하는 지는 sparse table로 찾으면 되기 때문에 $O(n \log n)$ 에 찾아줄 수 있습니다. 최종 시간 복잡도는 $O(n \log^2 n)$ 입니다.

마지막으로, 시간 복잡도를 $O(n \log n)$ 으로 줄이는 간단한 방법이 있습니다. 맨 처음 소개한, 각 점에서 최대 배치를 최소화하려 하지 않는 그리디에서의 답을 $T$ 라고 합시다. 그렇다면 최적해는 $T - 1$ 아니면 $T$ 가 됩니다. 그리디 배치는, 구간들의 최대 독립 집합을 찾고 그 집합의 끝점을 마킹한 것과 같은 식입니다. 그리디 배치에서 어떠한 구간이 $T$ 개의 점을 포함한다면, 이 구간에 포함되는 $T-1$ 개의 겹치지 않는 구간이 존재한다는 뜻입니다. 고로 이 구간 안에는 $T - 1$ 개의 점이 필요합니다. 이렇게 되면 이분 탐색이 필요하지 않아서 $O(n \log n)$ 풀이를 유도할 수 있습니다.