2018.10.16 problem solving

최근 카이스트 대회 기출 문제가 run.kaist.ac.kr/contest 에 전부 올라와 있습니다. 테스트 데이터나 풀이를 전부 공개하였으니 많은 관심 부탁드립니다! 맨 아래 과거 기출 문제 / Past Problemset 섹션에 모두 올라와 있습니다.

KAIST Contest 2018. Fractions

편의상, $A = C = 1$ 이라고 가정합시다. 이렇게 될 경우 $x, y$의 상한만이 존재하고 하한은 존재하지 않습니다. 이 가정을 하더라도 문제를 여전히 해결할 수 있는데, 만약에 위 문제를 해결하는 함수 $f(B, D)$ 가 존재한다면, 우리가 출력해야 하는 답은 포함-배제의 원리를 사용하여 $f(B, D) - f(A-1, D) - f(B, C-1) + f(A-1, C-1)$ 로 계산할 수 있기 때문입니다. (굳이 이렇게 생각하지 않아도 문제를 충분히 해결할 수 있습니다. 하지만 이러한 관점은 여러 문제들을 추상화시키는 데 매우 큰 도움을 주는 경우가 많기 때문에, 이해하고 넘어 가는 것을 추천합니다.)

이제, 문제를 거꾸로 생각해 봅시다. 분모와 분자 합이 1000 미만인 기약분수들을 모두 순회하고, 주어진 범위 안에서, 약분을 했을 때 해당 분모 / 분자가 나오는 분수의 개수를 모두 세어 줍시다. $\frac{p}{q}$ 라는 기약분수에 대해서, 그러한 분수는 $\frac{pN}{qN}$ 의 꼴이며, 고로 $pN \leq B, qN \leq D$ 를 모두 만족합니다. $pN \leq B, qN \leq D$ 를 모두 만족하는 자연수의 개수는 단순 나눗셈으로 세어 줄 수 있습니다.

어떠한 분수가 기약분수인지를 판별하는 것은, 유클리드 알고리즘으로 최대공약수를 구한 후, 1인지 아닌지를 계산해 주면 됩니다.

 

CF 2017 E. White And Blue

선거운동을 한 도시의 집합을 $S$ 라고 합시다. ($S$ 는 $\{1, 2, \cdots, n\}$의 부분 집합입니다, 예를 들어, $S = \{1, 3, 7\}$이면 1, 3, 7번 도시에서 선거를 진행합니다.) 이제 득표율이 $P$ 퍼센트 이상이 된다는 조건을 다음과 같은 식으로 쓸 수 있습니다.

$\frac{\sum_{i\in S}{a_i}}{\sum_{i\in S}{a_i} + \sum_{i\notin S}{b_i}} \geq \frac{P}{100}$

전개하면,

$100(\sum_{i\in S}{a_i}) \geq P(\sum_{i \in S}{a_i} + \sum_{i\notin S}{b_i})$

$100(\sum_{i\in S}{a_i}) \geq P(\sum_{i \in S}{(a_i - b_i)} + \sum_{i=1}^{n}{b_i})$

$(100-P)(\sum_{i\in S}{a_i}) + P(\sum_{i\in S}{b_i}) \geq P(\sum_{i=1}^{n}{b_i})$

$\sum_{i\in S}{((100-P)\times a_i + P\times b_i)} \geq P(\sum_{i=1}^{n}{b_i})$

우변은 선거운동을 어떻게 하든 바꿀 수 없으며, 입력에서 바로 계산할 수 있습니다. 한편으로, 좌변은 부분집합을 어떻게 골랐는지에 따라서 즉시 정해집니다. $f_i = (100-P)\times a_i + P\times b_i$ 라고 정의하면, 문제는 다음과 같이 바뀝니다.

$N$ 개의 수 $f_1, f_2, \cdots, f_n$ 이 주어졌을 때, 최소한의 수를 골라서 합이 일정한 숫자를 넘게 하여라. “

위 문제는, 합이 넘을 때까지 $f_i$ 가 큰 숫자부터 하나씩 고르면 풀 수 있습니다. 고로 $f_i$ 와 $P(\sum_{i=1}^{n}{b_i})$ 를 계산해 놓은 후 정렬 한번에 문제를 해결할 수 있습니다.

 

SRM 736 Medium. MinDegreeSubgraph

먼저 간단한 정의를 하고 시작합시다.

Definition. 그래프 $G$ 와 정점의 부분 집합 $S \subset V(G)$ 에 대해서, $S$ 에 속하지 않은 모든 정점들을 간선과 함께 지운 그래프를, 유도된 부분그래프 (Induced subgraph) 라고 부른다. 이를 $G[S]$ 라고 표현한다.

