SCPC 2024 Round 2 (D, E)

문제를 풀면서 정리한 생각 노트이다.

D

서브태스크가 갑자기 많아졌다. 아무래도 ABC 풀고 D/E 긁기로 본선 컷을 자르겠다는 게 의도 같아 보인다.

 

한편으로는 제출 횟수가 10회 제한이 걸려 있는데 섭테를 6개 주는 것은 조금 잔인하다는 생각도 들었다.

문제 이해 (+Subtask 4)

초기에 $a$의 값이 모두 다르다고 가정하자. $a$는 여러 연산을 통해 그 값이 바뀐다. 이때 $b_i$를 (몇 회의 연산 이후) 현재 $a_i$가 초기의 $a_j$와 같은 $j$값으로 정의하자.

 

이때 어떤 연산을 시행한 이후 $b[l \dots r]$은 $l \le i \le r$인 기존의 $b[i]$ 값 중 하나로 전부 바뀌게 된다. 예를 들어,

• $a = [1, 4, 2, 3]$이었고, 초기에 정의상 $b=[1, 2, 3, 4]$가 된다.
• $[2, 4]$ 구간에서 $\min$ 연산을 시행하면 $a = [1, 2, 2, 2]$가 되고, $b = [1, 3, 3, 3]$이 된다.
• $[1, 3]$ 구간에서 $\min$ 연산을 시행하면 $a=[1, 2, 2, 2]$가 되고, $b=[1, 1, 1, 3]$이 된다.

즉, 연산은 $b$ 배열의 $[L, R]$ 구간에서 어떤 값 $b[i]$를 골라 $[L, R]$ 전부에 덮어씌우는 것으로 생각할 수 있다. (모든 $b[i]$를 고를 수는 없음에 주의하자.)

 

여기서 문제는 어떤 배치가 최적해가 되는지이다. 일단 연산 횟수에 신경쓰지 않고 $\sum (a_i - a_j)^2$를 최대화시키는 방법을 고민해 보자.

 

가장 쉬운 케이스는 $a$의 최댓값과 최솟값을 각각 $n/2$개 근처로 만들 수 있는 경우일 것이다. 예를 들어 초기 배열 $a = [3, 4, 1, 2, 7, 4]$라면 $[1, 1, 1, 7, 7, 7]$ 형태로 만들 수 있고, $\sum (a_i - a_j) = \frac{n^2}{4} (7-1)$이 될 것이다.

 

Claim. $n$이 짝수일 때, 만약 수열의 최솟값 $X$와 최댓값 $Y$가 $n/2$개씩 등장하는 배치를 만들 수 있다면, 이것이 최적해이다.

 

Proof.

• 편의상 다음을 가정한다. $n$이 짝수이고, $a$는 오름차순이며, 최적 결과가 $[X, X, \cdots, X, Y, Y, \cdots, Y]$ ($X$와 $Y$가 각각 $n/2$개씩)임을 보인다.
• $\sum_{1 \le i, j \le n} (a_i - a_j)^2$는 $2 \sum_{1 \le i < j \le n} (a_i - a_j)^2$로 생각해도 좋다. 여기서 $a_i$가 들어가는 항만 모으면 $\sum_{1 \le j \le n} (a_i - a_j)^2$임을 알 수 있다. ($(a_i - a_i)^2 = 0$이기 때문에…)
• $1 \le i \le n/2$이고 $a[i] \neq X$인 $i$가 있는 경우, 이들 중 가장 작은 $i$에 대해 $a[i] = X$로 바꾸는 것이 최적이다.
  • 현재 $a[i] = v$라고 하자. $v > X$라고 가정하자. 이때 $\sum_{1 \le j \le n, i \neq j} (a_i - a_j)^2$는 $(n-1) a_i^2 + \sum_{1 \le j \le n, i \neq j} a_j^2 - 2 a_i \sum_{1 \le j \le n, i \neq j} a_j$이다. 이를 $f(a_i)$라는 함수로 쓰면 이차함수가 되고, $f(x) = (n-1)x^2 - 2x \cdot \sum_{1 \le j \le n, i \neq j} a_j + \sum_{1 \le j \le n, i \neq j} a_j^2$이다.
  • 이 함수는 $x$가 $\frac{\sum_{1 \le j \le n, i \neq j} a_j}{n-1}$에 가까울 수록 작아지고, 멀어질수록 커진다. 저 값을 $m$이라고 하자.
  • 현재 우리는 수열에 $X$가 $n/2$개 미만으로 존재함을 알고 있다. 만약 $m$에서 $X$가 $v$보다 가깝다면 $m \le \frac{X+v}{2}$를 의미한다. 그런데 $\sum_{1 \le j \le n, i \neq j} a_j$는 아무리 작아도 $(i-1)X + (n-i-1)v + Y$이다. 따라서,
  $$
  \begin{alignat}{1}
  m &\ge \frac{(i-1)X + (n-i-1)v + Y}{n-1} \\
  \frac{(i-1)X + (n-i-1)v + Y}{n-1} &\ge \frac{X+v}{2} \\
  \Longleftrightarrow 2(i-1)X + 2(n-i-1)v + 2Y &\ge (n-1)X + (n-1)v \\
  \Longleftrightarrow (n-2i-1)v + 2Y &\ge (n-2i+1)X \\
  \Longleftrightarrow (n-2i+1)v + 2(Y-v) &\ge (n-2i+1)X \,\,\,\,\, (\text{Holds since } X \le v \le Y \text{ and } n-2i+1 > 0) \\
  \therefore m &\ge \frac{X+v}{2}
  \end{alignat}
  $$

