Bubble Cup 11 - Finals (Online Mirror)

대회 링크 : http://codeforces.com/contest/1045

버블컵 미러에 koosaga님, breakun님과 팀으로 참가했다. 실력이 나랑 비슷하거나 그 이하인 사람과는 팀을 해 본 적이 있지만 나보다 압도적으로 잘하는 사람들이랑 팀을 해본 건 처음이었는데, 정말 너무 유익하고 재밌는 대회였다. 역시 팀으로 참가하는 대회가 개인전보다 훨씬 재밌다는 생각이 들었다.

대회는 무려 9문제를 풀어서 3등을 했고, 그 중에 내가 3솔브, koosaga님이 5솔브, breakun님이 1솔브를 하셨다. breakun님이 개인 사정으로 대회에 처음부터 참가하지 못하시고 중간부터 참가하게 됐는데 이게 너무 아쉽다. 처음부터 참가하셨으면 올솔브 가능했을 것 같은데 ㅠ

오늘 셋에서 내 실력에 풀 수 있을만한 문제는 사실 두 문제 정도 뿐이었는데. koosaga님이 친절하게 풀이를 알려주셔서 혼자서는 못 풀었을 문제인 A, D번을 직접 구현까지 해보게 됐다. 풀이 이야기하는 과정에서 잘하는 사람들이 어떤 식으로 접근하고 얼마나 빨리 풀이를 떠올리는 지를 느낄 수 있었고, 그 자체로 정말 많은 도움이 됐다.

아래는 내가 푼 문제들에 대한 요약(난이도 순)

I. Palindrome Pairs

N개의 문자열이 주어진다. 이 중 두 개를 골라서 두 문자열을 이어붙여서 마음대로 섞었을 때 팰린드롬을 만들 수 있으면 palindrome pair라고 한다. 주어진 문자열들에서 만들 수 있는 palindrome pair의 개수를 세는 문제였다.

 흔한 유형의 문제고 많이 풀어본 유형의 문제라 그냥 쉽게 풀었다. 최대 26개의 알파벳으로만 구성되기 때문에 i 번째 알파벳이 짝수개면 i번째 비트를 0, 홀수개면 i번째 비트를 1로 놓고 해당 문자열을 숫자로 변환할 수 있다. 이렇게 숫자로 변환하고 나면 나랑 합쳤을 때 팰린드롬이 되는 숫자가 무엇인지 쉽게 계산 가능하고 이걸 이용해서 개수를 세주면 된다. map 등의 자료구조를 이용하면 구현이 편하다.