Remark. 부분 그래프에서, 정점을 몇 개 지운 후, 간선을 전혀 지우지 않은 버전입니다. 처음 들어봤다면 알아두는 것이 좋습니다.

첫번째 과정은, k-좋은 그래프의 표현을 단순하게 하는 것입니다. 부분 그래프라고 함은, 정점의 부분 집합을 고른 후, 부분 집합에 걸린 간선들의 부분 집합을 또 한번 고르는 과정으로 표현할 수 있습니다. 어떠한 정점 부분 집합을 골랐을 때, 최소 차수가 k가 되도록 간선을 적절히 제거하려면 어떻게 해야 할 까요? 최소 차수가 이미 k 미만이면 당연히 할 수 없고, k 이상이면, 최소 차수를 가진 점에서 (최소 차수)–k개의 간선을 아무거나 제거해 주면 최소 차수가 k가 됩니다. 이제 k-좋은 그래프의 정의를 아래와 같이 할 수 있습니다.

Lemma 1. 그래프 $G$가 $k$-좋은 그래프인 것은, 해당 그래프에 정점의 부분 집합 $S \subset V(G)$ 가 존재해서, $G[S]$ 의 최소 차수가 $k$ 이상이라는 것과 동치이다.

위 간단해진 정의를 통해서 쉽게 알 수 있는 사실은, k-좋은 그래프에 어떤 에지를 추가해도 k-좋은 그래프이며, k-좋지 않은 그래프에 어떤 에지를 제거해도 k-좋지 않은 그래프라는 것입니다. 그렇다면, 가장 작은 / 큰 그래프만 구해놓은 후, 마음대로 간선을 제거하거나 추가해서 개수를 m으로 맞춰두면 되니, 결국 다음 두 개의 문제를 해결하면 됩니다.

• 정점의 개수 $n$에 대해서, 간선의 개수를 가장 적게 쓰는 $k$-좋은 그래프와, 간선의 개수를 가장 많이 쓰는 $k$-좋은 그래프가 아닌 그래프를 찾아라.

먼저, 간선의 개수를 가장 적게 쓰는 $k$-좋은 그래프는 $k+1$ 크기의 완전 그래프입니다. 이보다 적은 $k$-좋은 그래프가 없음을 쉽게 보일 수 있습니다. 고로 $m \geq k(k+1)/2$ 이면 무조건 $k$-좋은 그래프가 존재합니다.

간선의 개수를 가장 많이 쓰는 $k$-좋지 않은 그래프는 조금 더 복잡합니다. 먼저 주어진 그래프가 $k$-좋은 그래프인지를 판별하는 방법을 생각해봅시다. 현재 주어진 그래프에서 차수가 $k$ 미만인 점이 있다면, 해당 점은 절대 부분 그래프를 이룰 수 없습니다. 이러한 점을 지우는 것을 반복하는 단순한 그리디 알고리즘을 사용하면, 판별이 가능합니다.

우리가 원하는 것은, 위 알고리즘이 차수가 $k$ 미만인 점들 (크기가 크면 좋으니, $k-1$ 인 점들) 을 반복적으로 지우다가, 결국에 마지막에 모든 점을 지워버리는 것을 원합니다. 정점 하나를 지울 때 같이 지울 수 있는 간선의 개수는 최대 $min(k-1, |V(G)| - 1)$ 입니다. 고로, $0 + 1 + \cdots + (k-2) + (k-1) + (k-1) + \cdots = (n-k)(k-1) + k(k-1)/2$ 이 해당 그래프가 가질 수 잇는 간선의 최대 개수가 될 것입니다. 위와 같은 최대 개수의 간선을 가지는 그래프를 만드는 것은, 정점 하나에서 출발하여 단순히 과정을 거꾸로 반복하면서, 차수가 $min(k-1, |V(G)| - 1)$ 인 정점을 반복적으로 이어주는 것으로 가능합니다. 고로 이 역시 판별이 가능합니다. $k = 0, k \geq n$ 일 때의 케이스에 유의하십시오.

 

JAG Autumn 2017. Revenge of the Broken Door

문제를 해결하기 앞서서 “전략” 이라는 것을 정리하는 것이 좋습니다. 공사중인 도로가 무엇인지 간파했다면 그 순간 취해야 할 전략은 자명합니다. 공사중인 도로를 제외한 그래프에서 $T$로 가는 최단 경로를 찾고, 그 경로로 가면 됩니다. 공사중인 도로가 무엇인지 간파하지 못했다면, 플레이어의 행동은, $S$ 에서 어떠한 결정된 경로를 따라서 움직이다가, 공사중인 도로를 만나게 되면 그 즉시 최단 경로로 이동하는 것입니다. 이 경로를 미리 정해놓으면, 공사중인 도로를 만나지 않은 이상 이 경로를 단순히 따라가다가, 공사중인 경로를 만나면 그 즉시 $T$ 로 가는 최단 경로로 모드를 전환하면 됩니다.

