적분

각 위치 $i$에 대해

$$D_i=X_i-Y_i$$

라고 하자. 여기서 문자를 정수로 보아 0은 $0$, 1은 $1$로 생각한다. 그러면 $D_i$는 $-1,0,1$ 중 하나이다.

먼저 목적식을 $D_i$로 바꾸자. $S$의 앞 $i$글자에 포함된 1의 개수를 $one_S(i)$라고 하면,

$$f_S(i)=one_S(i)-(i-one_S(i))=2one_S(i)-i$$

이다. 따라서

$$f_X(i)-f_Y(i)=2(one_X(i)-one_Y(i))=2\sum_{j=1}^{i}D_j$$

이다. 그러므로 전체 목적식은

$$2\sum_{i=1}^{N}\sum_{j=1}^{i}D_j = 2\sum_{j=1}^{N}D_j(N-j+1)$$

이다.

이제 연산이 $D$에 어떤 영향을 주는지 보자. 구간 $[l,r]$에서 $X$와 $Y$의 1 개수가 같다는 것은

$$\sum_{i=l}^{r}D_i=0$$

이라는 뜻이다. 이 구간을 서로 바꾸면, 해당 구간의 모든 $D_i$는 부호가 바뀐다. 즉 $D_i$가 $1$이면 $-1$이 되고, $-1$이면 $1$이 되며, $0$은 그대로 $0$이다.

따라서 문제는 다음과 같이 바뀐다.

$D_i \in \{-1,0,1\}$인 수열이 있다. 합이 $0$인 연속구간의 부호를 원하는 만큼 뒤집을 수 있다. 이때

$$\sum_{i=1}^{N}D_i(N-i+1)$$

를 최대화하여라.

$D_i=0$인 위치는 어떤 연산을 해도 계속 $0$이다. 이제 $D_i \ne 0$인 위치들만 보자. 만약 어떤 두 비영 위치 사이에 $-1$이 먼저 나오고, 그 뒤에 $1$이 나오며 그 사이가 모두 $0$이라면, 그 전체 구간의 합은 $0$이다. 이 구간을 뒤집으면

$$-1,\ 0,\ 0,\ \ldots,\ 0,\ 1$$

이

$$1,\ 0,\ 0,\ \ldots,\ 0,\ -1$$

이 된다. 즉 비영 위치들만 보면 인접한 $-1,1$을 $1,-1$로 바꿀 수 있다.

이 연산을 반복하면, $D_i \ne 0$인 위치들에서 모든 $1$을 앞쪽으로, 모든 $-1$을 뒤쪽으로 보낼 수 있다. 또한 연산은 $1$의 개수와 $-1$의 개수를 바꾸지 않으므로, 이보다 더 앞쪽에 $1$을 많이 놓을 수는 없다.

가중치 $N-i+1$은 $i$가 작을수록 크다. 따라서 최적 상태는 다음과 같다.

• $D_i \ne 0$인 위치들을 왼쪽부터 모은다.
• 그중 앞에서부터 원래 $D_i=1$이었던 개수만큼 $1$을 배치한다.
• 나머지 비영 위치에는 $-1$을 배치한다.
• $D_i=0$인 위치는 계속 $0$이다.

따라서 구현은 간단하다. $D_i \ne 0$인 위치들을 배열에 저장하고, $D_i=1$인 개수를 $P$라고 하자. 비영 위치 배열을 $pos$라고 하면 최댓값은

$$2\left( \sum_{t=0}^{P-1}(N-pos_t) - \sum_{t=P}^{|pos|-1}(N-pos_t) \right)$$

이다. 여기서 구현에서는 $pos_t$를 $0$-indexed 위치로 저장했기 때문에 가중치가 $N-pos_t$가 된다.

시간 복잡도는 $O(N)$이고, 메모리 복잡도는 $O(N)$이다.