problem solving 2016.02.02

Water Tree (CF 343D)

http://codeforces.com/problemset/problem/343/D

거꾸로 생각한다. 기본적으로 모든 노드에 물이 채워져 있고, 1 ~ N개의 노드에 물을 비우는 연산을 넣어 줬다고 가정하자. 비우는 연산이라 함은 해당 노드와 그 부모에 있는 물을 모두 제거함을 뜻한다.

 * Query 1 : v의 서브트리에, 물이 비우는 연산이 적용되어 있는 노드가 있다면, 모두 지워주고, v의 부모에 물을 비우는 연산을 적용한다.

 * Query 2 : v에 물을 비우는 연산을 적용한다.

 * Query 3 : v의 서브트리에 물이 비우는 연산이 적용되어 있었다면 0, 아니면 1을 출력한다.

문제가 아주 깔끔해졌으며, dfs number 순서대로 수를 보관해두면, 세그먼트 트리로 각각의 연산을 O(lgN)에 처리할 수 있으니, O(N + QlgN)에 해결된다.

또한, 세그먼트 트리를 안 쓰고도 해결할 수 있는데, std::set으로 2번 3번 연산은 O(lgN)에 가능하고, 1번 연산은, 서브트리에 있는 모든 노드를 일일히 지워주면서 해결한다. 생각해보면 std::set에 삽입되는 원소의 합이 O(N + Q)인 고로 삭제되는 원소의 합도 그럴 것이고, 모두 일일히 지워줘도 O((N + Q)lgN)이다.

Ciel the Commander (CF 321C)

http://codeforces.com/problemset/problem/321/C

간단한 전략으로는 아무 루트를 잡은 후 깊이 0일 때 A, 1일 때 B, 2일 때 C 이런 식으로 값을 넣어주는 것이다. 만약에 깊이를 25로 바운드 시키는 방법이 존재만 한다면, 적절한 루트를 잡고 그냥 bfs를 시켜주면 문제를 풀 수 있다. 물론 간단한 전략이고, 선에서는 꼼짝없이 O(N).

생각해 보면, 문제가 아주 재귀적으로 정의된다는 것을 알 수 있다. 아무 점에다가 A를 잡으면, 그 점을 중심으로 여러개의 서브트리가 나눠지며, 그 서브트리에 대해서 똑같이 문제를 쭉쭉 풀어주면 문제를 해결할 수 있다. 중요한 건 이러한 작업의 깊이가 26 이하여야 한다는 점인데, 이는 centroid decomposition을 사용하면 된다. centroid를 기준으로 트리를 쪼개면, 서브트리의 크기를 항상 반 이하로 만들어줄 수 있기 때문에, 17개 언저리의 알파벳으로 트리를 배치가 가능하다.

NAFTA (BOJ 10863)

https://www.acmicpc.net/problem/10863 (영어 : http://hsin.hr/2015/final/second_day/tasks.pdf)

조금만 생각해보면 결국 x축에다 송유관을 쭉 꽂아서 기름을 뽑아오는 것이기 때문에 y축이 전혀 필요없다는 것을 알 수 있다. Flood Fill을 통해서 각각의 영역의 최소 X좌표, 최대 X좌표, 기름 합을 구하면, 다음과 같은 구간이 O(NM)개 생긴다.

 * [sx, ex] 구간에 송유관을 꽂으면, V의 이득을 얻을 수 있다. (1 <= sx <= ex <= M)

이제 S개의 송유관을 꽂아서 얻을 수 있는 최대의 이득에 대해서 고민해봐야 한다. 송유관을 순서대로 꽂는다고 생각하면, dp[i][j] -> i번 위치에 j번째 송유관을 꽂았을 때 얻을 수 있는 최대 이득 이라고 생각할 수 있다. dp 식은 충분히 만들 수 있지만 조금 더럽다.

거꾸로, dp[i][j] -> i번 위치에 j번째 송유관을 꽂았을 때 놓칠수 있는 최소 이득 이라고 생각해보자. 모든 송유관을 꽂았을 때를 생각해보면, 이렇게 해서 놓치는 이득은 송유관 사이에 존재하는 구간들로 정의가 된다. 즉, dp[i][j] = Min(dp[k][j-1] + Cost(k+1, j-1)) 이라고 정의했을 때, Cost(s, e) -> [s, e] 안에 포함되는 구간들의 가중치 합으로 계산할 수 있다. Cost(s, e)를 O(NM)에 계산하면 O(N^2M^3)의 알고리즘을 만들 수 있다.

Cost(s, e)를 이제 O(1)에 계산해보자. s <= s' <= e' <= e를 만족하는 송유관의 가중치합을 빠르게 구해야 하는데, 2차원 좌표 (x, y) = (s', e')을 생각해 보자. 그러한 가중치 합은, [s, e] x [s, e] 직사각형 안에 들어있는 2차원 좌표들의 가중치 합이 된다. 이는 부분합을 통해서 O(1)에 빠르게 계산 가능하다. 이제 O(NM^2)이다.

이제 꽤 유명한 분할 정복을 통해서 이 문제를 O(NMlgM)에 해결할 수 있다. 여기에 대해서는 특별한 설명을 하기보다는, 내가 비슷한 문제 (http://koistudy.net/?mid=prob_page&NO=1140)에 제공했던 풀이 파일을 주는 걸로 대신하겠다. 분할 정복 최적화로 알려져있는 테크닉이며, 최근 IOI에도 출제된 바 있는등, 꽤 유명한 문제이다.

리소스 :

http://blog.naver.com/dark__nebula/220424213129

http://codeforces.com/blog/entry/8219

비슷한 문제 :

지하철 3호선 : http://koistudy.net/?mid=prob_page&NO=1140

CEOI 2004 목공소 두개 : http://koistudy.net/?mid=prob_page&NO=2044

IOI 2014 휴가 : http://oj.uz/problems/view/IOI14_holiday