고로, 전략은 $S$에서 시작하는 어떠한 경로로 표현됩니다. 더 나아가서, 그 경로는 유한하고, $T$ 에서 종료합니다. 이 두 사실의 증명은 어렵지 않습니다.

이제 답을 찾는 것은 특정 조건을 최소화하는 $S-T$ 경로를 찾는 것과 사실상 동일합니다. 최적 전략이 $S-T$ 를 잇는 최단 경로 / 두번째 최단 경로라는 가정은 모두 반례가 존재하니, 명확한 풀이를 제시해야 합니다.

어떠한 전략(경로) 가 최악의 경우 소비하게 되는 시간을 계산해 봅시다. 경로를 정했을 경우, 어떠한 전략이 사용하는 시간은 모든 간선 끊김에 대해서 해당 경로가 사용하게 될 시간의 최댓값입니다. 이를 수식으로 표현하면, 어떠한 경로의 소비 시간은:

$max_{e \in E}((P$에서 간선 $e$ 를 만나는 데 걸리는 시간$) + ($해당 위치에서 $e$ 없이 $T$에 가는 최단 경로의 길이$))$

이것은 경로가 고정되었을 때 문제를 해결하기에는 충분하지만, 이것을 최소화하는 경로를 찾는 문제를 풀기에는 복잡한 식입니다. 가장 어려운 점은, 간선 $e$ 를 경로에서 한 번 이상 만날 수 있어서, 그 시간이 하나로 고정되어 있지 않고 여러 수의 최솟값으로 정의된다는 점입니다. 이 문제를 해결하기 위해서는 다음 Lemma가 필요합니다. (증명은 생략합니다.)

Lemma 1. 경로의 길이는, 최악의 경우 해당 경로에서 소비하는 시간보다 짧거나 같다.

이제 위 내용을 다시 돌아봅시다. 우리는 어떠한 경로 $P$가 소비하는 시간을 다시 정리할 수 있습니다. 모든 간선 $(u, v)\in E(G)$에 대해서,

• 만약에 그 간선이 $P$ 와 교점이 없다면 소비 시간은 $P$의 길이와 동일합니다.
• 그렇지 않고, $P$와 교점이 하나라면, 일반성을 잃지 않고 그 교점이 $u$라 하였을 때, ($P$에서 $S-u$ 경로 길이) + ($(u, v)$ 없는 그래프에서 $u-T$ 최단 경로의 길이) 라고 정의할 수 있습니다.
• $P$ 를 이루는 간선이라면, 일반성을 잃지 않고 경로에서 $u$ 가 먼저 등장한다고 합시다. 우리는 $e$ 가 끊겼을 때 걸리는 시간을 $max($($P$에서 $S-u$ 경로 길이) + ($(u, v)$ 없는 그래프에서 $u-T$ 최단 경로의 길이), ($P$에서 $S-v$ 경로 길이) + ($(u, v)$ 없는 그래프에서 $v-T$ 최단 경로의 길이)$)$ 라고 할 수 있습니다. $u$가 나오는 항은 자명히 참입니다. $v$가 나오는 항은, 위 답이 $P$의 길이보다 작거나 같음을 관찰할 수 있습니다. 고로 Lemma 1에 의해서 답에 영향을 끼치지 않습니다.

이러한 과정을 통해서, 답을 경로가 지나는 각 정점에 대해서 따로 생각할 수 있습니다.

각각의 정점에 대해서 $f(v) = (v$ 에서 임의의 간선이 제거되었을 때 $T$ 에 도달하는 데 걸리는 최소 시간) 이라고 정의합시다. $f(*)$ 는 모든 간선을 한번씩 제거해 본 후 Dijkstra 알고리즘을 사용하면 $O(M^2\log M)$ 에 찾을 수 있습니다. 이것이 문제를 해결하기에 충분하지는 않지만, 일단 다항 시간으로 복잡도를 줄여냈으니, 현재로서는 $f(*)$ 를 모두 잘 계산했다고 가정하고 여기서 멈춥니다.

