티스토리 뷰

ICPC/World Finals

ACM ICPC World Finals 2011

전명우 2015.05.18 20:51

문제 링크


K. Trash Removal


다각형이 주어질 때, 다각형이 쓰레기 장으로 들어가기 위한 통로의 최소 너비를 구하는 문제다. 임의의 두 점을 잡아 직선을 그렸을 때, 그 직선이 수직하게 들어간다고 가정하고 너비를 계산한다. 계산된 너비 중 최소 너비가 답이 된다. 이와 같은 알고리즘이 가능한 이유는 다각형을 덮는 볼록 껍데기를 생각했을 때 너비가 최소가 되는 경우는 볼록 껍데기의 변들 중 한 변이 통로의 변과 평행하기 때문이다.


코드 보기


C. Ancient Messages


그림이 주어졌을 때, 그림에 있는 고대 문자들을 모두 구해 사전순으로 정렬하여 출력하는 문제다. 이 문제에 있는 고대 문자들은 모두 글자 안에 있는 구멍의 개수가 다르기 때문에 구멍의 개수를 세어주어 문자들을 구분하면 된다.


코드 보기


E. Coffee Central


커피점들의 위치가 주어지고, 최대 20개의 쿼리가 주어진다. 각 쿼리 별로 맨하튼 거리가 $m$이하에 있는 커피점의 개수가 최대가 되는 가장 위-왼쪽점을 구하는 문제다. 우선 커피점이 있는 좌표계가 $1000 \times 1000$으로 작은 편이다. 맨하튼 거리가 $m$이하인 점들의 모양이 45도 회전된 정사각형 모양인데 $(x, y)$ 좌표를 $(x-y, x+y)$좌표로 바꾸면 맨하튼 거리가 $m$이하인 점들의 모양이 직사각형으로 바뀐다. 좌표계는 2배 커진다. 이와 같이 좌표계를 바꾸면 쿼리별로 어떤 직사각형 크기가 주어질 때, 가장 많은 커피점을 포함하는 직사각형의 위치를 구하는 문제로 바뀌게 된다. 직사각형의 위치를 정했을 때, 그 직사각형에 포함되는 커피점의 개수는 전처리(precompute)를 통해 O(1)에 계산 가능하다. 문제 해결을 위한 총 시간복잡도는 $O(q \times dx \times dy + n)$이다.


코드 보기


J. Pyramids


정육면체 큐브를 통해 여러 종류의 피라미드를 만들 수 있다. 문제에 주어진 조건들을 만족하면서 $c$개의 큐브를 모두 사용해 피라미드를 만드는 문제다. $c \leq 10^6$이므로 만들 수 있는 피라미드의 종류는 320가지이다. $c$개의 큐브를 모두 사용하여 만드는 피라미드의 최소 개수를 구하는 것은 쉽지만, 문제에 있는 조건들을 모두 만족하는 피라미드 구성을 구하는 것은 어렵다.

미리 계산을 해보면, $c$개의 큐브를 모두 사용하기 위해 만들어야하는 피라미드의 개수는 최대 6개임을 알 수 있다. 이를 이용해 Dynamic Programming을 하면 문제의 조건을 만족하는 피라미드 구성을 구할 수 있다.

"D[i][j] = i개의 피라미드를 만들어 j개의 큐브를 사용할 때, 만든 피라미드 중 크기가 가장 큰 피라미드의 최소 크기" 라고 정의하고 문제를 해결하면 된다. 문제 해결을 위한 연산 회수는 약 $6 \times 10^6 \times 320$이다.


코드 보기


H. Mining Your Own Business


임의의 도시 하나가 파괴 되었을 때, 파괴 되지 않은 도시에서 대피소로 대피할 수 있도록 대피소를 최소 개수로 적절히 설치하는 문제다. 최소 개수를 설치할 때 가능한 경우의 수 또한 구해야한다. 이중연결요소들과 그래프에서 절단점들을 구한다. 이중연결요소들 중에 절단점을 단 하나만 포함하고 있는 연결요소에만 대피소를 설치하면 최소 개수의 대피소로 모든 도시를 대피시킬 수 있다. 이와 관련된 증명으로는 절단점을 하나만 포함하고 있는 연결요소에는 반드시 대피소를 설치해야하며, 그 이외의 연결요소들에 대해서는 설치하지 않아도 됨을 보일 수 있다. 가능한 경우의 수는 (이중연결요소의 크기-1)의 곱이다. 답은 적어도 2가 되어야함에 유의하자.


코드 보기


F. Machine Works


기계가 $N$개 있고, 기계별로 살 수 있는 날짜, 살 때 가격, 되팔 때 가격, 하루에 벌어들이는 수입이 있다. 최대 한 개의 기계만 소지가능하며, 일정 기간동안 벌 수 있는 최대 수입을 구하는 문제다.

우선 기계들을 살 수 있는 날짜 순서대로 정렬하자. 그리고 Dynamic Programming을 생각해보면,

"D[i] = i번 기계를 사고 난 직후 남은 최대 돈" 으로 정의할 수 있다. 이와 같이 정의하면 점화식은

$D[i] = \max(D[j] + (day[i] - day[j] - 1) * gain[j] - buy[i] + resell[j])$ 이다.

$D[i] = - buy[i] + \max(D[j] - day[j] * gain[j]  - gain[j] + resell[j] + gain[j] * day[i])$로 식을 바꿀 수 있으며,

$E[i] = D[i] - day[i] * gain[i] - gain[i] + resell[i]$ 라고 정의한 경우,

$D[i] = -buy[i] + \max(E[j] + gain[j] * day[i])$ 로 재정의할 수 있다. 이제 Convex Hull Optimization을 통해 문제를 $O(N \lg N)$ 안에 해결할 수 있다.


+ 추가 설명

처음에 기계들을 살 수 있는 날짜로 정렬하지 않고 하루에 벌어들이는 수입으로 정렬을 하면 Convex Hull Optimization 과정이 보다 더 간단해진다.

날짜 순서와 상관 없이 하루에 벌어들이는 수입으로 정렬을 해도 문제를 해결할 수 있는 까닭은 기계를 살 때 가격이 기계를 되팔 때 가격보다 항상 비싸기 때문이다. 때문에 현재 있는 기계를 되팔고 수입이 같거나 작은 기계를 사는 행위로는 최대의 수입을 낼 수 없다.

아래 코드는 기계들을 날짜 순서대로 정렬한 뒤 문제를 해결하였다. 두 가지의 풀이법 모두 시간복잡도는 $O(N \lg N)$이다.


코드 보기


'ICPC > World Finals' 카테고리의 다른 글

ACM ICPC World Finals 2018  (0) 2018.05.08
ACM ICPC World Finals 2016  (0) 2016.06.18
ACM ICPC World Finals 2015  (1) 2015.05.22
ACM ICPC World Finals 2011  (0) 2015.05.18
댓글
댓글쓰기 폼