problem solving 2016.03.16

Network (ICPC Seoul Regional 2007)

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=283&page=show_problem&problem=1903

처음에 DP로 접근했다 시간을 많이 날렸다. (DP 풀이는 잘 모르겠다.) 대충 이런 그리디를 짜서 live archive AC를 먹였는데, 데이터를 믿을 수 없는 저지이기 때문에 (...) 반례가 있다 싶으면 지적해주길 바란다.

 * 리프 노드를 깊이가 큰 순으로 정렬해서 처리한다.

 * 처리중인 노드에서 거리 K 이하에 서버가 없으면 노드의 K번째 조상에 서버를 지어준다. 아니면 넘어간다.

복잡도는 O(N^2)이다.

Superset (CF Yandex 2011 Final)

http://codeforces.com/problemset/problem/97/B

분할정복을 사용한다. 집합을 반으로 가른 후, 왼쪽 셋 1개 / 오른쪽 셋 1개로 쌍을 골랐을 때 그 쌍이 항상 superset이어야 한다. 그렇게 하는 방법은

 * 현재 분할 정복으로 처리하는 구간에 있는 "모든" Y좌표를 모은다.

 * X좌표를 X[m]으로 잡은 후, "모든" Y좌표를 x = X[m] 선에 뿌려준다. (X[m], Y[s]) / (X[m], Y[s+1]) ....

 * 출력 시에 중복 좌표를 주의

참 쉽죠?

이 알고리즘의 정당성은 쉽게 증명할 수 있다. 시간 / 개수 모두 T(N) = T(N/2) * 2 + O(N)을 만족하는 고로 O(NlgN)이다.

Leaders (CF Yandex 2011 Final)

http://codeforces.com/problemset/problem/97/E

임의의 스패닝 트리를 잡고 생각해보자. 쿼리로 들어온 점이 스패닝트리 상에서 홀수 거리면 답은 당연히 Yes이다. 중요한 건 짝수 거리를 처리하는 것이다.

스패닝 트리에 없는 간선을 생각해보자. 이 간선들은 홀수 사이클을 만들 수 도 있고 짝수 사이클을 만들수도 있다. 여기에 대해서 생각해보면 -

* 홀수 사이클을 만든다 : 트리에서 해당 간선을 지나는 경로를 쭉 돌릴 수 있어서, 홀수 거리를 만들어 줄 수 있다.

* 짝수 사이클을 만든다 : 짝수 사이클이 이미 있던 홀수 사이클과 연결되어 있다면 (짝수 사이클을 타고 도달할 수 있다면) 또 하나의 홀수 사이클이 만들어질 수도 있다. 이런 경우에는 홀수 사이클을 만들어 줄 수 있다.

Union Find로 사이클을 묶어주고, LCA로 질의를 처리해주면 풀 수 있다. 비슷한 문제는 JOI 2014 Camp의 전압. http://koistudy.net/?mid=prob_page&NO=1040

Double Knapsack (CF Wunder Fund 2016)

http://codeforces.com/contest/618/problem/F

먼저 배열을 부분합의 형태로 바꾸고, b(j) >= a(i)를 만족하는 최소의 j를 각각의 i = (0 ~ n)에 대해서 구한다. 이 값들은 모두 0 ~ n-1 범위에 속한다.

비둘기집의 원리에 의해, n+1개의 값이 n개의 경우를 가지면 하나의 값은 중복된다. b(j) - a(i) = b(j') - a(i') 라는 뜻인데, (j < j') 이는 b(j') - b(j) = a(i') - a(i) 라는 식으로 전개할 수 있다. 고로 불가능한 경우는 없고 답은 항상 존재한다.