USACO Platinum - 3

한 문제 한 문제가 고역이다

11990. Load Balancing (Platinum)

이 문제는 비교적 뻔한 문제여서 풀이는 금방 생각했다. 우선 모든 점을 x좌표를 기준으로 정렬해보자. 임의의 i번째 점과 i + 1번째 점 사이에 선을 그으면, 1 ~ i번째 점과 i +1 ~ n번째 점은 서로 다른 평면으로 분할이 된다. 이제 여기서 좌우로 선을 어떻게 긋는 경우가 최적인지를 찾아야 하는데, 이 때는 x좌표는 고려할 필요가 없다(x좌표는 이미 평면 분할된 걸 고려했으니). 그래서 y 좌표만 있는 일차원 배열 두 개에서 최적인 경우를 찾는게 되는데, 이 최적 그래프는 unimodal한 형태를 띈다(양쪽 평면 각각을 나눠서 생각했을 때 unimodal한 건 쉽게 생각할 수 있는데, 이 둘에서 다시 최대를 뽑는 것도 unimodal이므로 그래프가 unimodal해짐).

 

 따라서 삼분탐색을 통해 답이 되는 좌우 선분의 위치를 찾을 수 있다. 각 평면에서 점의 개수를 찾는 건 세그먼트 트리 등의 자료구조로 할 수 있다. 따라서 시간 복잡도는 O(Nlog^2N) 정도가 된다. 나는 여기서 좌표압축 하기 귀찮아서 그냥 돌렸는데 시간초과가 났고, 그래서 세그먼트 트리 -> 펜윅으로 바꾸고 쿼리 수 좀 줄여서 통과했다. 이 때 처음 짰던 풀이가 모든 점이 한 직선 위에 있는 경우 답을 못 찾는 예외가 있었어서 몇 번 틀리고 맞았다.

16760. Balance Beam

 도저히 모르겠어서 힌트를 좀 보고 풀었다. 어떻게 이게 Convex Hull로 풀린다는 발상을 할 수 있는지 모르겠다. 역시 기하는 어렵다... 이럴 때마다 내 수학적인 능력이나 센스가 참 많이 부족하다는 걸 느낀다.

 

 이 문제는 각각의 시작지점에서 얻을 수 있는 값을 f(x)라고 했을 때, f(x) = max(f(x), (f(x-1) + f(x+1)) / 2) 를 모든 지점 x에 대해 무한히 반복했을 때 f(x) 값을 출력하는 것으로 생각할 수 있다. 이렇게 생각했을 때 (x, f(x))를 좌표 평면 위에 찍어서 이 과정을 시뮬레이션 해보면, 각 지점이 (x, f(x))로 만들 수 있는 볼록 껍질의 윗 부분 직선으로 수렴하게 된다는 것을 알 수 있다. 그래서 convex hull을 구하고 convex hull 상에서 각 x좌표에서의 y값을 구해서 출력하면 O(nlogn)에 문제를 해결할 수 있다. 이 때 64비트 정수 범위를 초과하는 연산이 발생해서 이걸 잘 처리해주어야 한다. f(x) 범위가 10^5 정도여서 이런 짜증나는 처리를 안 해도 됐으면 더 좋은 문제였을 것 같다.

18313. Cave Paintings

 재밌는 문제였는데 식을 잘못 세워놓고 이걸 한참동안 못 깨달아서 고생하다 겨우겨우 풀었다.

 

 높이 h의 어떤 점에 물을 부었다고 생각해보자. 그러면, 높이가 같거나 작은 모든 연결된 위치에 대해 물이 흘러가게 된다. 하지만 높이가 h보다 큰 지점으로 물이 흐를 수는 없으므로, 높이가 h인 지점을 기준으로 그 아래쪽만 고려해도 충분하다. 이 때 높이가 h일 때 물을 흘려서 도달 가능한 모든 위치를 하나의 컴포넌트로 묶는다고 생각해보자.

 

 이러면 각각의 컴포넌트를 선택하는 경우 / 안 하는 경우 서로 다른 그림이 그려진다는 것을 알 수 있다. 이걸 기반으로 개수를 세면 되는데, 어떻게 잘 계산해서 높이가 h인 경우를 처리했다고 하자. 그 다음 높이가 h+1인 경우로 넘어가면, 높이가 h인 경우에서 만들어졌던 컴포넌트 중 일부가 h+1인 지점에서 서로 합쳐지는 경우가 생긴다. 즉, 높이 h+1인 어딘가에 점을 찍으면 높이 h인 지점에서는 점을 찍을 수 없는(h+1에 찍었을 때 경우에 포함이 되는) 경우가 생긴다는 뜻이다. 이 경우의 수를 잘 계산해서 제외해줘야 하는데, 다음과 같은 방법으로 제거할 수 있다.

 

 - 각 컴포넌트 내에서 서로 다른 그림을 그릴 수 있는(모양이 다르게 만들 수 있는) 경우의 수를 cnt[c] 라고 하자. 이 때 해당 컴포넌트의 가장 위에 물을 붓는 경우는 컴포넌트에 속한 모든 위치에 물이 흐르기 때문에 경우의 수가 1이 된다. 제일 위에 붓지 않는 경우, 바로 아래(높이 h-1)에서 존재했다가 c에 합쳐진 컴포넌트 n_1, n_2, n_3, ... n_k에 대해, cnt[n_1] ... cnt[n_k]를 모두 곱한 만큼의 경우의 수가 생긴다(서로 독립적으로 그림이 생길 수 있으므로). 따라서 이 전체 곱 + 1을 하면 cnt[c]도 구해줄 수 있다. 이 때 이 경우의 수는 합쳐졌기 때문에 이보다 아래 레벨에서 셌던 경우의 수에서 제외해주어야 한다.

 

 이렇게 제외하면서 현재 높이 h에서 생성되는 모든 컴포넌트의 경우의 수를 구하고 나면, (이번 레이어에서 하나이상의 컴포넌트를 고르는 경우) * (이와 독립적으로 아래쪽에서 뽑을 수 있는 경우의 수) 를 답에 더해주면 된다. 이를 h = 1 .. n - 1 까지 반복해주면 답을 구할 수 있다. 나는 여기서 (이와 독립적으로 아래쪽에서 뽑을 수 있는 경우의 수) 이 부분 경우의 수 구하는 걸 잘못 생각했는게 그게 무조건 맞을 거라고 찰떡같이 믿고 의심도 안했다가 한참을 고생했다. 왜 그게 맞다고 생각했는지 참...