• 위 식이 성립하고, 증명이 종료되었다.

• $n/2 < i \le n$이고 $a[i] \neq Y$인 $i$가 있는 경우, 위와 대칭적으로 $a[i] = Y$로 바꾸는 것이 이득임을 보일 수 있다.
• 따라서 위와 같은 해가 존재한다면 최적해임을 알 수 있다.

Claim. $n$이 홀수인 경우, 수열의 최솟값 $X$와 최댓값 $Y$가 각각 $(n-1)/2, (n+1)/2$번씩 등장하는 해가 있다면 이것이 최적해이다.

 

Proof. 위와 동일한 방식으로 하면 된다. (자세한 증명은 Subtask 3을 논할 때 쓴다.)

 

여기서 Subtask 4에 대한 아이디어를 떠올릴 수 있다. Subtask 4는 등장하는 값이 $1$과 $2$뿐이므로 무조건 $X=1$, $Y=2$이다. ($X = Y$인 케이스는 답이 당연히 $0$이므로 고려할 필요가 없다.) 이때, 적당한 연산 한 개를 잡아 무조건 $X$와 $Y$의 개수 차이를 $1$ 이하로 줄일 수 있다. 이 연산을 찾아서 출력해 주면 된다.

 

그렇다면, 모든 경우에 항상 이 형태의 해를 만들 수 있을까? 아래를 보자.

• $n = 6$, $a = [1, 6, 2, 3, 4, 5]$

위 경우 최솟값 $X=1$, 최댓값 $Y=6$이다. 그러나 둘 다 좌측에 몰려 있기 때문에, 다음과 같은 방법을 이용해야 한다.

• $[2, 6]$에서 $\max$ 연산을 한다. $a = [1, 6, 6, 6, 6, 6]$이 된다.
• $[1, 3]$에서 $\min$ 연산을 한다. $a = [1, 1, 1, 6, 6, 6]$이 된다.

위 방법을 관찰하면, 어떤 경우에도 위에서 언급한 최적해를 만들 수 있다는 사실과, 최소 연산 횟수가 무조건 2 이하임을 눈치챌 수 있다.

Subtask 1 (44점)

여기까지 관찰했다면 Subtask 1을 푸는 것은 매우 쉽다. 관찰을 정리해 보면,

• 최소 연산 횟수 2로 최적해를 만들 수 있다.
• 해당 최적해를 찾는 것을 $O(n)$에 할 수 있다. (최댓값과 최솟값의 위치만 알면 가능하므로…)

이제 문제의 나머지 부분은 다음에 집중되어 있다.

• 연산 횟수가 0 또는 1인 방법이 존재하는가?
• 만약 그렇다면, 그 방법은 무엇인가?

먼저 분산 최댓값을 찾는다. 이 값은 단순히 $(\max a - \min a)^2 \times \lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2} \rceil$로 구할 수 있다. 문제는 이 값이 long long 범위를 넘어간다는 점이다. 최대 $n^2 X^2$까지 갈 수 있기 때문에 __int128에 저장해야 한다.

 

다음으로 기존 배열의 분산을 $O(n^2)$에 찾고, 연산을 한 번 해서 만들 수 있는 모든 $O(n^2)$개의 배열에 대해서도 $O(n^2)$에 각각 분산을 찾는다. 이렇게 하면 $O(n^4)$에 문제를 해결할 수 있다.

Subtask 3 (136점)

이제 $n \le 1000$인 경우를 살펴보자. 우리는 연산 횟수가 2인 최적해를 $O(n)$에 찾을 수 있으므로 Subtask 2와 3이 사실상 동등하다.

 

분산을 $O(n^2)$의 시간에 찾는 것은 너무 느리다. $O(n \log n)$ 시간에 찾는 방법도 존재하지만 역시 충분하지 않아 보인다. 중요한 것은 실제 분산이 얼마인지가 아니라, 분산이 최댓값과 같은지가 중요하다는 사실을 상기하자. 분산이 최댓값과 같은지를 알기 위해서는 어떤 식으로 빠르게 계산해야 할까?

 

이를 위해서는 분산이 최댓값이 나올 수 있는 모든 형태에 대해 분석해 보아야 한다. 현재 우리가 알고 있는 사실은 다음과 같다.

• 만약 $n$이 짝수라면, 분산의 최댓값은 $(\max a - \min a)^2 \times \frac{n^2}{4}$이다.
• 만약 $n$이 홀수라면, 분산의 최댓값은 $(\max a - \min a)^2 \times \frac{(n-1)(n+1)}{4}$이다.

$n$이 짝수인 경우의 증명을 다시 되돌아보면, 사실 $X < v$를 적용해도 된다. 이것을 적용하면 $m > \frac{X+v}{2}$가 나오고, $X$로 값을 바꾸는 것이 strict하게 이득임을 알 수 있다. 따라서 $X$와 $Y$가 각각 $n/2$회씩 등장하는 것이 유일한 해임을 얻는다.

 

$n$이 홀수인 경우를 비슷하게 증명해보기로 하자. 이 경우에는 답이 두 가지 있는데 $X$와 $Y$가 각각 $(n+1)/2$회, $(n-1)/2$회 나오거나 그 반대인 경우이다. 이를 증명하자.

 

