빼빼로 파티

남은 기부자와 수령자를 각각 번호순으로 정렬하고 같은 순위끼리 매칭한다. 초기에는 자기 자신과 매칭되므로 유효하다. 이후에도 이 매칭이 유효하고 각 매칭 수령자 번호가 기부자의 원래 번호 이하라는 불변식을 유지한다.

기부자 $i$의 매칭 수령자를 $x$, 그 직전 남은 수령자를 $y$라 하자. 직전 수령자가 없으면 $y=0$이다. $L_i>y$인 기부자를 막힌 기부자라고 부르자. 첫 기부자는 항상 막혀 있으므로 적어도 하나 존재한다. 가장 오른쪽의 막힌 기부자 $i$를 선택한다.

응답 $j$는 $L_i$ 이상이므로 $x$보다 왼쪽일 수 없다. $i$와 $j$를 제거하면 그 사이 기부자들의 매칭이 수령자 하나씩 왼쪽으로 이동한다. 선택한 오른쪽에는 막힌 기부자가 없으므로 각 기부자의 조건이 유지된다. 수령자가 작아지므로 조건도 유지된다. 따라서 남은 매칭은 유효하며 모든 턴에 성공한다. 이 전략은 인터랙터의 선택 방식에 의존하지 않는다.

각 남은 기부자에 대해

$$D_i=\operatorname{rank}_{\rm donor}(i)-\#\{\text{남은 수령자 }j<L_i\}-1$$

을 관리한다. 순위는 1부터 센다. 유효한 순서 매칭에서 $D_i\geq0$이며, 막힌 기부자는 정확히 $D_i=0$인 기부자이다. 기부자 $$와 수령자 를 지우면 이고 인 기부자 의 만 1 줄어든다. 인 기부자는 반드시 오른쪽에 있으므로 다른 변화는 상쇄된다.

기부자 원래 번호를 크기 $B$인 블록으로 나눈다. 각 블록은 $L_i$순으로 정렬한 세그먼트 트리에서 접두사에 1을 빼는 연산과 최솟값을 관리한다. 선택한 기부자가 든 블록은 lazy 값을 내려보내고 직접 갱신한 뒤 다시 만든다. 오른쪽의 완전한 블록에는 $L_k\leq j$인 접두사 갱신을 적용한다. 최솟값이 0인 블록 집합을 관리하면 가장 오른쪽의 0을 찾을 수 있다.

시간 복잡도는 $O(N(B+(N/B)\log B))$, 공간 복잡도는 $O(N)$이다. 제공 구현은 $B=1024$를 쓴다. 에서는 순서 매칭을 직접 배열로 관리하는 풀이도 가능하다. 에서는 두 사용 여부 비트마스크를 상태로 모든 수령자 응답을 탐색하는 완전 탐색이 가능하다.

Solution written by GPT6.1