All Falls Somewhere

고정된 서로 다른 두 정점 $a,b$에 대해 Alice의 점수에서 Bob의 점수를 뺀 값을 생각하자. 최종적으로 정점 $a$에 있는 말 하나는 $+1$, 정점 $b$에 있는 말 하나는 $-1$, 나머지 말은 $0$만큼 기여한다.

$f_{a,b}(i)$를 정점 $i$에 있는 말 하나가 최종 점수 차이에 기여하는 값이라고 하자. $i$번째 턴에 이 말을 인접한 정점 $j$로 옮겼을 때의 기여량은 다음과 같다.

• $j<i$라면 정점 $j$의 턴은 이미 끝났다. $j=a$이면 $+1$, $j=b$이면 , 나머지는 이다.

$i$가 홀수이면 Alice가 가능한 값 중 최댓값을 고르고, $i$가 짝수이면 Bob이 최솟값을 고른다. 이를 $N$부터 $1$까지 역순으로 계산할 수 있다.

이 계산이 말 하나만 따로 움직일 수 있다고 가정하는 것은 아니다. 정점 $i$에 말이 $c$개 모여 있다면 어느 이웃을 고르든 해당 선택이 만드는 점수 차이가 $c$배가 된다. 항상 $c>0$이고, 아직 움직이지 않은 다른 정점의 말이 만드는 값은 이 선택과 무관하다. 따라서 최댓값이나 최솟값을 만드는 이웃은 $c$와 관계없으며, 위 기여량을 모든 말에 선형적으로 적용할 수 있다.

모든 $(a,b)$에 대해 위 DP를 직접 수행하면 너무 느리다. 각 기여량은 $-1,0,+1$ 중 하나라는 점을 사용하자.

$P_a(i)$를 $f_{a,b}(i)=+1$인지 나타내는 값이라고 하자. 정점 에서 이웃 를 고른 결과가 인 조건은 일 때 이고, 일 때 가 참인 것이다. 따라서 다음이 성립한다.

• $i$가 홀수이면 이웃 중 하나라도 조건을 만족할 때 $P_a(i)$가 참이다.
• $i$가 짝수이면 모든 이웃이 조건을 만족할 때 $P_a(i)$가 참이다.

이 점화식에는 $b$가 등장하지 않는다. 그러므로 $+1$을 기여하는 말의 개수

$$X_a=\sum_{i=1}^{N}[P_a(i)]$$

는 $a$에만 의존한다.

마찬가지로 $Q_b(i)$를 $f_{a,b}(i)=-1$인지 나타내는 값이라고 하자. 이번에는 홀수 정점에서 모든 이웃이 조건을 만족해야 하고, 짝수 정점에서는 이웃 하나만 조건을 만족해도 된다. 이 점화식에는 가 등장하지 않으므로

$$Y_b=\sum_{i=1}^{N}[Q_b(i)]$$

는 $b$에만 의존한다.

따라서 순서쌍 $(a,b)$에서 최적 플레이 뒤의 점수 차이는 정확히 $X_a-Y_b$이다. 각 목표 정점에 대해 정점을 역순으로 훑으며 $$와 를 계산한다.

마지막으로 모든 $Y_b$를 정렬한다. 각 $a$에 대해 $Y_b<X_a$인 원소의 개수를 이분 탐색으로 구하고, 이 중 가 포함되었다면 하나를 뺀다.

전체 시간 복잡도는 $O(N(N+M)+N\log N)$이다. 연결 그래프에서는 $M\geq N-1$이므로 으로 나타낼 수 있다. 공간 복잡도는 이다.

Solution written by GPT6