Claim. $n$이 홀수일 때, 만약 $X$가 $\frac{n-1}{2}$개 미만이라면, $X$ 이상인 값 중 가장 작은 값 $v$를 $X$로 바꾸는 것이 strict하게 이득이다.

 

Proof. 마찬가지로 $a$를 정렬해 놓고, $1 \le i \le n-1$인 $i$ 중 $a[i] \neq X$인 가장 작은 $i$를 잡아 $a[i] = v$라고 하자. 이때 $a[i] = X$로 바꾸는 것이 strict하게 이득임을 보일 것이다. 정의에 따라 $a[n] = Y$임을 알 수 있다.

• 마찬가지로 수식을 계산해 보자. $f(x) = (n-1)x^2 - 2x \cdot \sum_{1 \le j \le n, i \neq j} a_j + \sum_{1 \le j \le n, i \neq j} a_j^2$에서 $f(X) > f(v)$임을 보일 것이다.
• 이는 $m = \frac{\sum_{1 \le j \le n, i \neq j} a_j}{n-1}$에 대해 $m$에서 $v$보다 $X$가 더 멀다는 것을 뜻한다. $X < v$이므로, 이는 $m > \frac{X+v}{2}$임을 뜻한다. 이것을 보이자.
• $m \ge \frac{(i-1)X + (n-i-1)v + Y}{n-1}$이다. 이 값이 $\frac{X+v}{2}$보다 큼을 보이자.
• 이 증명은 짝수일 때의 증명과 거의 똑같이 가다가, 등호조건에서만 차이가 난다. 등호가 나오는 식을 다시 보면,
  • $(n-2i+1)v + 2(Y-v) \ge (n-2i+1)X$인데 $X \le v \le Y$인 경우에 저 등식이 성립하려면 $i = \frac{n+1}{2}$이고 $Y = v$여야 한다. 즉, $a[\frac{n+1}{2}]$는 $X$나 $Y$ 중 어느 쪽이여도 문제없다.

지금까지의 증명을 요약하면 다음과 같다.

• $n$이 짝수라면, 가능한 유일한 해는 $X$가 $n/2$개에 $Y$가 $n/2$개 있는 해이다.
• $n$이 홀수라면, 가능한 해는 $X$와 $Y$를 각각 $(n-1)/2$개, $(n+1)/2$개씩 포함하거나, $(n+1)/2$개, $(n-1)/2$개씩 포함해야 한다.

이제 이 조건을 바탕으로 각 구간마다 답을 $O(n)$에 판단할 수 있다. 그러나 아직 여전히 시간 복잡도는 $O(n^3)$이고, 문제를 풀기에는 너무 느리다. 최소 횟수가 $1$인 경우의 성질을 조금 더 관찰해 보자.

 

일반성을 잃지 않고 한 번의 연산이 $\min$ 연산이라고 가정해 보자. 이 연산을 시행할 구역을 $[L, R]$이라고 하자. 그렇다면 다음 성질이 성립해야 한다.

• $[L, R]$ 구역에 $X$가 최소 하나 이상 존재해야 한다.
• $[L, R]$ 구역 바깥의 $Y$ 개수는 $n/2$개 근처여야 한다. (이 근처라는 것은, $n$이 짝수인 경우 $n/2$, $n$이 홀수인 경우 $\frac{n \pm 1}{2}$를 말한다.)
• $[L, R]$ 밖의 값은 모두 $X$ 또는 $Y$여야 한다.

이 조건은 누적합을 이용하면 $O(1)$에 처리할 수 있고, 문제를 $O(n^2)$에 해결할 수 있다. 하지만 나는 이걸 아무리 최적화해도 시간 초과가 나서 Subtask 2/3을 맞을 수 없었다.

Full Task (100점)

Full task를 풀려면 위의 조건을 만족하는 아무 구간을 빠른 속도로 찾을 수 있어야 한다. 먼저 이 조건을 보자.

• $[L, R]$ 밖의 값은 모두 $X$ 또는 $Y$야 한다.

이 조건을 보기 위해 $X$나 $Y$가 아닌 값 중 가장 왼쪽 위치를 $s$, 가장 오른쪽 위치를 $e$라고 하자. 이때 $L \le s$, $e \le R$이 만족하는 구간만을 보면 된다.

 

만약 $X$나 $Y$ 외의 값이 존재하지 않는다면 (Subtask 4), 답을 찾는 것은 쉽다. WLOG $X$의 개수가 $Y$보다 적다고 해 보자. 적당한 $X$를 하나 잡고, 개수 차이가 $1$ 이하가 될 때까지 양옆으로 구간을 늘려주면 된다.

 

만약 $X$나 $Y$ 외의 값이 존재한다면, 이 구간에 $\min$ 연산을 하는 옵션과 $\max$ 연산을 하는 옵션이 있다. $\min$ 연산을 한다고 가정해 보자. 그렇다면 구간 밖에 들어가야 할 $Y$의 수를 적당히 계산할 수 있다. 해당 $Y$ 값이 될 때까지 구간 $[S, E]$를 왼쪽/오른쪽으로 점점 늘려 주면 된다. 이렇게 하면, $1$인 해가 존재한다면 항상 찾아낼 수 있다.

 

시간 복잡도는 선형이다.

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

using namespace std;

