Codeforces Round 985 F. Palindrome Everywhere

문제

길이 n의 사이클이 있다. 간선은 i->(i+1) mod n으로 가며 R 또는 B로 색깔이 있다. 이때, 모든 쌍 (i,j) (i<j)에 대하여 i에서 j로 가는 팰린드롬 경로가 있으면 YES, 팰린드롬 경로가 없는 쌍이 하나라도 있다면 NO를 출력하시오. 팰린드롬 경로란, 경로 위의 간선의 색깔을 순서대로 배치했을 때 나오는 문자열이 팰린드롬임을 뜻한다. 이때 경로는 같은 간선, 정점을 여러 번 지나도 된다.

 

풀이

팰린드롬으로 간선을 지나가야 한다는 것이 좀 복잡해 보인다. 생각을 편하게 하기 위해서 i,j에 위치하는 두 사람이 있고 이 두 사람이 만나야 하는데, 두 명이 이동하기 위해서는 항상 같은 색깔의 간선만 타고 가야하는 문제라고 문제 서술을 약간 바꿔보자. 문제를 이렇게 바꾸면 꽤 다루기 편한 형태가 된다. 이제 관찰을 하자.

관찰 1) R로 색깔이 같은 인접한 간선과 B로 색깔이 같은 인접한 간선이 같이 존재할 경우, 답은 NO이다. 왜냐하면 그 두 위치에 두 사람을 배치하면 움직일 수 없다.

이 관찰 하나로 간선의 형태를 매우 단순화시킬 수 있다. 어떤 한 색깔의 간선은 절대 인접할 수 없기 때문이다.

하지만 아직은 정보가 부족하니 특수한 형태를 좀 보자.

이웃한 모든 간선의 색깔이 다른 경우를 생각해보자. 이 경우 두 사람을 아무렇게나 배치하면 둘은 계속 같은 방향으로만 가기 때문에 영원히 만날 수 없다. 음.. 지금까지를 보면 두 사람이 만나지 못하려면 결국 어떤 곳에서 둘다 빠져나오지 못하거나, 계속 빙빙 도는 형태일 것이라고 생각할 수 있다.

좀 더 쉬워보이는 둘 다 빠져나오지 못하는 경우를 생각해보자. 관찰 1 덕분에 우리는 한 색깔의 간선이 절대 인접할 수 없다는 것을 알기 때문에, 이 색깔을 B로 고정하고 R만 연속할 수 있다고 해보자. 그리고 나서 연속한 R을 그룹으로 묶자. i, j가 같은 그룹에 있다면 당연히 팰린드롬 경로가 있을 것이다. 그렇지 않다면 B를 몇 개 건너야 만날 수 있는 형태일 것이다. 그럼 애초에 B를 건너지 못하는 경우라면 어떨까? 둘은 반드시 같이 이동해야 하므로 어떤 한 명이 B에 인접해있을 때 한명은 반드시 인접해있지 않다면 둘은 영원히 그 그룹을 빠져나가지 못한다. 그리고 그러한 경우는 바로, 그룹의 R 개수가 둘 다 짝수개일 때 가능하다. 이 경우 i와 j를 그룹 내에서 parity를 다르게 배치하면 된다.

다시 말해서, 그룹 중에 크기가 짝수인 것이 2개 이상 있다면 답은 NO인 것이다. 따라서 우리는 짝수인 그룹의 개수를 1개 이하로 줄일 수 있다! 그리고 또 잘 생각해보면 짝수인 그룹은 반드시 1개여야 한다. 그 이유를 알기 위해서 홀수 - 홀수 그룹의 상황을 관찰하자. 둘 모두 홀수 그룹에 있다면 둘의 parity가 같거나 다른 두 상황이 나온다. 이 두 상황 모두 둘의 방향성이 일정하다. 

