SCPC 2018 2차(Round 2) 간략한 풀이

문제는 나중에 codeground.org에서 확인할 수 있을거에요.

1. Quick Sort

지금 수가 0~N-1 범위였는지, 그렇지 않았는지가 기억이 잘 안나는데, 만약 그렇지 않다고 해도 각 수를 크기순으로 정렬해서 re-ordering을 하면 되니까 그냥 수가 0~N-1 범위라고 가정을 합시다. 수를 A[0], A[1], A[2], A[3], ... 이라고 하면 각 A[i]에 대해 max(A[0], A[1], ... , A[i-1]) = i-1, A[i] = i를 만족한다면 A[i]는 조건을 만족합니다. max를 왼쪽에서부터 누적시키면서 계산하면 total O(N)에 해결할 수 있습니다.

2. 메모지

<관찰>

-조금만 생각해보면 x좌표는 아무런 의미가 없음을 알 수 있습니다. 

- 메모지를 y좌표가 낮은 것부터 처리를 한다고 하면, 꺾은 선 갯수가 동일하다면 메모지를 최대한 y좌표가 낮게 부착하는 것이 이득입니다. 낮게 부착하면 할수록 다음번에 메모지가 부착될 수 있는 범위가 늘어나니까요.

메모지의 y좌표, 길이만 저장하고, y좌표 순으로 정렬을 합니다. 이제 메모지를 하나씩 보면서 D table을 갱신해나갈 건데, D[i]는 직선을 i개 썼을 때 마지막으로 붙인 메모지의 y좌표 중에서 최솟값입니다.

초기값은 D{0] = -INF, D[1~] = INF입니다.

이후 k(=0 to N-1)번째 메모지에 대한 DP를 갱신합니다.

j = N-1 to 0에 대해 k번째 메모지의 y좌표가 D[j] 이하인 경우 D[j+1] = min(D[j+1], max(D[j]+k번째 메모지의 높이, k번째 메모지의 y좌표)) 으로 갱신이 되고 D{j] = D[j] + k번째 메모지의 높이 로 갱신이 됩니다. 이후 D[i] != INF인 최대의 i를 구해 N-i를 하면 그것이 정답입니다.

O(N^2)이 통과될지 안될지 의아해하며 제출했는데 생각보다 너무 빨리 돌아서 신기했습니다. 참고로 2017 대전 인터넷 예선 G번 문제와 아예 동일하다고 하네요.

3. Binotic Paths

일단 Bitonic Path 말고 Increasing Path를 생각합시다. 각 점 k에 대해 dist1[k]를 1 to k의 Increasing Path의 최솟값, distN[k]를 N to k의 Increasing Path의 최솟값이라고 하면 min(dist1[k] + distN[k])를 계산하면 됩니다.

이제 dist1, distN을 어떻게 구할지가 문제인데, 먼저 edge의 weight가 distinct한 경우를 생각해봅시다. 그렇다면 일단 dist1[1] = 0, dist1[2~N] = INF, distN[N] = 0, distN[1~N-1] = INF로 둔 뒤 edge의 weight 순으로 보면서 수많은 그래프 알고리즘에서 하는 것과 유사하게 dist를 갱신해나갑니다. (a와 b가 연결되어있을 경우 dist1[a] > dist1[b]+weight(a,b) 이면 dist1[a]를 갱신, a-b를 바꿔서도 마찬가지로 진행) 그러면 Increasing Path임이 보장됩니다.

문제는 이러한 방식을 채용하면 edge의 weight가 distinct 하지 않을 때 어느 edge를 먼저 보냐에 따라 dist table의 값이 달라질 수도 있는데, 이를 방지하기 위해 edge를 weight로 정렬한 뒤 weight가 동일한 그룹을 묶어 그 그룹 안에서는 아래와 같은 방식으로 진행합니다.

- 그 그룹 내에서 등장하는 vertex들을 전부 기억합니다.(예를 들어 edge(2,3), edge(2,5), edge(3,7), edge(4,6)일 경우 2,3,4,5,6,7을 기억)

- 그 그룹 내의 edge들을 adjacency list 형태로 만듭니다.

- vertex들에 대해 Dijkstra와 유사하게 priority queue에 dist1[v], v를 넣습니다.

- 하나씩 꺼내면서 Dijkstra와 똑같이 adjacency list 상의 이웃한 vertex를 보면서 dist를 갱신해줍니다.

이러면 Edge가 최대 M개이므로 대략 O(MlgM) 정도에 해결이 가능합니다.

4. 지진

(97, 72, 35, 17, 43)과 (1, 6, 3, 2, 4)에서 최소 몇 개를 제외하면 동일한 패턴을 만들 수 있는지를 알아봅시다. (97, 72, 35, 17, 43) - (1, 6, 3, 2, 4)를 (97, 17, 35, 43, 72) - (1, 2, 3, 4, 6)으로 만들어도 아무런 문제가 없다는 것은 자명합니다. 그렇다면 이제 97, 17, 35, 43, 72에서의 LIS 길이를 찾기만 하면 됩니다. 즉, N개의 data를 M개의 길이로 잘라낸 후, LIS의 길이가 M-K 이상이면 지진 카운트를 1 증가하면 됩니다. 시간복잡도는 O(NMlgM)입니다.

5. 히스토그램

(x-a1)^2 + (x-a2)^2 + (x-a3)^2 +.. + (x-an)^2의 최솟값은 x = (a1+a2+...+an)/n일 때입니다. 이는 미분을 이용하면 쉽게 보일 수 있습니다. 이제 스택에 (값, 갯수)를 넣습니다. 무슨 의미냐면, 예를 들어 3 4 1 6 5 3 5 5라고 치면 일단 스택에 (3,1)을 넣습니다. 이제 4를 보는데 스택의 top인 3보다 4가 크므로 4를 넣는 것이 문제가 되지 않습니다. 스택에 (4,1)을 넣습니다. 그 다음 1을 보는데 스택의 top인 4보다 1이 작으므로 Non-decreasing이라는 조건에 위배되니 (4,1)을 pop한 후 (1,1)과 묶어 (2.5, 2)를 만듭니다. 다시 스택의 top을 보면 스택의 top인 3보다 2.5가 작으므로 (3,1)을 pop한 후 (8/3, 3)을 만듭니다. 스택에 (8/3, 3)을 넣습니다. 이런식으로 Non-decreasing 조건을 계속 만족하게끔 값들을 바꿔나갑니다. 각 원소는 최대 1번 stack에 pop 됨이 보장되므로 O(N)에 해결가능합니다.

대충 4시쯤 다 풀고나서 스샷 찍고 딴 일좀 하다가 왔는데 끝나고 보니 다섯 문제 다 생각보다 훨씬 많이 풀려있었습니다. 검색을 통해 비슷한 문제를 찾을 수 있어서 그랬나 싶기도 하고 사람들 실력이 1년 사이에 많이 오른건가 싶기도 하네요. BItonic Paths에서 const int INF = 0x3f7f7f7f7f7f7f; 으로 두는 실수를 한 것을 제외하면 아무런 실수없이 깔끔하게 잘 풀어서 굉장히 만족스럽습니다.