struct Answer{
    int t, l, r;
    Answer(){t=l=r=0;}
    Answer(int t, int l, int r): t(t), l(l), r(r){}
};

int t;
int n;
int arr[50002];
int arr2[50002];
int minCnt[50002], maxCnt[50002], otherCnt[50002];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> t;
    for(int tc=1; tc<=t; tc++){
        cin >> n;
        for(int i=1; i<=n; i++) cin >> arr[i];
        int p = n/2, q = (n+1)/2;

        /// 최댓값을 찾는다.
        int minIdx = 0, minVal = INT_MAX;
        int maxIdx = 0, maxVal = INT_MIN;
        for(int i=1; i<=n; i++){
            if(arr[i] < minVal) minVal = arr[i], minIdx = i;
            if(arr[i] > maxVal) maxVal = arr[i], maxIdx = i;
        }
        if(minVal == maxVal){
            cout << "Case #" << tc << "\n0\n";
            continue;
        }

        for(int i=1; i<=n; i++){
            minCnt[i] = minCnt[i-1] + (arr[i] == minVal);
            maxCnt[i] = maxCnt[i-1] + (arr[i] == maxVal);
            otherCnt[i] = otherCnt[i-1] + (arr[i] != minVal && arr[i] != maxVal);
        }

        /// 답이 0인지 살펴본다.
        bool answerIsZero = minCnt[n] >= p && maxCnt[n] >= p && minCnt[n] + maxCnt[n] == n;
        if(answerIsZero){
            cout << "Case #" << tc << "\n0\n";
            continue;
        }

        cout << "Case #" << tc << "\n";
        /// 여기부터는 답이 1인지 판별하는 구역
        if(otherCnt[n] == 0){ /// 그런 값 없다
            cout << "1\n";
            if(minCnt[n] < maxCnt[n]){ /// min을 만들어야 한다
                int l = minIdx, r = minIdx, diff = maxCnt[n] - minCnt[n];
                while(diff > 1 && l>1){
                    l--;
                    if(arr[l] == maxVal) diff -= 2;
                }
                while(diff > 1 && r<n){
                    r++;
                    if(arr[r] == maxVal) diff -= 2;
                }
                cout << "1 " << l << ' ' << r << "\n";
            }
            else{
                int l = maxIdx, r = maxIdx, diff = minCnt[n] - maxCnt[n];
                while(diff > 1 && l>1){
                    l--;
                    if(arr[l] == minVal) diff -= 2;
                }
                while(diff > 1 && r<n){
                    r++;
                    if(arr[r] == minVal) diff -= 2;
                }
                cout << "2 " << l << ' ' << r << "\n";
            }
            continue;
        }

        /// other가 존재
        int TS = 1, TE = n;
        while(arr[TS] == minVal || arr[TS] == maxVal) TS++;
        while(arr[TE] == minVal || arr[TE] == maxVal) TE--;

        /// 최솟값으로.
        Answer ans;

        if(minCnt[n] <= maxCnt[n]){
            int S = TS, E = TE;
            if(minCnt[E] == minCnt[S-1]) while(S>1 && arr[S] != minVal) S--;
            if(minCnt[E] == minCnt[S-1]) while(E<n && arr[E] != minVal) E++;
            int cnt = maxCnt[S-1] + (maxCnt[n] - maxCnt[E]);
            while(cnt > q){
                if(S>1) cnt -= arr[--S] == maxVal;
                else if(E<n) cnt -= arr[++E] == maxVal;
                else break;
            }
            if(cnt == p || cnt == q) ans = Answer(1, S, E);
        }
        if(ans.t){
            cout << "1\n" << ans.t << ' ' << ans.l << ' ' << ans.r << '\n';
            continue;
        }

        if(minCnt[n] <= maxCnt[n]){
            int S = TS, E = TE;
            if(minCnt[E] == minCnt[S-1]) while(E<n && arr[E] != minVal) E++;
            if(minCnt[E] == minCnt[S-1]) while(S>1 && arr[S] != minVal) S--;
            int cnt = maxCnt[S-1] + (maxCnt[n] - maxCnt[E]);
            while(cnt > q){
                if(E<n) cnt -= arr[++E] == maxVal;
                else if(S>1) cnt -= arr[--S] == maxVal;
                else break;
            }
            if(cnt == p || cnt == q) ans = Answer(1, S, E);
        }
        if(ans.t){
            cout << "1\n" << ans.t << ' ' << ans.l << ' ' << ans.r << '\n';
            continue;
        }

        /// 최댓값으로.

        if(minCnt[n] >= maxCnt[n]){
            int S = TS, E = TE;
            if(maxCnt[E] == maxCnt[S-1]) while(S>1 && arr[S] != maxVal) S--;
            if(maxCnt[E] == maxCnt[S-1]) while(E<n && arr[E] != maxVal) E++;
            int cnt = minCnt[S-1] + (minCnt[n] - minCnt[E]);
            while(cnt > q){
                if(S>1) cnt -= arr[--S] == minVal;
                else if(E<n) cnt -= arr[++E] == minVal;
                else break;
            }
            if(cnt == p || cnt == q) ans = Answer(2, S, E);
        }
        if(ans.t){
            cout << "1\n" << ans.t << ' ' << ans.l << ' ' << ans.r << '\n';
            continue;
        }

        if(minCnt[n] >= maxCnt[n]){
            int S = TS, E = TE;
            if(maxCnt[E] == maxCnt[S-1]) while(E<n && arr[E] != maxVal) E++;
            if(maxCnt[E] == maxCnt[S-1]) while(S>1 && arr[S] != maxVal) S--;
            int cnt = minCnt[S-1] + (minCnt[n] - minCnt[E]);
            while(cnt > q){
                if(E<n) cnt -= arr[++E] == minVal;
                else if(S>1) cnt -= arr[--S] == minVal;
                else break;
            }
            if(cnt == p || cnt == q) ans = Answer(2, S, E);
        }
        if(ans.t){
            cout << "1\n" << ans.t << ' ' << ans.l << ' ' << ans.r << '\n';
            continue;
        }

        /// 답은 무조건 2이다. 잘 풀어보자.
        cout << "2\n";
        int mid = n/2;
        if(minIdx < maxIdx){
            if(maxIdx <= mid) cout << "2 " << maxIdx << ' ' << n << "\n1 " << 1 << ' ' << mid << '\n';
            else if(minIdx <= mid) cout << "2 " << mid+1 << ' ' << n << "\n1 " << 1 << ' ' << mid << '\n';
            else cout << "1 " << 1 << ' ' << minIdx << "\n2 " << mid+1 << ' ' << n << '\n';
        }
        else{
            if(minIdx <= mid) cout << "1 " << minIdx << ' ' << n << "\n2 " << 1 << ' ' << mid << '\n';
            else if(maxIdx <= mid) cout << "1 " << mid+1 << ' ' << n << "\n2 " << 1 << ' ' << mid << '\n';
            else cout << "2 " << 1 << ' ' << maxIdx << "\n1 " << mid+1 << ' ' << n << '\n';
        }
    }
}