우리가 찾는 경로 $P$는, 경로 상에 있는 모든 정점 $w$에 대해서, $dist(w) + f(w)$ 의 최댓값을 최소화해야 합니다. 답에 대한 이분 탐색을 사용해 봅시다. 답이 $X$이하인지를 판별하는 문제를 해결할 때, 우리는 경로 상의 각 정점 $v$에 대해서 $dist(V) \leq X - f(V)$ 를 만족하는 $S-T$ 경로를 찾아야 합니다. 이는 Dijkstra 알고리즘의 간단한 응용이니, 전체 문제를 $O(M\log M\log X)$ 에 해결할 수 있습니다. $T$에서 거꾸로 Dijkstra를 돌리면 $O(M\log M)$ 역시 가능합니다. 이에 대한 설명은 생략합니다.

마지막으로 우리는 $f(v)$를 빠르게 계산하는 방법을 알아봅시다. 정점 $T$에서 Dijkstra를 돌렸을 때, $T$가 아닌 모든 정점에 대해서 최단 경로를 따라가는 "포인터" 를 생각해 볼 수 있습니다. 이 포인터를 모두 모으면, 최단 경로를 모두 모으는 트리가 생기게 됩니다. 이를 Shortest Path Tree라고 부릅니다.

첫번째로 관찰해야 할 사실은, Shortest Path Tree 밖에 있는 간선을 끊는다고 최단 경로의 길이가 바뀌지 않는다는 것입니다. Shortest Path Tree상에 있는 간선이 보존되는 한 모든 최단 경로가 보존되기 때문입니다. 고로, 끊어봐야 할 간선은 $N-1$ 개 뿐이니 우리의 알고리즘을 $O(MN\log M)$ 으로 최적화 할 수 있습니다.

어떠한 정점 $v$ 와 이 정점의 조상 $parent(v)$ 로 가는 간선이 끊겼다고 합시다. $v$ 에서 찾을 "대안" 최단 경로는, $v$ 에서 시작해서, 서브트리 안에 있는 정점들을 거치다가, $v$의 서브트리 안과 밖을 잇는 간선을 최소 한번 이상 지나서 서브트리를 탈출하고, 이후 여러 정점을 거치다가 최종적으로 $T$에 도달할 것입니다.

이 과정에서, 서브트리를 탈출하는 첫 순간을 주목하면 재미있는 관찰을 할 수 있습니다. 서브트리를 탈출한 에지가 $(p, q)$이고 $p$가 $v$의 서브트리 안에 있다고 합시다. $q$로 나온 순간, 대안 최단 경로는 Shortest Path Tree상에 있는 경로를 따라가지 않을 이유가 없습니다 (끊기지 않았기 때문), 마찬가지로, $v$에서 $p$로 가는 경로는 $T$에서 $p$로 가는 최단 경로의 일부이고 끊기지 않았기 때문에, 이 역시 Shortest Path Tree를 그대로 사용하면 됩니다.

간선 $(p, q)$의 가중치를 $weight(p, q)$, 두 정점의 최단 거리를 $Dist(p, q)$ 라 정의합시다. 서브트리를 탈출할 때 사용한 간선 $(p, q)$를 고정시키면, $p$와 $q$가 서브트리 안밖을 잇는 모든 $v$에 대해서, $parent(v) - v$로 가는 경로를 $weight(p, q) + Dist(T, q) + Dist(T, p) - Dist(T, v)$ 로 대체할 수 있게 됩니다. 이 정보는 한 번의 Dijkstra로 계산할 수 있으니, 이를 모든 간선과 정점 쌍에 대해서 상수 시간에 계산해 주면 시간 복잡도 $O(NM)$에 문제를 해결할 수 있습니다.

마지막으로, $(p, q)$가 대체 경로로 사용될 수 있는 정점들은, $LCA(p, q)$와 $p$를 잇는 경로 상의 정점들이라는 것을 알아낼 수 있습니다. 고로, 모든 $T$가 아닌 정점 $v$에 대해서, 올바른 "탈출 간선"이 가지는 최소의 $Dist(T, q) + Dist(T, p) + weight(p, q)$을 배열 등에 저장해 두면, 결국 문제는

1. LCA를 빠르게 계산하고
2. 어떠한 조상 - 자식 경로에 대해서, 경로 상 간선에 $ans[v] := min(ans[v], X)$ 쿼리를 반복적으로 수행하는

문제가 됩니다.

첫번째 문제는 잘 알려진 문제로, Sparse Table 알고리즘을 사용해서 해결할 수 있으며, 두 번째 문제는 쿼리를 오프라인으로 X 순으로 정렬한 후, 각 경로에 대해서 Path Compression을 사용해 주면 됩니다. Path Compression에 대한 간략한 정보는 http://codeforces.com/blog/entry/21476 에서 확인할 수 있습니다.

$f(*)$ 를 효율적으로 구할 수 있으니, 이제 모든 문제가 $O(M\log M\log X)$ 에 해결됩니다. 수고하셨습니다. :D