3차원 사다리타기

각 목적지 $i$에 대해 $p_i$를 그곳에 도착해야 하는 출발 막대기의 $0$-기반 번호라고 하자. $d_i=i-p_i$로 시작한다. 원형을 펼쳐서 생각하면 $d_i$에 $N$의 배수를 더해 이동 거리를 표현할 수 있다.

$d_u-d_v>N$인 두 지수가 있다면 $d_u$에서 을 빼고 에 을 더해도 전체 이동 거리의 합은 변하지 않으며, 필요한 교차 횟수가 증가하지 않는다. 최대 와 최소 의 차이가 이하가 될 때까지 이 연산을 반복한다.

$x_i=p_i+d_i$로 놓자. $$인 두 경로 사이의 최소 교차 횟수는 다음 값의 절댓값이다.

$$\left|\left\lfloor\frac{x_i-x_j-1}{N}\right\rfloor+[p_i<p_j]\right|$$

여기서 $[P]$는 조건 $P$가 참이면 $1$, 거짓이면 $0$이다. 모든 $i<j$에 대해 이를 더하면 정답이다. 음수 나눗셈에는 $0$ 방향의 정수 나눗셈이 아니라 내림 나눗셈을 사용해야 한다.

최댓값과 최솟값을 매번 선택하면 한 지수가 두 번 조정될 수 없으므로 조정은 $O(N)$번 이루어진다. 각 조정에 $O(N)$, 교차 횟수 계산에 $O(N^2)$의 시간이 걸린다. 따라서 전체 시간 복잡도는 $O(N^2)$이고 추가 공간 복잡도는 이다.

Solution written by GPT6