티스토리 뷰

ICPC/World Finals

ACM ICPC World Finals 2015

전명우 2015. 5. 22. 08:28

문제 링크


A. Amalgamated Artichokes


1부터 N까지 정수 k가 있을 때, price(k) 에 대해 최대 감소폭을 구하는 문제다. 이전까지 나온 최대 값을 저장해두고 현재 값이 최대값 보다 같거나 작다면 최대 감소폭에 차이를 갱신해주고, 현재 값이 최대값 보다 크다면 최대값을 갱신해주면 된다. 시간복잡도는 $O(N)$이다.



D. Cutting Cheese


$100 \times 100 \times 100$ 크기의 정육면체 치즈가 있다. 이 치즈에 구 모양의 구멍이 뚫려 있고, 이 구 모양은 치즈의 범위를 벗어나지 않으며 교차하지도 않는다. 이 때, 치즈를 xy평면에 평행하게 잘라 같은 부피로 $s$ 조각으로 자를 때 자르는 위치를 구하는 문제다.

$z1$에서 $z2$ 사이의 부피를 구하는 것은 $O(N)$에 가능하다. 우선 전체 치즈 부피 $V$를 계산하고 각 치즈 조각의 부피 $u = \frac{V}{s}$를 구한다. 직접적으로 수식을 계산할 수도 있지만 이분검색을 통해 부피가 $u$가 되는 자르는 지점을 구할 수 있다.



F. Keyboarding


$R \times C$ 크기의 직사각형 화상 키보드 격자가 주어지고 방향키와 선택키를 이용하여 문자를 입력할 수 있다. 주어진 문자열을 입력하기 위해 필요한 최소 누르는 회수를 구하는 문제다. 여담으로 이 문제는 대회 측에서 HARD로 분류되었지만, 세 번째로 가장 많이 풀린 문제고 매우 간단한 문제다.

D[i][y][x] = 주어진 문자열 중 앞의 i개의 문자를 입력했고 현재 커서가 (x, y)에 있을 때 버튼을 누른 최소 회수

라고 배열을 정의한 뒤, bfs를 돌리면 된다. 시간복잡도는 $O(LRC)$다.



I. Ship Traffic


각 레인 별로 방향이 정해져있고, 배가 모두 같은 속력으로 지나간다. 이 때 크기가 아주 작은 요정이 지나가는데 요정이 배와 충돌하지 않으면서 출발할 수 있는 시간 간격 중 최대 간격의 크기를 구하는 문제다. 모든 배에 대해서 요정과 충돌하는 시간 구간을 구할 수 있다. 그리고 그 시간에 요정이 그 위치에 있는 요정의 출발 시간 또한 계산할 수 있다. 즉, 각 배에 대해서 이 배와 요정이 충돌할 때 요정의 출발 시간 구간을 계산할 수 있다. 결국 요정의 출발 시간으로 불가능한 구간이 배의 개수 만큼 있고, 이 구간들을 시작 시간 순서로 정렬하면 요정이 출발 가능한 시간 간격들을 모두 구할 수 있다.



C. Catering


1번이 출장 뷔페 본부고 2번부터 $n+1$번 지점까지 출장 뷔페를 다녀야한다. 출장 뷔페를 다니기 위해 본부는 $k$개의 트럭을 가지고 있다. 번호가 작은 곳에서 큰 곳으로만 이동할 수 있고 같은 곳을 여러번 방문하지 못할 때, 최대 $k$개의 트럭을 이용해 최소 이동거리로 모든 지점을 방문하는 문제다. MCMF를 생각할 수 있다. 우선 각 지점에 방문했음을 알기 위해 정점을 두 개의 정점으로 나누고 간선을 하나 만들어준다. 한 정점을 최대 한 번 방문할 수 있으므로 그 간선의 유량은 1이고 비용은 $-10^{10}$으로 하자. 그리고 1번 정점에 대해서는 그 간선의 유량을 $k$로 하고, 비용은 0으로 한다. 이렇게 그래프를 디자인하고 Max flow 중 Min cost를 구하면, 최대 $k$개의 트럭이 사용됨이 보장되고, 각 정점에 방문했을 때 비용이 $-10^{10}$이므로 $n$개의 정점을 모두 방문함이 보장된다. (최소 비용에는 반드시 $-10^{10}$이 $n$개 포함될 것이며, 이런 경우는 반드시 존재하기 때문)



L. Weather Report


날씨를 4종류로 분류할 수 있다. 각 날에 대해서 독립적으로 날씨가 일어날 확률이 있다. $n$일이 지난 후 가능한 $4^n$가지에 대해서 서로 구분 가능하게 (한 가자의 비트가 어떤 다른 가지의 비트의 prefix가 되지 않도록)  표현할 때 기대값의 최소값을 구하는 문제다.

