ONTAK 2010

.. 다 정리할 생각은 없다. 그냥 어젯밤에 풀었던 문제들 정리.

https://github.com/koosaga/olympiad/tree/master/POI 에서 ontak10_으로 시작하는 cpp들이 풀이이다.

Highways

https://www.acmicpc.net/problem/8476

결국 dfs traversal로 나타내면 2차원 평면상에 몇개의 점이 있는지를 세는 문제로 환원할 수 있다. 전형적인 2D Query 문제. main.edu.pl에서 실험해 봤을 때 O(qlg^2n)은 TLE가 났었음. O(n + (m + q)lgn)에 짜야 한다. 

요 근래 2D Query는 거의 상식이 되어 가는 것 같다. 잘 해야 한다.

Excursion

https://www.acmicpc.net/problem/8480

옛날에 출제했던 김치(https://www.acmicpc.net/problem/11001) 문제랑 비슷한 컨셉인데, 차이점은

 * 김치 문제는 미리 계산된 값들을 처리하는 것이라 divide & conquer opt. 가 먹혔는데, 이 문제는 DP를 계산하면서 진행하기 때문에 그 풀이가 먹히지 않는다

 * 구간의 길이 D가 일정하지 않다 (김치 문제는 이를 활용한 풀이가 당시 존재했다)

 * 김치 문제는 기울기 증가 쿼리 증가지만, 이 문제는 기울기와 쿼리 모두에 있어 제약 조건이 없다.

... 그냥 전반적으로, 더 독해졌다고 보면 된다.

내가 의도했던 김치 풀이 (Segment Tree + CHT) 를 통해서 O(nlg^2n)에 풀 수 있긴 한데, 지금 다시 생각해보면 아무래도 그보다는 분할 정복을 통해서 O(nlg^2n)에 푸는 것이 낫지 않나 싶어서, 그렇게 코딩했다. 메모리라던지 상수라던지 뭐 모든 면에서...

분할 정복은 DP값을 뿌려주는 형태로 작동하는데, [S, E] 구간의 DP 값을 계산하라 하면, [S, M] 구간의 DP값을 계산하고, [S, M]에 있는 DP값을 [M+1, E]에 뿌려준 후, [M+1, E] 구간의 DP값을 계산하는 식으로 루틴을 돌리는 것이다. 

결국 뿌려주는 것이 문제의 핵심이라고 할 수 있는데, std::set으로 CHT를 O(nlgn)에 구현하면 되지만 아무래도 음... 이 때 내가 코더스 하이에 출제했던 반평면 땅따먹기 (https://www.acmicpc.net/problem/12795) 문제가 생각났는데, 당시 의도한 풀이였던 O(n^1.5)가 O(nlgn)보다 실제 수행 시간이 빠른 것을 확인해서, O(n^1.5)에 동적 CHT를 구현했고, 실제 시간 복잡도가 O(n^1.5lgn)인데도 굉장히 빠른 시간 안에 작동하는 것을 확인했다. std::set에 iterator를 꼬고 또 꼬아서 구현하는 O(nlgn)보다, order notation 뒤에 붙은 상수가 훨씬 더 빠른 것으로 보인다... 

교훈은, 동적 CHT를 구현할 일이 생긴다면 O(nlgn)보다 O(n^1.5)가 더 나은 선택일 수 있다는 것이다. 코딩은 확실히 그렇고, constant factor 측면에서도.

Life of the Party

https://www.acmicpc.net/problem/8470

옛날에 Racing Car Trail (http://koosaga.com/138) 이라는 문제를 다루면서 언급했던 것과 아주 비슷한 문제이다.

일단 매칭은 빠르게 O(K(N+M)^0.5)에 찾을 수 있으니, 이후 그 정점을 막고 alternating path를 찾는 것을 반복하면 O(K(N+M)) 시간에 문제를 해결할 수 있지만, 아무래도 느리다. 

이를 줄이는 것은 생각보다 어렵지 않은데, 결국은 alternating path를 찾는다는 것이 무향 그래프에서 free한 vertex들이 도달 가능한지를 판별하는 것이다. 그 vertex들에서 거꾸로 flood fill을 하면, 도달 가능한지를 쉽게 판별할 수 있다. flood fill을 하는데 O(K + N + M)의 시간이 들기 때문에, alternating path의 존재 여부를 한번의 dfs로 찾을 수 있다. 남자 / 여자 side에서 각각 이를 해주면 된다. 

여담으로, 이 방법을 통해서 Racing Car Trail을 O(N^3)에 풀 수 있다.

Vacation

https://www.acmicpc.net/problem/8472

간단한 min-cost max-flow 문제이다. 각각의 n개의 구간에 대해서 k개 초과의 날짜를 선택하면 안되는데, 각각의 날짜에 여행을 떠나는 것을 [i, i + n - 1]의 구간을 차지한다고 생각하면, 각각의 날짜에 대해서 겹치는 구간의 개수가 k개 이하인 조건을 만족하게, 최대 비용의 구간을 선택하는 문제가 된다. 이 문제는 min-cost max-flow로 해결할 수 있다.

MCMF는 O(fVE)인 고로, 시간 복잡도는 O(kn^2)로 아주 빠르다고 할 수 있다. SPFA를 쓰면 O(kn) 정도의 시간에 작동하는 것을 기대할 수도 있다.

여담으로 MCMF를 사용하지 않은 O(nk^5) dynamic programming 풀이도 있다. 날짜의 길이가 3n인 점을 적극적으로 이용하는 것 같다. 아마 의도된 풀이가 이것이 아닐까 싶다. http://codeforces.com/blog/entry/49356?#comment-333699

Palindromic Equivalence

https://www.acmicpc.net/problem/8477

너무 어려운 문제. 관찰이 너무 안 떠올라서 문제 풀다 말고 계속 딴짓했던 문제이기도 하다 (마침 저번 코포에 폴란드공이 나와서 (...) 레딧에서 폴란드공 찾아보다가 2시간을 보냈다.) 

결국은 이 문제를 어떠한 그래프의 26-coloring의 경우의 수를 세는 문제로 치환할 수 있다. 각각의 위치를 중심으로 하는 최대 팰린드롬의 길이가 같으면 (= manacher's algorithm의 결과가 같으면) palindromic equivalence한 문자열이다. 이는 어떠한 두 위치의 문자열이 같다 / 다르다의 관계로 귀결되며, 같은 정점끼리는 묶어서 슈퍼노드로 만들어주면 결국은 그래프가 나오고 이 그래프의 26-coloring의 개수를 세면 된다. 그 문제가 NP인건 말할 필요도 없을 거지만..

그래프 자체는 manacher's algorithm을 돌리면서 O(n)에 만들어 줄 수 있는데, coloring을 세는 게 문제가 된다. 나는 이런 식의 접근 방법이 당연히 아닐 것이라고 생각해서 이 쯤에서 포기했었는데, 놀랍게도 이런 식의 접근 방법이 맞고 coloring을 다항 시간 안에 세줄 수 있다고 한다. 

정확히는, super node i에서 인덱스가 가장 작은 원소를 G(i) 라고 부르자. G(i) < G(k), G(j) < G(k)일 때, i - k, j - k간에 간선이 있다면 i - j 간에 간선이 있음을 증명할 수 있다. (그 증명을 읽었는데 잘 이해가 안 간다... 작성자 분이 공개를 원치 않으셔서 여기 올리지는 않는다.) 고로, G(i)가 작은 순으로 그냥 그리디하게 coloring을 세 줄 수가 있고 이렇게 하면 문제를 선형 시간 안에 해결할 수 있다. 너무 어려운 문제....