티스토리 뷰

IOI/IOI2016

IOI2016 Day 2 문제 및 해법

전명우 2016. 8. 16. 21:22

0. 문제 패키지


day2.zip


1. paint


길이가 $n$인 문자열이 있고 각 문자는 'X'혹은 '_'이다. 연속한 'X'끼리 묶어 블록이라 부르고, 총 $k$개의 블록이 있다. 문자열의 전체가 주어지지 않고 일부만 주어진다. 그리고 블록의 개수 $k$와 왼쪽부터 순서대로 블록들의 크기가 길이 $k$인 정수배열로 주어진다. 이 때 가능한 문자열이 여러 개가 있을 수 있는데, 가능한 모든 문자열에 대해서 항상 'X'가 놓이는 위치, 그리고 항상 '_'가 놓이는 위치를 구하는 문제다.


모든 위치에 대해서 '_'를 놓을 수 있는지, 'X'를 놓을 수 있는지를 나눠서 계산하면 된다. 아래와 같은 세 개의 DP 배열을 계산해놓으면 편하다.

D[i][j] = 1번 블록부터 i번 블록을 1번째 문자부터 j번째 문자까지의 부분 문자열에 놓을 수 있는지 여부

E[i][j] = i번 블록부터 k번 블록을 j번째 문자부터 n번째 문자까지의 부분 문자열에 놓을 수 있는지 여부

F[i][j] = i번 블록의 오른쪽 끝을 j번째 문자로 놓을 수 있는지 여부


어떤 위치 $i$에 대해서 '_'를 놓을 수 있다는 것은 $0 \leq j \leq k$인 $j$에 대해 D[j][i-1]과 E[j+1][i+1]이 동시에 1이 되는 $j$가 하나라도 있다는 것이다.


어떤 위치 $i$에 대해서 'X'를 놓을 수 있다는 것은 $1 \leq j \leq k$인 $j$, $i \leq p \le i+A_j$인 $p$에 대해 F[j][p]가 1이 되는 $j$, $p$가 하나라도 있다는 것이다. 여기서, $A_j$는 $j$번 블록의 크기를 의미한다.


어떤 위치 $i$에서 'X'와 '_' 모두 못 놓는 경우는 문제 조건에 따라 주어지지 않는다. 만약 'X'만 놓을 수 있으면 해당 칸에 대한 답은 'X'가 되고, '_'만 놓을 수 있으면 답은 '_', 둘 다 놓을 수 있으면 '?'가 된다. 위 알고리즘의 시간복잡도는 $O(nk)$이다.



2. messy


길이가 $n$인 0과 1로만 이루어진 문자열들이 있다. 최대 $w$개의 문자열을 집합에 넣을 수 있다. 문자열들을 집합에 넣고 나서 집합에 있는 문자열들은 변형이 되는데, 하나의 특정 순열에 의해 문자들의 순서가 섞인다. 섞은 이후에 최대 $r$개의 문자열이 집합에 있는지 확인할 수 있다. 이를 통해 문자열들을 섞은 순열을 구하는 문제다.


이 문제는 마지막 서브태스크의 제한이 $n=128$, $w=896$, $r=896$으로 노골적으로 $w = r = n \lg n$이다. 덕분에 분할정복을 어렵지 않게 유추할 수 있다. $s$부터 $e$까지의 구간, $[s, e]$의 순열을 구하는 분할 정복을 생각해보자. 구간 $[s, e]$의 순열에 들어갈 수 있는 $e-s+1$ 크기의 위치 후보들이 있다. 초기에 $s=0$, $e=n-1$이고. 위치 후보는 $[0, 1, \dots, n-2, n-1]$이다.


$m$을 구간 $[s, e]$의 중간 지점이라 하자. 분할 과정에서 $e-s+1$개의 위치 후보 중 구간 $[s, m]$에 들어가는 위치 후보 $m-s+1$개를 추려내야한다. 나머지 위치 후보는 구간 $[m+1, e]$의 위치 후보가 된다. 이는 $m-s+1$개의 고정된 문자열을 집합에 넣고, $e-s+1$개의 문자열이 집합에 있는지 확인하는 작업을 통해 이루어진다.


$[s, m]$에 들어가는 위치 후보들을 추리기 위해서 구간 $[s, e]$의 이진값은 $0$, 나머지는 $1$인 기본 이진문자열을 생각해보자. 이 기본문자열에서 구간 $[s, m]$에 속한 한 $i$에 대해 $i$의 이진값은 $1$인 문자열이 $m-s+1$개있다. 이 문자열들을 집합에 넣으면 적절한 질문을 통해 구간 $[s, m]$에 들어가는 위치 후보들을 추릴 수 있다.


예를 들어 $n=4$일 때 다음 문자열들을 집합에 넣는다: $1000$, $0100$, $1011$, $1110$

최종적으로 $w = \frac{n \lg n}{2}$, $r = n \lg n$ 이다.



3. aliens


$m \times m$ 크기의 격자판의 격자칸 안에 $n$개의 점들이 분포되어있다. 두 대각 꼭지점이 전체 대각선 위에 있도록 정사각형 영역으로 사진을 찍을 수 있다. 이 때 최대 $k$개의 사진을 찍어 모든 점들을 담고, 사진 찍은 영역 합집합의 크기를 최소화하는 문제다.