문제 설명이 다소 복잡한 문제다. 반드시 원본 문제를 읽는 것을 권장한다. 이 문제를 느리게 해결하는 방법은 $4^n$가지에 대해서 일어날 확률들을 구하고 $4^n$개의 확률에 대해서 Huffman coding을 했을 때 String의 길이를 구하면 된다. 우선 Huffman coding을 이용하는 이유에 대해서 설명하자면, 문제에서 설명한 구분 가능한 조건이 있을 때 가장 좋은 압축률을 보여주는 알고리즘이 Huffman coding 이다. 확률에 대해서 Huffman coding을 한다는 것은 확률을 빈도 수로 보고 Huffman coding을 했을 때, String의 길이가 기대값이 되기 때문이다. 이 느린 방법을 생각하고 나면 문제 해결이 쉬워진다.

위의 느린 방법에서는 $4^n$개의 확률에 대해 Huffman coding을 했지만, 가능한 확률 종류의 개수는 $_{21}H_{3} = 1771$가지 밖에 없다. 이 확률들을 묶어서 Huffman coding을 하면 빠른 시간안에 문제를 해결할 수 있다. 소스 코드를 참고하며, 소스 코드에서 필요한 연산 수는 $1771 \times 40$에 비례한다.



J. Tile Cutting


직사각형 타일 격자에 평행 사변형을 꽉 채워 그릴 수 있다. 여러 개의 테스트케이스가 주어졌을 때, 가능한 평행사변형의 최소 면적과 최대 면적이 주어진다. 면적 별로 그릴 수 있는 평행사변형의 개수가 있는데, 면적 범위 내에서 그릴 수 있는 평행사변형의 개수가 가장 많은 면적과 그 때의 개수를 구하는 문제다.

직사각형의 윗 변에 닿은 평행사변형의 꼭지점이 윗 변을 왼쪽 길이 $a$, 오른쪽 길이 $b$로 나눈다고 하고, 직사각형의 왼쪽 변에 닿은 평행사변형의 꼭지점이 위쪽 길이 $c$, 아래쪽 길이 $d$로 나눈다고 하자. (그림을 그리지 않고 설명하려니 복잡하다...) 그 때 평행사변형의 넓이는 $(a+b)(c+d) - ac - bd = ad + bc$가 된다. "cnt[i] = 어떤 두 자연수를 곱했을 때, i가 되는 경우의 수"라고 정의하자. 이는 에라토스테네스의 체를 이용하여 $O(n \lg n)$에 계산 가능하다. 면적이 4인 평행사변형의 개수는 $cnt[1] \times cnt[3] + cnt[2] \times cnt[2] + cnt[3] \times cnt[1]$이 된다. 면적이 5인 평행사변형의 개수는 $cnt[1] \times cnt[4] + cnt[2] \times cnt[3] + cnt[3] \times cnt[2] + cnt[4] \times cnt[1]$이다. 각 면적 별로 가능한 평행사변형의 개수를 빠르게 계산하는 것은 FFT(Fast Fourier Transform, 고속 푸리에 변환)을 이용해 $O(n \lg n)$에 해결 가능하다.



E. Evolution in Parallel


$n$개의 화석이 있다. 화석에 포함된 유전자 정보는 문자열로 나타내어진다. 유전자 배열 A, B가 있을 때, B의 문자열이 A의 문자열의 subsequence인 경우 A는 B에서 진화되었다고 볼 수 있다. 문제는 현 시대의 유전자 배열이 주어졌을 때 두 종류의 진화 경로를 구하는 문제다.

아주 당연한 얘기지만, 진화하면 길이가 증가하므로 화석들을 유전자 문자열 길이 순으로 정렬하고 문제를 해결한다.

문제를 해결하기 위해 편의상 왼쪽 경로, 오른쪽 경로, 그리고 중간 경로가 있다고 하자. 중간 경로는 왼쪽 경로와 오른쪽 경로 모두 들어갈 수 있는 화석들만 이어준다. 만약 중간 경로, 왼쪽 경로, 오른쪽 경로 모두에 화석이 이어질 수 없다면 두 개의 경로로는 모든 화석을 포함할 수 없는 경우이다. 중간 경로에 화석이 있음에도 불구하고 중간 경로에 화석을 잇질 못하면 화석이 들어가는 반대쪽 경로에 중간 경로에 있는 화석들을 이어주고 중간 경로를 비운다. 이렇게 했을 경우 반례가 전혀 없음을 알 수 있다. "중간 경로" 없이 로직을 작성할 경우 두 경로 모두에 포함 되는 화석을 어느 경로에 이어주느냐에 따라 반례가 발생할 수 있지만, "중간 경로"라는 것을 만들어 줌으로써 이러한 반례들을 해결할 수 있다.



H. Qanat


