티스토리 뷰

공부

ONTAK 2010

구사과 2017.01.18 14:21

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

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을 세 줄 수가 있고 이렇게 하면 문제를 선형 시간 안에 해결할 수 있다. 너무 어려운 문제.... 

'공부' 카테고리의 다른 글

지하철 1호선 (트리와 쿼리 8) 풀이  (0) 2017.01.26
Centroid Decomposition  (0) 2017.01.26
ONTAK 2010  (0) 2017.01.18
ONTAK 2015  (1) 2017.01.16
Fast Fourier Transform  (2) 2016.11.19
CERC 2011. Racing Car Trail  (0) 2016.11.16
댓글
댓글쓰기 폼
공지사항
Total
267,608
Today
310
Yesterday
629