우선 깔끔한 문제 풀이를 위해 입력 데이터를 다듬을 필요가 있다. Example 2에도 소개되어 있듯이 $r_i$와 $c_i$는 두 값이 서로 뒤바뀌어도 상관없다. 따라서 $r_i < c_i$가 되도록 바꿔준다. 그리고 $i < j$인 모든 $i$, $j$ 쌍에 대해 $r_i < r_j$, $c_i < c_j$가 되도록 존재가 무의미한 점들을 제거할 수 있다. 이제 아래와 같은 DP를 생각할 수 있다.

D[i][j] = 1번 점부터 $i$번 점까지 사진 영역에 포함되고, 마지막 사진 영역의 오른쪽 아래 꼭지점이 $(c_i, c_i)$이고, 지금까지 사진 찍은 회수가 $j$일 때, 사진 찍은 영역 합집합 크기의 최소값

D[i][j] = min(D[k][j-1] + (c[i]-r[k+1]+1)^2 - max(0, c[k]-r[k+1]+1)^2)

이를 있는 그대로 구현하면 시간복잡도는 $O(n^2k)$이다. 이 경우 25점을 받는다.



여기서 위 점화식 꼴은 Convex Hull Optimization을 통해 $O(nk)$ 시간복잡도로 줄일 수 있다. 이 경우 60점을 받는다.



우선 찍는 사진의 수가 정확히 $k$개일 때 사진 찍은 영역 합집합의 최소 크기(비용)를 한번에 계산하는 방법이 $O(nk)$보다 빠른 것은 거의 불가능하다. 그래서 조금 우회해야하고 이 문제는 이전에는 보기 힘들었고 매우 신기한 기법을 통해 풀린다. 문제를 다시 정리하면, 사진을 적게 찍으면 비용은 커지고, 찍는 사진의 수가 많아질수록 비용은 줄어든다. 그리고 문제는 찍는 사진의 수가 정확히 $k$일 때 최소 비용을 찾는 것이다.


한 가지 특별한 관찰이 있어야한다. 찍는 사진의 수가 많아질수록 비용이 줄어드는 것은 자명하지만, 줄어드는 감소폭 또한 감소한다. 즉, $x$축이 찍는 사진의 수고 $y$축이 비용일 때 아래 그래프처럼 아래로 볼록한 그래프가 나온다.



이제 사진을 한 번 찍을 때 비용 $c$를 새로 정의하자 (원래 문제에서 $c=0$). 그러면 새로운 전체 비용은 "사진 찍는 영역 합집합의 크기 - (찍는 사진 개수) * $c$"가 되며, 새로 생기는 그래프는 위 그래프에 $y = cx$를 더한 꼴이 된다. 이 때 새로운 전체 비용의 최소값을 구하는 것은 마찬가지로 Convex hull optimization을 통해 $O(n)$에 가능하다. $c$ 값에 따라 새로운 그래프의 최소점의 $x$좌표가 달라진다. $c$ 값이 커질수록 최소점은 왼쪽으로 이동할 것이고, $c$ 값이 작아질수록 최소점은 오른쪽으로 이동할 것이다. 이제 최소점의 $x$ 좌표가 $k$가 되는 $c$ 값을 이분탐색으로 찾으면 찍는 사진의 개수가 $k$일 때 사진 찍은 영역 합집합의 최소 크기를 구할 수 있다.


정한 $c$ 값에 따라 최소점이 여러 개가 존재하는 경우가 있다. 최소점이 여러 개인 경우 어떤 $x$ 좌표를 최소점으로 구할지 예상할 수 없다. 따라서 최소점이 $k$보다 작으면서 제일 오른쪽인 점 $l$과 그 때의 $y$ 좌표, 최소점이 $k$보다 크면서 제일 왼쪽인 점 $r$과 그 때의 $y$ 좌표를 구해놓는다. 이제 총 2가지 경우가 있는데 $l$과 $r$ 사이에는 기울기가 일정하거나, 아니면 $r-l = 2$이고 사이에 감소폭이 1 감소한 경우다. 첫 번째 경우 아래 그림에서 $x=l$일 때 $y$ 값을 알고, $x=r$일 때 $y$ 값을 알고 있으면, $k$일 때 값을 쉽게 계산할 수 있다.



두 번째 경우는 아래 그림과 같이 $n = 3$, $k = 2$이고 각각의 $y$ 좌표가 $10, 5, 1$이 되는 경우다. 이 경우 감소폭이 $5, 4$로 1만 감소하고 경우에 따라 최소점의 $x$ 좌표가 $2$가 되는 $c$가 존재하지 않을 수 있다.

두 경우 모두 하나의 식으로 $y(k)$를 구할 수 있다. $y(k) = y(r) + \lfloor\frac{y(l) - y(r)}{r - l}\rfloor \times (r - k)$

전체 시간복잡도는 $O(n \lg m)$ 이다.



'IOI > IOI2016' 카테고리의 다른 글

IOI2016 Day 1 문제 및 해법  (1) 2016.08.15
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
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
글 보관함