E

서브태스크에 $n$, $m$ 관련 제한이 하나도 없는 경우는 꽤나 드물다. 이를 보아 문제의 핵심이 풀이 아이디어를 찾는 쪽이지, 시간을 단축하는 쪽이 아니라는 것을 알 수 있다.

 

서브태스크를 통해 문제에 대한 직관을 얻고, 전체 문제를 해결하는 방향으로 가기로 선택했다.

Subtask 1 (18점)

Bob의 모든 정점에 보물이 있다. Bob 입장에서는 매우 곤란한데, 자신이 턴을 가진다는 것은 상대가 이기는 것에 더 가까워진다는 것이기 때문이다. 따라서 Bob의 정점이 아예 없고 Alice의 정점에도 보물이 하나도 없는 경우를 제외하면 Alice가 항상 이긴다.

Subtask 2 (50점)

Alice의 모든 정점에 보물이 있다. Bob이 자신의 턴을 무한히 가져갈 수 있다면 이기고, 그렇지 않다면 지게 된다. Alice 입장에서는 그러지 못하도록 해야 할 것이다.

 

Alice 입장에서는 자신의 정점이 여럿 연결된 컴포넌트에 넣을 수 있다면 무조건 이긴다. 이러한 점들을 묶고 색칠하자. 만약 이러한 점들로만 연결된 Bob의 정점이 있다면 그 정점에서 시작하면 Alice가 이긴다.

 

반대로 Bob의 정점끼리 연결되어 있는 컴포넌트를 하나로 묶자. 이 컴포넌트 $C$에 속하는 두 정점 $x$와 $y$가 서로 연결되어 있고 두 정점 다 보물이 없다면, 컴포넌트 $C$는 Bob이 무조건 이기는 영역이 된다. 따라서 Alice는 이 정점으로 절대 말을 보내지 말아야 한다. 여기에 해당하는 점들도 모두 색칠해 두자. 만약 Alice의 정점 중 이런 점들로밖에 보내지 못하는 정점이 있다면 해당 점에서 Alice가 진다.

 

이제 위와 같은 경우를 전부 처리했다고 생각하자. 남은 점들에 대해 다음 성질이 만족한다.

• 정점 $x$가 Alice의 정점이라면, 이 정점은 모두 Bob의 정점으로 연결되어 있다.
• 정점 $x$가 Bob의 정점이라면, 이 정점은 모두 Alice의 정점 또는 보물이 있는 Bob의 정점으로 연결되어 있다.

따라서 이 위에서는 어떻게 플레이를 하든 보물이 있는 정점을 무한히 지나갈 수밖에 없고, Alice가 이긴다.

Subtask 3 (96점)

Bob의 모든 정점에 보물이 없다.

 

위와 비슷한 방법으로 생각해 보자. Bob의 정점이 둘 이상 연결된 컴포넌트가 있다면 이 컴포넌트를 Bob의 승리 컴포넌트라고 하자. 만약 말이 이 영역으로 들어온다면 무조건 Bob이 이긴다. Ailce의 정점들 중 이러한 색칠된 점으로밖에 못 보내는 경우가 있다면 Bob이 무조건 이긴다.

 

하지만 여기서 끝이 아니다. 다음과 같은 경우를 생각해 보자. (이후의 그림에서 검은색은 보물이 없는 정점, 빨간색은 보물이 있는 정점이다.)

 

 

이 경우 속에 들어 있는 Alice의 정점에서는 Bob의 승리 컴포넌트로 절대 들어가면 안된다. 그런데 그 점들로 가지 않고 향할 수 있는 Alice의 점들에서도 점수를 얻을 수 없다. 따라서 이 경우 저 점에 들어가면 Alice가 항상 패배한다. 다른 방식으로 생각할 수도 있다. 어차피 Alice의 저 컴포넌트에는 보물 정점이 없으니 저기서 빠져나가면 Bob이 다시 저 컴포넌트로 유도한다고 생각해도 된다.

 

