오전 셋

VK cup 15 R2중 몇개를 돌았다.

A. Berland Miners
일단 키가 0인(…) 사람들을 추가해서 사람들을 n명으로 만들자. 키의 내림차순으로 정렬하자.
그러고 나면, 키가 큰 사람(그냥 앞쪽에 있는 사람)은 작은 사람보다 트리의 위쪽, 즉 1번에 가깝게 들어간다. 그렇지 않으면 바꿔도 무방하다.
그러니 PQ를 써서, 처음에는 루트부터 시작해서 정점을 사용할 때마다 정점의 자식들을 넣어준다. PQ에 있는 가장 큰 값을 뽑았을 때, 값이 들어가야 하는 사람의 키 이상이라면 사람을 넣어주고, 정점을 뽑고 자식들을 넣어준다.
만약 그렇지 않다면, 동굴을 높일 시점이 온 것이다. 이때 무조건 기다리고 있는 사람의 키만큼으로 높이를 올려줘야 한다.
그러면 정점들이 여러 개 있는데, 이 중에서 높일것을 잘 고르거나, 전부 빠르게 시행해봐야 한다. 후자를 택한다.
생각해보면, 최종 상태의 동굴 높이와 사람 키이를 오름차순으로 정렬해 보았을 때, (괄호문자열처럼 생각하면) 임의이 시점에서 동굴이 발생하는 횟수가 사람이 발생하는 횟수 이상이여야 한다.
이를 사용하여 세그트리같은 곳에 관리하면, 한 점을 변화시키는 점은 무조건 한개이기 때문에 (나에게 최소값을 주는 점 중 가장 높은 점) 갱신은 많아야 n번 일어난다.

D. Landmarks
각 기둥에 대해서 오른쪽으로 가능한 거리, 왼쪽으로 가능한 거리를 DP로 채우면 된다고 한다. 잘 모르겠다.

오후 셋

CF 17 Final 중 몇개를 돌았다.

E. Combination Lock
회문이니까 연산들을 적당히 접어주고, 필요한 연산 회수를 각 위치(전반부)에 대해서 구한 다음, 이웃한 값의 차이를 가지고 있는다. 이러면 구간에 적용되는 연산이 두 점을 골라, 더했을 때 mod26으로 0인 두 값을 더해주는 것과 같다.
연산으로 고를 수 있는 두 점들을 모두 union해주고, 만약 한 dsjnt set 안에 속하는 점들의 값의 합이 mod26으로 0이 아니라면 불가능, 0이라면 신장 트리를 생각하면 가능하다.

H. Poor Penguins
빙산들의 위치를 보아, 살아남는 얼음판들을 구할 수 있다. 여러 개의 섬들로 나오는데, 두 부분이 끊어질 조건은 십자선을 그었을 때, 대각하는 두 사분면 상에 빙산이 모두 존재하지 않는다는 것이다. 대략 그렇게 모든 직사각형에 대해서 DP를 생각할 수 있다.

I. Full Tournament
원래 상태를 무조건 왼쪽이 이기는 경우로 바꿀 수 있고, 왼쪽이 이기도록 숫자들이 주어지면 항상 만들 수 있다. 대략 그렇게 하면 된다.

J. Tree MST
Boruvka 알고리즘을 쓰면 된다고 에디토리얼에서 그런다. imeimi의 풀이가 이것과 같은것인지는 모르겠다.
알고리즘이 나름 신박한데, 모든 edge set을 logN번 보면 MST가 된다는 것이다.
Kruskal을 생각해볼 때, 가장 가중치가 작은 간선들부터 넣기 시작한다. 비슷하게, Boruvka 알고리즘에서는 각 정점에 대해서 가장 가중치가 짧은 간선을 찾는다. 그리고 그 간선들 사용해서 정점들을 전부 합친다. 그러고 나면 남은 정점 수가 반으로 줄어드므로, logN번만 시행하면 끝난다.
사이클이 안생기고, 최소이고 등의 자세한 증명은 위키에 가면 있을듯.
아무튼, 이 문제에서는 각 정점에서 가장 짧은 간선을 찾는게 생각보다 (O(N^2)을 다 보지 않고도) 빠르게 되서, 사용할 수 있다.

imeimi는 centroid decomposition으로 풀었다. 한 정점을 루트로 했을 때, 서브트리 사이의 간선은 사용하지 않기 때문에, O(N^2)개를 다 보지 않고 kruskal을 돌리면 된다.

생각해보면 요즘에 하는게 이거밖에 없는데, 이정도는 적어야 되는게 아닌가 싶기도 하다. 이거라도 안적으면 남는게 없는거같은 느낌.

분명히 뭔가 부족한거같진 않는데. 뭐가 문젠지 모르곘다. 굉장히 스트레스받는다. 그래도 조금만 더 하면 될거같은 느낌도 든다. 잘 모르겠다. 피곤하다.