[BOJ 15770] QueryreuQ

https://www.acmicpc.net/problem/15770

15770번: QueryreuQ

Tag : dynamic programming

 

문제요약

 

이 두가지 연산을 Q개 처리하면서 매 연산마다 현재 S의 부분 문자열 중 팰린드롬의 개수를 출력하라.

 

풀이

$d{p}_{l,r}=[s[l,r]$는 팰린드롬$]$이라 정의하고 매 쿼리마다 $1\le i\le S.size$인 i에 대해

$d{p}_{i,S.size}$를 모두 갱신해주면 된다.

 

Q=10000인데 $O(Q^2)$풀이를 짜는 것은 찜찜했으나 일단 믿음으로 짰다.

 

일단 첫 제출부터 한시간쯤 TLE에서 빠져나오지 못했다.

이만큼 했으면 할만큼 했다. 하고 포기하고 싶었다....

매우 상수가 작은 $O({10}^8)$이면 돌아갈만하다고 생각했는데....

 

1. fastio : 어림도 없었다 

2. 변수 할당 횟수를 줄이자! : 역시나 어림도 없다

3. gcc flag를 잘쓰고 simd 박을 때나 쓸법한 헤더를 불러서 컴파일러 최적화를 노리자 : 어림도 없지 컽

4. 혹시나...하고 clang 제출 -> 컽

5. 캐시히트를 잘 맞춰보자 : 드디어 AC ( 180ms )

 

캐시히트로 인해 TLE가 180ms가 됐다... 이정도로 극단적인 차이는 처음 겪어서 놀랐다.

dp를 갱신할 때 r은 고정이고 l이 가변적이기 때문에 $d{p}_{r,l}$의 형태로 테이블을 잡는 것이 

캐시히트에 훨씬 좋은 배치였다.

 

1등을 제외한 모두가 나와 비슷한 시간으로 통과했는데 

0ms로 통과한 1등분은 어떤 시간복잡도를 짰는지 매우 궁금하다. 

그나마 빠른 분도 memset 또는 fill을 잘 활용해서 커팅한 듯하다.

$O(Q^2)$을 정해로 두고 티어가 매겨진 듯한데 제한을 바꾸거나하면 좋겠다..

 

코드가 추한 점 이해바란다.

 

시간복잡도 : $O(Q^2)$

 

전체코드

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include "immintrin.h"

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
char O[2000000],*d=O;
int z[36];char *c=(char*)mmap((void*)fstat(0,(struct stat*)z),z[12],1,2,0,0);
int dp[10001][10001];
char v[10101];int sz=0,i,l,r,chk;
ll ans=0;

int main(){
//    ios::sync_with_stdio(0);cin.tie(0);
    
    auto P=[&](ll x)->void{
        char t[16],*q=t;
        do *q++=x%10|48; while(x/=10);
        do *d++=*--q; while(q!=t);
        *d++=32;
    };
    int Q=0;do Q=Q*10+*c-'0';while(*++c>='0');++c;
    for(;Q--;){
        char p=*c++;
        if(p=='-'){
            p=v[sz-1];dp[sz-1][sz-1]=0;ans--;
            for(i=2;i<=sz;i++){
                l=sz-i;
                r=sz-1;
                ans-=dp[r][l];
                dp[r][l]=0;
            }
            sz--;
        }else{
            v[sz++]=p;
            dp[sz-1][sz-1]=1;ans++;
            for(i=2;i<=sz;i++){
                l=sz-i;
                r=sz-1;
                chk=(l+1>r-1 || dp[r-1][l+1]) && v[l]==v[r];
                dp[r][l]=chk;
                ans+=chk;
            }
        }
        P(ans);
    }
    write(1,O,d-O);
}