여기서 Alice의 패배 컴포넌트라는 개념을 생각해 보자. 만약 Alice의 정점으로만 이루어진 연결 컴포넌트에 보물 정점이 하나도 없다면, Alice가 승리할 수 없다. 따라서 이러한 컴포넌트를 패배 컴포넌트로 생각할 수 있다. Alice의 패배 컴포넌트와 인접한 Bob의 컴포넌트는 또 다른 유형의 Bob의 승리 컴포넌트가 될 것이다.

 

마지막으로 Alice의 컴포넌트 중 크기가 2 이상이고 보물 정점이 있는 경우 당연히 Alice의 승리 컴포넌트가 된다.

 

위 사항을 정리하면,

• Alice의 컴포넌트의 크기가 $2$ 이상이고 보물 정점이 있는 경우 Alice 승리. - 유형 A
• Alice의 컴포넌트에 보물 정점이 없다면 Bob 승리. - 유형 B
• Bob의 컴포넌트에 정점이 둘 이상이라면 Bob 승리. - 유형 C

이제 남은 경우는 아래와 같다.

• Alice의 크기 $1$ 컴포넌트 (보물 있음) - 유형 D
• Bob의 크기 $1$ 컴포넌트 (보물 없음) - 유형 E

만약 저 컴포넌트들이 모두 승부가 확정된 컴포넌트 (유형 A/B/C)로만 연결되어 있다면, 그 유형을 보고 확정지을 수 있다. 그렇지 않다면, 유형 D/E의 정점들만 서로 연결되어 있는 형태가 된다. 여기에서는 Alice가 무조건 이긴다.

 

이 모든 계산은 $O(n+m)$에 할 수 있을 것이다.

Subtask 4 (155점)

Alice의 모든 정점에 보물이 없다.

 

굉장히 흥미로운 케이스인데, Alice는 보물을 얻어야 하고, 그러려면 Bob의 정점으로 보내야 한다. Bob의 입장에서는 말이 왔다면, 자신의 component 안에서 보물을 얻지 못하도록 최대한 오랫동안 말을 돌려야 한다.

 

앞의 경우와 비슷하게 Bob의 승리 컴포넌트를 다음과 같이 정의하자.

• Bob의 컴포넌트에 보물 정점이 아닌 두 정점이 서로 연결되어 있다면, Bob이 승리한다. - 유형 A

Alice는 저런 유형 A 정점으로 보내면 바로 진다. 따라서 다른 컴포넌트로만 보내야 한다. 유형 A가 아닌 Bob의 컴포넌트를 생각해 보자. 이런 컴포넌트에서 Bob이 말을 가지고 있으면 무조건 보물이 쌓인다. 따라서 Bob은 Alice에게 최대한 빠르게 말을 넘기는 게 좋다. 만약 시작 정점에만 보물이 없다면, Bob이 바로 Alice에게 넘겨도 문제가 없다.

 

 

위 그림에서 왼쪽 아래 Alice 정점이 연결된 Bob 컴포넌트는 유형 A에 해당하지는 않지만, Bob의 정점으로 보내면 Bob이 계속 돌려보내므로 Bob이 승리한다. 그 오른쪽 Alice의 정점에서는 보물이 있는 Bob의 정점으로 보낼 수 있지만, Bob이 말을 다시 맨 왼쪽 아래 Alice의 점으로 보내면 Bob이 승리한다.

 

여기까지 정리했을 경우, 다음과 같은 관계를 알 수 있다.

• 어떤 Alice의 정점 컴포넌트가 유형 A/C의 정점이나 보물이 없는 Bob의 정점만으로 갈 수 있다면, Bob이 승리한다. - 유형 B
• 어떤 Bob의 정점 컴포넌트 안에 보물이 없는 정점 $x$가 있어 $x$가 유형 B의 정점과 연결되어 있다면, Bob이 승리한다. - 유형 C

유형 A, B, C를 제거하고 나면 남은 경우는 다음과 같다.

• Alice의 정점 컴포넌트에서 보물이 있고 유형 A/C의 정점이 아닌 Bob의 정점으로 이동할 수 있다.
• Bob의 정점 컴포넌트에서 보물 정점이 아닌 점은 무조건 Bob의 보물 정점이나 유형 B가 아닌 Alice의 정점으로만 이동 가능하다.

위 유형의 정점만 남은 상태에서 Bob이 승리할 수 있을까? 승리할 수 있다고 가정해 보자. 그렇다면 특정 시점 이후 보물을 얻는 것이 불가능해지도록 하는 Bob의 선택지가 있어야 한다. 그런데 Bob의 보물 없는 정점끼리 연결되어 있는 경우가 제외되었으므로, Bob의 보물 없는 정점에서 Alice의 정점으로 이동해야 할 것이다. 그런데 이 정점은 유형 B에 속하지 않으므로, 이 정점에서는 보물이 있고 유형 A/C의 정점이 아닌 Bob의 정점으로 이동할 수 있다. 이 정점으로 이동하면 다시 보물이 쌓이므로 모순이다.

 