i와 j은 노란색 방향으로 동시에 빠져나가거나, 초록색 방향으로 동시에 빠져나간다. 이 때 i, j가 새롭게 들어온 그룹도 홀수라면, 그 그룹에서의 parity 역시 동일하게 유지되므로 일정한 방향으로 계속 이동한다.

 

그런데 우리는 i와 j의 parity를 임의로 지정해줄 수 있고(모든 쌍에 대해 만족해야 하므로), 만약 parity가 같게 지정해준다면(그림에서 2번 상황) 둘은 짝수 그룹에 도달하기 전까지는 같은 방향으로 이동한다.

사이클에 홀수 그룹만 있다면 방향성이 영원히 유지된다. 따라서 위 사진과 같이 방향성을 줄 경우 영원히 만나지 않는다.

따라서 짝수 그룹이 없다면 영원히 돌게 만드는 상황을 만들 수 있고 이때 답은 NO이다.

이제 우리는 짝수 그룹이 1개여야 한다는 사실을 알았다. 여기서 잠깐 오해하면 안되는 것이, 저 상황은 i와 j가 다른 그룹에 있어야 성립하므로 애초에 그룹이 1개인 경우는 예외이다. 그룹이 1개면 무조건 YES이다.

이제 짝수 그룹이 1개라면 어떻게 될 지 생각해보자. 이 경우 우리는 i와 j 중 하나가 반드시 짝수 그룹에 있는 경우만 고려해주어도 무방하다. 그렇지 않은 경우 계속 돌다 보면 하나는 짝수 그룹에 도달하기 때문이다.

하나가 짝수 그룹에 있을 경우 빠져나가야 할 방향은 반드시 하나로 정해진다. 그 방향이 만약 서로 가까워지는 방향이라면 답은 당연히 YES이다. 만약 멀어지는 방향이라면 (정확히는, 바로 위 그림처럼 같은 거리를 유지하는 방향) 다른 하나가 다시 짝수 그룹에 도달하게 되고, 방향이 바뀌게 된다(홀수 그룹에서 짝수 그룹으로 들어왔기 때문에, 반대 방향으로만 나갈 수 있다.) 그럼 다시 가까워지는 방향이 되고, 답은 YES가 된다. 따라서 답은 항상 YES이다.

 

위 내용을 모두 구현해주면 된다.

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define COMP(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define sz(x) (ll)x.size()
typedef __int128_t lll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pi;
typedef pair<ll, pi> PP;
const ll Lnf = 2e18;
const ll inf = 1e9;
void solve(){
    ll n; string s; cin>>n>>s;
    bool R=0,B=0;
    for(int i = 0 ; i < n ; i++){
        if(s[i]==s[(i+1)%n]){
            if(s[i]=='R')R=1;
            else B=1;
        }
    }
    if(R+B==2){ cout<<"No\n"; return; }
    if(R+B==0){
        if(n&1)cout<<"Yes\n";
        else cout<<"No\n";
        return;
    }
    if(B){
        for(auto &i : s){
            if(i=='R')i='B';
            else i='R';
        }
    }
    ll cnt = 0;
    for(int i = 0 ; i < n ; i++){
        if(s[i]=='B')break;
        cnt++;
    }
    if(cnt>0){
        s.erase(s.begin(),s.begin()+cnt);
        while(cnt--)s+='R';
    }
    ll cntO = 0, cntE = 0;
    cnt=0;
    for(int i = 0 ; i < n ; i++){
        if(s[i]=='B'){
            if(cnt>0){
                if(cnt&1)cntO++;
                else cntE++;
            }
            cnt=0;
        }
        else cnt++;
    }
    if(cnt>0){
        if(cnt&1)cntO++;
        else cntE++;
    }
    if(cntO+cntE==1){ cout<<"Yes\n"; return; }
    if(cntE!=1){ cout<<"No\n"; return; }
    cout<<"Yes\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

수상할 정도로 대회 환경이 아니면 문제가 잘 풀리는 사람

그날의 복수(?) 성공

이런 애드혹은 좀 재밌는 것 같다.