BOJ 8189 - Antisymmetry

문제 링크 : https://www.acmicpc.net/problem/8189

문제 풀이

 일단 문제를 보면 몇 가지 사실들을 알 수 있다. 첫 번째로 답이 가능한 길이는 짝수이다. 좀 더 생각해보면 답이 가능할 조건을 다른 방법으로도 판단할 수 있다고 생각할 수 있다. 예를 들면 반으로 접었을 때 만나는 두 원소의 합이 모두 1일 때 Antisymmetry이다. 

 중요한 것은 1010101010... 과 같은 경우에 답의 스케일이 $O(N^2)$이기 때문에, 답의 개수를 하나하나 구하는 것은 불가능하다고 판단할 수 있으며, 따라서 (어떠한 조건의 ) 문제에서 구하고자 하는 구간의 개수를 한번에 구함으로서 문제를 해결하는 쪽으로 방향을 잡을 수 있다. 

 보통 구간과 같은 경우에는 동일한 시작점 혹은 끝점으로 묶지만, 이번의 경우에는 구하고자 하는 구간의 특성상 가운데 지점을 잡을 수 있다. 이렇게 묶으면 여러가지를 관찰할 수 있다. 특히 위치 $x$를 기준으로 길이 2k가 문제를 만족한다면 $0<i<k$ 인 모든 $i$에 대해서 $x$를 기준으로 길이가 2i인 구간은 문제의 조건을 만족한다. 

 여기까지 관찰 되었으면 문자열에서 팰린드롬의 개수를 구하는 문제가 떠오를만 하다. 그렇다면 자연스럽게 manacher's algorithm이 생각나게 된다. 이를 감안하고 다시 문제의 조건을 확인한다면  특히 위치 $x$를 기준으로 길이 2k인 구간이 문제를 만족할 때 왼쪽 부분의 일부가 만족한다면 대칭인 오른쪽 부분의 일부도 똑같이 문제의 조건을 만족한다는 것을 알 수 있다. (0101) 이 만족하면 (1010) 도 만족한다. 따라서 마나커 알고리즘을 완벽히 똑같이 적용시키면 된다는 것을 알 수 있다. 

코드 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
 
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);
 
struct poi{
    ll val,xx,yy;
};
 
vector<ll> v;
ll n,m;
ll mod=998244353;
string s;
string t;
ll arr[1010101];
ll ans=0;
ll val[1010101];
ll mx,cen;
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll a,b,c,d,i,j,k,p,q;
    cin>>n>>s;
    for(i=1;i<=n;i++){
        arr[i*2-1]=s[i-1]-'0';
    }
    n=2*n-1;
    for(i=2;i<n;i+=2){
        if(i<=mx){
            val[i]=min(val[2*cen-i],mx-i);
        }
        else val[i]=-1;
        //cout<<mx<<' '<<i<<' '<<val[i]<<'\n';
 
        while((arr[i-val[i]-2]+arr[i+val[i]+2])==1&&1<=i-val[i]-2&&i+val[i]+2<=n){
            val[i]+=2;
        }
 
        if(mx<i+val[i]){
            mx=i+val[i];
            cen=i;
        }
        //cout<<i<<' '<<val[i]<<'\n';
        ans+=(val[i]+1)/2;
    }
    cout<<ans;
 
}