결과적으로, 위 유형 A/B/C에 해당하지 않는 모든 정점에서는 Alice가 승리한다.

Full Task (500점)

이제 전체 문제를 풀어보자. 먼저 base case로,

• 인접한 두 Alice의 정점 중 하나라도 보물이 있다면 이 두 정점에서는 Alice가 이긴다.
• 인접한 두 Bob의 정점에 보물이 없다면 Bob이 이긴다.
• Alice의 정점에서 Alice가 무조건 이기는 정점으로 보낼 수 있다면 Alice가 이긴다. Bob도 마찬가지이다
• Alice의 정점에서 Bob이 무조건 이기는 정점으로만 보낼 수 있다면 Bob이 이긴다. 그 반대도 마찬가지이다.

위 경우를 먼저 처리해 주면, 아래와 같은 상태만 남는다.

• Alice의 정점 (보물 있음): Bob의 정점과만 연결되어 있다. 그들 중 적어도 하나는 Bob이 확정적으로 이기는 점이 아니다.
• Alice의 정점 (보물 없음): Alice의 보물 없는 정점, 또는 Bob이 확정적으로 이기지 못하는 점으로만 이동할 수 있다.
• Bob의 정점 (보물 있음): Bob의 정점, 또는 Alice가 확정적으로 이기지 못하는 Alice의 정점으로만 보낼 수 있다.
• Bob의 정점 (보물 없음): 보물이 있는 Bob의 정점, 또는 Ailce가 확정적으로 이기지 못하는 Alice의 정점으로만 보낼 수 있다.

만약 어떤 시점 이후로 절대 보물을 얻지 못하게 되어 Bob이 승리했다고 가정해보자. 그러면 어떤 경우가 가능할까? 이렇게 만드는 것이 가능한 Bob의 정점 번호를 $x$라고 하자. 이때 $x$가 연결된 Bob의 정점들은 모두 보물이 있으므로 그쪽으로 보내면 안 된다. 따라서 적어도 하나의 (보물 없는) Alice의 정점과 연결되어야 할 것이다. 이 정점을 $y$라 하자. $y$에서 Alice가 아무리 잘 해도 보물을 얻을 수 없다. 이 말은 $y$의 컴포넌트에 보물이 있는 정점이 하나도 없고, $y$의 컴포넌트와 연결된 Bob의 모든 정점은 보물이 없는 정점 (또는 앞에서 Bob의 승리가 이미 확정된 정점)이라는 뜻이다.

따라서, 다음과 같은 방식으로 문제를 풀 수 있다.

• 보물이 없는 Alice의 정점 여러 개가 연결되어 있다면, 하나로 합친다. 마찬가지로 보물이 있는 Bob의 정점 여러 개가 연결되어 있다면, 하나로 합친다.
• 먼저 base case를 큐에 넣는다. (앞 두 개 + 아래 굵은 글씨 두 개)
• 이후 큐에 있는 필승/필패 case들을 순서대로 처리한다. 이때 다음과 같은 케이스가 있다.
  • 어떤 플레이어 $X$의 필승 case에서, 해당 정점이 아직 승패 여부가 결정되지 않은 $X$의 정점 $v$와 연결되어 있다면, 이 정점 $v$ 역시 필승으로 체크한다.
  • 어떤 플레이어 $X$의 필승 case에서, 해당 정점이 아직 승패 여부가 결정되지 않은 $Y$의 정점 $v$와 연결되어 있다면, 이 정점 $v$에서 기존 정점으로의 연결을 제거한다. 만약 $v$에서 더 이상 갈 수 있는 정점이 없다면, $v$는 필패로 체크한다.
  • 어떤 플레이어 $X$의 필패 case에서, 해당 정점이 아직 승패 여부가 결정되지 않은 $X$의 정점 $v$와 연결되어 있다면, 기존 정점으로의 연결을 제거한다. 만약 $v$에서 더 이상 갈 수 있는 정점이 없다면, $v$는 필패로 체크한다.
  • 어떤 플레이어 $X$의 필패 case에서, 해당 정점이 아직 승패 여부가 결정되지 않은 $Y$의 정점 $v$와 연결되어 있다면, 이 정점 $v$는 필승으로 체크한다.
  • 위 과정 중 어느 경우에서든, Alice의 보물 없는 정점 $v$에서 갈 수 있는 option이 Bob의 보물 없는 정점밖에 남지 않은 경우, 해당 정점 $v$를 Alice가 패배하는 정점으로 체크한다.
  • 위 과정 중 어느 경우에서든, Bob의 보물 있는 정점 $v$에서 갈 수 있는 option이 Alice의 정점밖에 남지 않은 경우 / Bob의 정점 $v$에서 갈 수 있는 option이 Alice의 보물 있는 정점밖에 남지 않은 경우, 해당 정점 $v$를 Bob이 패배하는 정점으로 체크한다.
• 여기까지 했는데 남은 정점이 있다면, 해당 정점에서는 항상 Alice가 승리한다.

위의 모든 과정은 $O((n + m) \log n)$에 처리할 수 있다. $\log n$ 항은 union find나 (필요하다면) 정렬 등에서만 붙기 때문에 상수가 굉장히 작다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int x; char winner;
    dat(){}
    dat(int x, char winner): x(x), winner(winner){}
};

struct unionFind{
    int par[100002];

    void init(int n){
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int x){
        if(par[x] == x) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        par[x] = y;
    }
} dsu;

