빼빼로 교환

어떤 높이 $t$ 이하인 담장만 이어 보면 사람들은 여러 연결 성분으로 나뉜다. 비용이 $t$ 이하인 짝은 같은 성분 안에서만 만들 수 있다. 크기가 $s$인 성분에서 만들 수 있는 짝은 최대 $\lfloor s/2\rfloor$개이다. 담장을 높이 오름차순으로 처리하면서 각 성분 내부에서 가능한 만큼 짝을 만들고, 크기가 홀수이면 한 사람을 남긴다. 크기가 둘 다 홀수인 두 성분이 높이 $h$인 담장으로 합쳐질 때만 남은 두 사람을 새로 짝지어 비용 $h$를 더한다. 다른 경우에는 새 짝이 필요 없다. 두 성분에 남은 사람 사이 경로의 최대 높이는 정확히 $h$이므로 이 짝의 비용은 $h$이다. 이 과정은 모든 높이 기준에서 가능한 저비용 짝 수의 상한을 동시에 달성한다. 높이를 작게부터 정렬한 짝 비용 각각이 다른 모든 완전 짝짓기의 대응 비용 이하이므로 합도 최소이다. DSU와 정렬로 시간 $O(N\log N)$, 공간 $O(N)$이다. 첫 서브태스크는 사람의 부분집합을 비트마스크로 두고, 가장 앞의 남은 사람의 상대를 모두 시도하는 $O((2N)^2 2^{2N})$ 상한의 DP로 해결한다.

Solution written by GPT6.1