오전 셋

Nordic OI 2017 2문제를 돌았다.

A. Subway

한 트리를 다른 트리로 변형하는데, 한 간선을 없애고 한 간선을 만들 수 있다. 이때 연결그래프여야 한다. 어떻게 할 것인지 구하는 문제.

원래 트리 (A트리)와 나중 트리(B트리)에서 겹치는 간선들은 제외한다. 제외한 간선들로 정점을 이어주면, 나머지 간선들을 봤을 때 트리들을 정점으로 하는 트리가 2개 생긴다. 이제 A’트리에서 B’트리로 만들어야 하는데, A’트리의 리프를 끊고, 동일한 정점의 B’트리에서의 부모로 가는 간선을 이어 주면 된다.

SJ가 안 들어가 있다. CF에 동일한 문제가 있다.

B. Yule Lads

한 점을 포함하는 최대 넓이 정사각형을 찾는 문제다.

우선 파라메트릭이나 DP같은걸로 한 점을 꼭지점으로 했을 때의 최대 넒이 정사각형을 구해줄 수 있다. 그러고 나면 전체 격자에 칠해 주는 것이 문제인데, 이는 그냥 한줄씩 훑어 나가면 된다. union-find로 해도 되고, set으로 해도 될 것 같다.

오후 셋

APC001 중 CDFH를 돌았다.

C.

한 구간을 잡았을 때, 기우성이 잘못된 구간이 항상 존재하기 때문에 그냥 이분탐색하면 된다.

D.

각 컴포넌트에서 1개 이상의 점을 고르고, 고른 점이 2n-2개라면 트리를 만들 수 있다. 이 때 이 점들의 가중치 합이 최소이여야 하므로, 그냥 가장 작은것들을 골라주면 된다.

F.

트리에서는, 각 정점에 인접한 간선들의 가중치를 전부 xor한 값이 0인 것과 간선의 가중치가 전부 0인 것이 동치이다. 이를 사용하면 비트마스킹 DP로 가능하다.

H.

여러 가지 풀이가 있으나, 문제 고안자의 풀이는 O(NlogN)이다.

임의의 루트 있는 트리를 잡았을 때, ‘가지’ 노드들을 정의할 수 있다. 만약 노드가 리프면 가지이고, 자식이 한개뿐인데 자식이 가지이면 가지이다. 즉, 한 리프에서 최대한 위로 올라간 경로들이라고 생각할 수 있다.

만약 한 트리의 가지들을 전부 제거하면, 리프의 수는 절반 이하로 줄어든다. 이는 가지가 달린 정점들이 전부 자식이 2 이상이기 때문이다.

그래서 한 연산에서 가지들을 O(N)에 제거하면 되는데, 이는 적당히 해주면 된다.

가지를 잡는 아이디어는 괜찮은 것 같다.