D. Interstellar Battle

 N개의 정점으로 이루어진 트리가 있다. 트리에서 각 정점에 대해 각 정점이 제거될 확률 pi가 주어진다. 그리고 q개의 쿼리가 주어지는데, 매 쿼리마다 트리의 정점들 중 하나의 제거될 확률이 변경된다. 쿼리가 주어질 때, 정점이 제거될 확률을 주어진 확률로 변경한 다음, 모든 정점에 대해 해당 확률로 정점이 제거된다고 했을 때 정점들이 제거된 후 남아 있는 컴포넌트 개수(서로 연결된 정점 집합 개수)의 기댓값을 구하는게 문제이다.

 N도 Q도 10만 범위기 때문에 빠르게 계산하는 방법을 떠올려야하는데, 이게 너무 어려웠다. 일단 쿼리를 빼고 생각했을 때 트리 DP로 접근하면 O(N)으로 전체 기댓값을 구할 수 있을 거라고 생각했는데, koosaga님이 Q개의 쿼리가 주어지기 때문에 그 방법은 최적화하기 충분히 간단한 방법이 아니다. 더 간단한 방법을 생각해보라. 고 하셨다. 그리고 추가적으로 힌트를 주셨는데, N개의 노드중 어떤 노드가 제거되었고 어떤 노드가 남아있는지를 알고 있을 때, 탐색 없이 남아있는 컴포넌트의 개수를 셀 수 있는 방법을 생각해보라고 하셨다.

 그리고 좀 더 고민해본 후 만약 K개의 노드가 살아 있을 때, 그 K개가 모두 서로 연결되어 있지 않다면 총 K개의 컴포넌트가 있을 것이므로 K개가 컴포넌트의 최대 개수가 될 것이라고 생각했다. 여기에 이어서, 어떤 경우에 컴포넌트의 개수가 줄어들까를 생각해보았고, 주어진 노드들이 서로 연결되어 있으면(인접해있으면) 컴포넌트의 개수가 줄어드는 것이라는 생각이 떠올랐다. 두 노드가 서로 인접해 있다는 것은 두 노드가 서로 부모자식 관계라는 의미이므로, K개의 노드가 살아 있을 때 컴포넌트의 개수는 K - (부모 자식 관계인 노드 쌍의 개수) 라는 결론에 도달했다.

 여기서 계속 고민을 했었는데, 어떻게 해야 이 공식을 기댓값 계산에 사용할 수 있는지 전혀 감이 오지 않았다. 어쨌든 노드들이 몇 개 살아있는지 각 경우를 따져봐야하고, 또 그 중에 누가 부모 자식 관계가 되는 지도 생각해봐야 하지 않을까? 모든 경우를 테스트해보려면 결국 DP를 써야 하는 것 아닌가? 에서 도저히 진전이 없었고, 그래서 그냥 koosaga님에게 헬프를 요청했다. 그래서 들은 결론의 핵심은 기댓값의 선형성을 이용하면 된다 였고, 나는 이 쪽으론 전혀 생각도 못 했기 때문에 그냥 감탄만 했다. 

 생존한 노드가 K개 있고 그 중에 부모 자식 관계인 노드 쌍의 개수를 X라고 하면 결국 우리가 구하고 싶은 기댓값은 E(K-X)인데 이는 앞서말한 선형성에 의해 E(K) - E(X)와 동일하다. 두 식 모두 굉장히 계산하기 쉬운데, E(K)의 경우 생존하는 노드 개수의 기댓값이므로 단순히 각 노드별 생존 확률의 합이 된다. E(X)도 간단한데, 부모자식 관계인 노드 쌍의 개수이므로 서로 부모 자식인 두 노드의 생존확률이 각각 Pi, Pj라고 하면 모든 쌍에 대해 Pi*Pj를 계산해서 더한 것이 곧 E(X)가 된다.

이러한 계산은 N개 노드를 모두 순회하면서 쉽게 계산할 수 있다. 이제 Q개의 쿼리가 문제인데, 이 쿼리의 경우 위 식에선 굉장히 쉽게 계산할 수 있다. 어떤 노드 A의 생존확률이 변경되었다면, 이 변경된 값이 E(K)와 E(X)에 각각 영향을 끼친 부분만 고쳐주면 된다. E(K)의 경우 기존 확률을 빼고 새 확률을 더해주면 되고, E(X)의 경우 이 노드의 부모 / 자식 부분에만 영향을 끼친다. 이 때 각 노드별로 자신의 자식 노드 전부의 생존 확률 합을 미리 전처리 해두면, A 노드의 부모에 대해 자식 노드 합을 갱신해주고 갱신한 값으로 다시 확률 계산해주고, A의 자식 노드에 대해 (기존 확률과 새 확률의 차이) * (A의 자식 노드 확률 합)을 더해주면 변경된 확률을 구할 수 있다. 이러한 과정은 모두 O(1)에 수행되기 때문에 전체 시간 복잡도 O(N+Q)에 답을 구할 수 있다.

A. Last Chance

N개의 무기와 M개의 외계 함선이 있다(N, M <= 5000). 각 무기는 아래의 세 종류 중 하나이다.

로켓: 로켓마다 정해진 K개의 후보 함선 중 하나를 골라 부술 수 있다. 모든 로켓들의 후보 함선 개수 합은 10만을 넘지 않는다.

빔:  연속된 l,r 구간의 함선 중에 하나를 골라 부술 수 있다.

바주카: 세 개의 후보가 주어진다. 사용할 때는 그 중에 반드시 두 개를 골라서 부숴야 한다. 모든 바주카들 끼리는 서로 후보 집합이 disjoint하다.

이 때, 부술 수 있는 최대 외계함선의 개수 및 어떤 무기로 어떤 함선을 부수면 되는지 목록을 구하는 것이 문제이다.

문제를 보고 나면 당연히 바로 딱 드는 생각은 로켓과 빔은 동일한 것이다 와 그러면 당연히 네트워크 플로우로 풀리겠네 라는 것이다.