int t;
int n, m, fn;
vector<int> link[200002];
char who[100002], newWho[100002];
int ex[200002], ey[200002];
bool treasure[100002], newTreasure[100002];
char winner[100005];
int firstWhere[100005];

int deg[100002], degPartial[100002][2][2];

int main(){
    scanf("%d", &t);
    for(int tc=1; tc<=t; tc++){
        scanf("%d %d", &n, &m);
        fn = n;
        scanf("%s", who + 1);
        for(int i=1; i<=n; i++){
            char c;
            scanf(" %c", &c);
            treasure[i] = (c == 'T');
        }
        for(int i=1; i<=m; i++) scanf("%d %d", &ex[i], &ey[i]);


        /// dsu 압축
        {
            dsu.init(n);
            for(int i=1; i<=m; i++){
                if(who[ex[i]] != who[ey[i]]) continue;
                if(who[ex[i]] == 'A' && (!treasure[ex[i]] && !treasure[ey[i]])) dsu.merge(ex[i], ey[i]);
                if(who[ex[i]] == 'B' && (treasure[ex[i]] && treasure[ey[i]])) dsu.merge(ex[i], ey[i]);
            }

            vector<int> roots (1, 0), convert (n+1);
            for(int i=1; i<=n; i++) if(dsu.find(i) == i) roots.push_back(i);
            n = (int)roots.size()-1;
            for(int i=1; i<=n; i++) convert[roots[i]] = i, newTreasure[i] = 0;
            for(int i=1; i<=fn; i++){
                firstWhere[i] = convert[dsu.find(i)];
                if(treasure[i]) newTreasure[firstWhere[i]] = 1;
                newWho[firstWhere[i]] = who[i];
            }

            for(int i=1; i<=n; i++) link[i].clear(), treasure[i] = newTreasure[i], who[i] = newWho[i];
            for(int i=1; i<=m; i++){
                int x = convert[dsu.find(ex[i])], y = convert[dsu.find(ey[i])];
                if(x==y) continue;
                link[x].push_back(y), link[y].push_back(x);
            }
        }

        /// 초기화
        for(int i=1; i<=n+2; i++) winner[i] = 0;
        for(int i=1; i<=n; i++){
            winner[i] = 0;
            sort(link[i].begin(), link[i].end());
            link[i].erase(unique(link[i].begin(), link[i].end()), link[i].end());
            deg[i] = (int)link[i].size();
            for(int a=0; a<2; a++) for(int b=0; b<2; b++) degPartial[i][a][b] = 0;
            for(int y: link[i]){
                degPartial[i][who[y]-'A'][treasure[y]]++;
            }
        }

        queue<dat> que;

        /// base case
        for(int i=1; i<=n; i++){ /// A 확인
            if(who[i] == 'A'){
                bool win = 0, lose = 0;
                if(!deg[i]) lose = 1;
                else if(treasure[i] && (degPartial[i][0][0] || degPartial[i][0][1])) win = 1;
                else if(!treasure[i] && degPartial[i][0][1]) win = 1;
                else if(!treasure[i] && deg[i] == degPartial[i][1][0]) lose = 1;

                if(win) winner[i] = 'A', que.push(dat(i, 'A'));
                if(lose) winner[i] = 'B', que.push(dat(i, 'B'));
            }
            else{
                bool win = 0, lose = 0;
                if(!deg[i]) lose = 1;
                else if(!treasure[i] && degPartial[i][1][0]) win = 1;
                else if(treasure[i] && deg[i] == (degPartial[i][0][0] + degPartial[i][0][1])) lose = 1;
                else if(!treasure[i] && deg[i] == degPartial[i][0][1]) lose = 1;

                if(win) winner[i] = 'B', que.push(dat(i, 'B'));
                if(lose) winner[i] = 'A', que.push(dat(i, 'A'));
            }
        }

        /// 이제 전부 search
        while(!que.empty()){
            int x = que.front().x; char c = que.front().winner; que.pop();
            char w = who[x];

            for(int y: link[x]){
                if(winner[y]) continue;
                if(who[y] == w){ /// 같은 사람이다
                    if(c == w) winner[y] = c, que.push(dat(y, c));
                    else deg[y]--, degPartial[y][who[x]-'A'][treasure[x]]--;
                }
                else{ /// 다른 사람이다
                    if(c != w) winner[y] = c, que.push(dat(y, c));
                    else deg[y]--, degPartial[y][who[x]-'A'][treasure[x]]--;
                }

                if(who[y] == 'A'){
                    if(!deg[y]) winner[y] = 'B', que.push(dat(y, 'B'));
                    else if(!treasure[y] && deg[y] == degPartial[y][1][0]) winner[y] = 'B', que.push(dat(y, 'B'));
                }
                else{
                    bool lose = 0;
                    if(!deg[y]) lose = 1;
                    else if(treasure[y] && deg[y] == (degPartial[y][0][0] + degPartial[y][0][1])) lose = 1;
                    else if(!treasure[y] && deg[y] == degPartial[y][0][1]) lose = 1;

                    if(lose) winner[y] = 'A', que.push(dat(y, 'A'));
                }
            }
        }

        for(int i=1; i<=n; i++) if(!winner[i]) winner[i] = 'A';
        printf("Case #%d\n", tc);
        for(int i=1; i<=fn; i++) printf("%c", winner[firstWhere[i]]);
        puts("");
    }
}