빼빼로 선물

서브태스크 1 남은 사람의 집합을 비트마스크로 나타낸다. 각 상태에서 보낼 사람 $a$와 그 사람에게 가장 가까운 모든 $b$를 열거해 두 사람을 지운 상태로 전이한다. 역추적하면 행동도 구할 수 있다. 시간 복잡도는 $O(2^N N^2)$, 공간 복잡도는 $O(2^N+N^2)$이다.

최솟값 원 위에서 연속한 사람 사이의 시계 방향 간격을 $D_1,\ldots,D_N$이라 하자. 마지막 간격은 $D_N=L-X_N+X_1$이다. 홀수 간격 합을 , 짝수 간격 합을 라 하면 최솟값은 이다.

어떤 행동 순서도 완전 매칭을 만든다. 각 쌍이 이동한 최단 호를 택하고, 각 간격을 덮는 호의 수를 세자. 각 사람에서 그 사람을 끝점으로 갖는 호가 정확히 하나이므로, 양옆 간격의 덮인 횟수는 홀짝이 서로 다르다. 따라서 홀수 간격이 모두 홀수 번 덮이거나 짝수 간격이 모두 홀수 번 덮인다. 총거리는 적어도 $\min(A,B)$이다.

두 교대 인접 매칭 중 합이 작은 것을 택한다. 그 합은 $L/2$ 이하이므로 선택한 각 간격도 $L/2$ 이하이고, 실제 최단거리와 같다. 남은 것은 이 매칭을 최근접 규칙에 맞는 순서로 실행하는 일이다.

행동 순서 현재 남은 사람들은 선택 간격과 비선택 간격이 번갈아 나타난다. 선택 간격의 합을 $A$, 비선택 간격의 합을 $B$라 두면 항상 $A\le B$이다. 어떤 선택 쌍도 어느 끝점에서조차 최근접이 아니라면, 모든 선택 간격이 양옆의 비선택 간격보다 크다. 이 부등식을 합하면 $2A>2B$가 되어 모순이다. 따라서 적어도 한 방향으로 합법적인 선택 쌍이 존재한다.

길이 $d$인 합법적인 쌍을 지우면 선택합은 $A-d$, 비선택합은 $B+d$가 된다. 양옆 비선택 간격과 선택 간격이 하나로 합쳐지기 때문이다. 부등식이 유지되므로 같은 논리를 끝까지 반복할 수 있다. 두 명만 남았을 때는 당연히 서로가 최근접이다.

양방향 연결 리스트로 현재 원의 이웃을 관리한다. 각 단계에서 살아 있는 사람을 순서대로 확인하고, 정해진 짝까지의 거리가 양쪽 이웃까지의 거리보다 크지 않으면 그 방향으로 실행한다. 원 위 최근접은 양쪽 이웃 중 하나이므로 이 검사는 충분하다. 시간 복잡도는 $O(N^2)$, 공간 복잡도는 $O(N)$이다.

Solution written by GPT6.1