나는 여기서 생각이 멈춰버렸는데, 네트워크 플로우 문제에 많이 안 익숙하기도 하고 바주카의 반드시 두 개를 골라서 부숴야한다를 어떤 식으로 모델링해야 할지 전혀 감이 안잡혔기 때문이었다. 여기서 혼자 그래프를 어떻게 짜야 하나 한참 고민하고 있었는데, J 잡고 계시던 koosaga님이 오셔서 풀이 방향성을 봐주셨다.

그리고 순식간에 풀이 방향이 나왔는데, 그래프 모델링을 잘 해서 그냥 네트워크 플로우로 바주카를 처리할 수 있다는 것을 우선 설명해주셨다. 그리고 남은 한 가지 문제는 빔을 그냥 로켓처럼 처리해버리면 간선 개수가 너무 많아져서 TLE가 날 수 밖에 없다는 것이었는데, 이건 해결할 수 있는 테크닉이 있다고 말씀해주셨다. 1. 모델링, 2. 빔 간선 개수 줄이기 둘 다 정리해보자.

1. 그래프 모델링

그림판으로 만든 조악한 모델링 설명을 첨부해서 이야기 하자면, 위와 같은 그래프에서 S 정점으로부터 T정점으로 유량을 흘릴 것이다. 화살표 그리기 힘들어서 화살표는 생략했는데 당연히 전부 왼쪽에서 오른쪽 가는 방향만 존재하는 간선이다. 또, 모든 간선의 capacity는 1이다.

이렇게 그래프를 구성하면, 바주카를 제외한 나머지 부분은 명확하다. 빔, 로켓으로 되어 있는 무기 정점에서 외계 함선을 지나서 T정점으로 흘러가는 유량 각각이 무기들과 함선들을 매칭해주는게 된다. 여기서 바주카의 위치가 독특하다. 바주카는 외계함선보다 뒤쪽에서, 자신이 후보로 하는 외계 함선 셋과 연결되어 있으며 그 중 1의 유량만 T로 흘려 보낼 수 있다. 

이 모델링은 바주카는 항상 고르는게 이득이다라는 사실에 기초한다. 하나의 바주카로 항상 둘을 부술 수 있으므로, 바주카는 골라서 딱히 손해될 게 없다. 무기 하나로 두 개를 부술 수 있는 유일한 종류이고, 바주카를 고르는게 항상 이득이라는 증명을 하는 것은 별로 어렵지 않다.

이제 이 바주카에서 두 개의 후보를 뭘 선택할 지가 문제인데, 위의 그래프에서는 거꾸로 바주카에서 고르지 않을 후보를 선택하게 만드는 것이다. 바주카에서 고른 함선는 다른 무기로 부술 수 없고, 바주카에서 고르지 않을 함선만이 부술 수 있는 함선이다. 따라서, 저 그래프에서 외계 함선 -> 바주카 간선을 통해 흐른 유량을 제외한 나머지 두 후보는 바주카로 부수고, 저 유량으로 흐른 함선을 다른 무기로 부쉈다고 생각하면 성립하게 되는 것이다. 바주카들의 후보가 모두 disjoint하지 않다면 이렇게 모델링할 수 없겠지만 모두 중복이 없기 때문에 이렇게 모델링할 수 있게 된다.

이제 이 모델에서, 주어진 그래프에서 얻은 max flow값이 곧 바주카를 제외한 나머지 무기들로 부순 최대 함선 수이다. 여기에 바주카들은 항상 2개씩 부술 수 있고 무조건 선택할 것이기 때문에, max flow + 2 * 바주카 수가 부순 최대 함선 수가 된다.

2. 빔 간선 수 줄이기

이건 나는 처음 들어봤지만 상위권 사이에선 잘 알려진 테크닉인 것 같은데, 연속한 구간에 대한 간선 목록은 세그먼트 트리의 개념을 응용하는 것으로 개수를 줄일 수 있다. 즉, 그래프 상에 어떤 1~n까지의 구간을 나타내는 세그먼트 트리 노드를 하나 만든다. 이 노드는 내부적으로 다시, 중간 지점 m에 대해 1~m / m+1~n 의 구간을 나타내는 두 노드로 간선을 가지고 있다. 이런 식으로 구간을 쭉 분할하는 것을 반복해서, 마지막 리프 노드는 실제로 그 리프 노드에 해당하는 노드로의 간선을 갖게 만든다. 이 때 트리의 내부 간선끼리는 모두 capacity를 무한대로 보고, 리프 노드->실제 노드만 capacity가 1인 간선을 두면 된다.