너비 $w$, 높이 $h$인 직각삼각형 모양의 카나트(물을 얻기 위한 지하 수로)가 있다. 구멍이 없는 초기 상태에는 왼쪽 꼭지점과 위 꼭지점에서 물을 끌어 올리며, 추가적으로 수직 구멍을 $n$개 뚫으면, 구멍을 뚫은 삼각형 빗변에서 추가적으로 물을 끌어 올릴 수 있다. 물을 끌어올리는데 비용이 있는데, $n$개의 수직 구멍을 적절히 뚫어 물을 끌어 올리는 비용을 최소화하는 문제다.

구멍을 뚫은 좌표들을 $x_1, x_2, \dots, x_n (x_1 < x_2 < \dots < x_n)$라고 했을 때, 비용에 대한 수식을 구하면 아래와 같이 정리된다.


$f(x) = a_1(x_1 - k_1x_2)^2 + a_2(x_2 - k_2x_3)^2 + \dots + a_n(x_n - k_nw)^2 + C$


$a_1 = \frac{1}{2}$이며, $k_i = \frac{1}{4}\times\frac{1-r^2}{a_i}$, $a_{i+1} = \frac{1}{2} - a_ik_i^2$이다. (여기서 $r = \frac{h}{w} \lt 1$)

이와 같은 식이 나오는 까닭은 직접 식을 구해 전개해보길 바란다. 이 때, 항상 $a_i \gt \frac{1}{4}, 0 \lt k_i \lt 1$을 만족한다. 이는 주어진 수식을 보고 증명 가능하다.


모든 $i$에 대해, $0 \lt k_i \lt 1$을 만족하므로 $f(x)$의 최소값은 $C$라는 것을 알 수 있고, 그 때 $x_1, x_2, \dots, x_n$ 값들도 계산할 수 있다.



M. Window Manager


$W \times H$ 크기의 픽셀이 있다. 이 곳에 윈도우를 열고, 크기를 바꾸고, 움직이고, 끌 수 있는 명령이 주어진다. 특이한 경우는 윈도우를 움직이는 경우인데, 윈도우를 움직일 때 움직이는 윈도우 이외에 다른 윈도우들도 밀려 움직일 수 있다는 것이다. 네 가지 명령을 문제 조건에 따라 구현하면 되는 문제이며, 윈도우 움직이는 명령을 구현하는게 까다로울 수 있다. 이와 관련된 방법은 소스 코드를 참고하길 바라며, 움직이는 명령을 $O(n^3)$에 구현해도 문제를 통과한다. 아래 소스 코드는 움직이는 명령을 $O(n^2)$에 구현했다.

상,하,좌,우 네 가지 방향으로 모두 움직일 수 있는데, 좌우대칭, 혹은 y=x 선대칭 등을 통해 오른쪽으로 움직이는 것에 대해서만 구현하면 상,하,좌,우 네 방향에 대해서 모두 해결할 수 있다.



K. Tours


양방향 간선 $m$개와 정점 $n$개로 이루어진 그래프가 주어진다. 버스 회사가 $k$개 있다고하고, 각 간선들을 하나의 버스 회사에 배정한다. 이 때, 그래프에 있는 모든 싸이클 별로 싸이클에 있는 간선들이 각 버스 회사에 공평하게 배정되어야 한다. 이 조건을 만족하는 가능한 버스 회사 개수 $k$를 모두 구하는 문제다.

만약 가능한 버스 회사의 최대 개수가 $c$라고 하자. 그러면 필요충분조건으로 $c$의 약수는 버스 회사 개수로 가능하다.

편의상 cycle set component라는 것을 정의하자. 서로 다른 두 간선이 속한 싸이클 집합이 같은 경우 같은 cycle set component에 들어있다고 본다. 당연한 얘기지만 간선은 최대 한 개의 cycle set component에 포함된다. 이 때, 답은 cycle set component들에 있는 간선 개수의 최대 공약수다. 이유는 cycle set component에 있는 간선들에게 균등하게 버스 회사를 배분하는 것과 모든 싸이클에 대해 싸이클에 있는 간선들에게 균등하게 버스 회사를 배분하는 것은 필요충분조건이기 때문이다.

싸이클에 속하지 않은 간선, 즉, 절단선들은 어떤 cycle set component에 속하지 않는다고 보자.

어떤 간선 $e$와 같은 cycle set component에 포함된 간선들을 모두 구하기 위해 그래프에서 간선 $e$를 없애고 새로 생기는 절단선들을 구하면 된다.

절단선을 구하기 위한 방법으로는 이중-연결-요소를 구하는 dfs 방법이 있으며, 시간복잡도는 $O(E)$이다.

그러므로 문제를 해결하기 위한 총 시간복잡도는 $O(m^2)$이다.



'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 2011  (0) 2015.05.18
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함