이렇게 노드를 갖추고 나면 세그먼트 트리와 동일한 방식으로 엣지를 추가해줄 수 있다. 어떤 l~r구간 전체에 엣지를 추가하고 싶다면, 그 l~r 구간에 해당하는 세그먼트 트리 노드로 간선을 추가해주면 되고 이러한 간선의 개수는 세그먼트 트리 쿼리가 탐색하는 구간 개수와 상한이 같으므로 O(logn)개면 충분하다. 따라서, 이 세그먼트 트리 노드를 통해 빔 하나당 O(logn)개의 간선만 가지고 구간을 표현해줄 수 있게 된다.

이제 이 두가지를 이용해서 그래프 모델링도 끝냈고 간선 개수도 줄여서 충분히 시간 안에 답을 얻을 수 있게 됐다. 마지막으로, 이걸 어떻게 역추적해야 할 것인가만 해결하면 문제를 풀 수 있다.

3. 역추적

koosaga님에게 위의 두 풀이를 다 설명을 듣고, 바로 구현에 들어가려고 했는데 koosaga님께서 역추적이 까다롭고 이런 문제는 정리를 30분정도 하고 구현에 들어가는게 낫다 라고 말씀하셔서 먼저 정리에 들어갔다(그리고 koosaga님은 다시 J를 풀러 가셨다). 그래서 구현하지 않고 그래프부터 그리고 역추적을 어떻게 해야할 지 공책에 정리를 했다. 역추적은 아래의 세 가지 과정을 통해서 구현했다.

1. 로켓 정점 -> 외계 함선 간선에 flow가 있는 경우 : 이 경우가 가장 간단하다. (해당 로켓, 해당 함선)을 부순 경우이므로 이를 정답 리스트에 추가해준다.

2. 바주카 : 바주카의 경우, 외계 함선 노드에서 특정 바주카 노드로 유량이 흐른 경우가 있는지 확인한다. 그런 경우가 있으면, 해당 외계 함선은 그 바주카에서는 선택할 수 없는 경우이다. 따라서, 해당 바주카에서 그 함선을 선택하지 못하도록 체크해준다.

3. 빔 : 이 경우가 제일 복잡하다. 빔 정점은 바로 외계 함선을 골라서 들어가는게 아니라 세그먼트 트리 노드들을 거쳐서 들어가게 되는데 이 것 때문에 실제로 어떤 빔이 어떤 함선에 매칭이 되었는지를 알 수가 없다. 따라서, 별도의 방법을 통해 빔이 어떤 함선을 부숴야 성립하게 되는지를 복구해 줄 필요가 있다.

우선, 빔에 대해 빔 -> 세그먼트 트리 노드 로의 간선에 flow가 있으면 해당 빔을 사용했다는 뜻이므로 이런 빔들 목록을 구해준다. 그리고, 위의 1,2번 과정에서 어떤 함선이 파괴되어서 쓸 수 없고 어떤 함선은 쓸 수 있는지 목록을 체크해둔다. 이제, 구간이 주어지고 각 구간에 대해 사용할 수 있는 원소 목록이 주어져 있을 때 구간마다 하나씩 원소를 매칭해주는 문제가 된다. 이건 그리디한 방법으로 구현할 수 있는데, 어제 POI에서 풀었던 Rooks 문제의 풀이와 굉장히 유사한 방법으로 구현할 수 있다.

이런 방식으로 세 가지 경우 각각에 대해 실제로 파괴한 함선 목록을 구해서 출력해주면 답을 얻을 수 있다. 처음 구현해보는 로직이라서 상당히 헤맸는데, 정말로 처음에 각 경우에 대해 어떻게 구현해야 할지 생각을 해놓고 짜지 않았으면 대회 시간 안에 구현하는데 실패했을 것 같다. 복잡한 로직은 충분히 길게 생각하고 구현해야 한다 라는 것을 다시 한 번 강하게 느꼈다.