結果

問題 No.464 PPAP
ユーザー walkre
提出日時 2017-05-23 10:08:33
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 71 ms / 2,000 ms
コード長 3,069 bytes
コンパイル時間 1,657 ms
コンパイル使用メモリ 173,440 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-19 11:36:49
合計ジャッジ時間 2,550 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

vector<int> manacher(const string& s){
    vector<int> rad(s.size());
    int i=0,j=0;
    while(i<s.size()){
        while(i-j>=0 and i+j<s.size() and s[i-j]==s[i+j]) ++j;
        rad[i]=j;
        int k=1;
        while(i-k>=0 and i+k<s.size() and k+rad[i-k]<j){
            rad[i+k]=rad[i-k];
            ++k;
        }
        i+=k;
        j-=k;
    }
    return rad;
}

//res[i]:=s[i]を中心とするような極大回分の半径.中心を半径に含める.[i-rad[i]+1,i+rad[i]-1]
vector<int> odd_palindrome(const string& s){ return manacher(s); }
//res[i]:=s[i]とs[i+1]の間を中心とするような極大回分の半径.[i-rad[i]+1,i+rad[i]]
vector<int> even_palindrome(const string &s){
    string t("$");
    for(int i=0; i<s.size(); ++i) t+=s[i]+string("$");
    vector<int> tmp=manacher(t),res(s.size());
    for(int i=0; i<s.size(); ++i) res[i]=tmp[(i+1)*2]/2;
    return res;
}

// 0 1 2 3 4
// a b c d e
//012345678910
//$a$b$c$d$e$
// i s s i
//$i$s$s$i$

void solve(){
    string s;
    cin >> s;
    vector<int> op=odd_palindrome(s),ep=even_palindrome(s);
    vector<i64> pp(s.size());
    rep(i,0,s.size()){
        {
            int l1=i-op[i]+1,r1=i+op[i]-1;
            if(l1==0){
                rep(j,r1+1,s.size()){
                    {
                        int l2=j-op[j]+1;
                        if(l2<=r1+1) ++pp[j+j-r1-1];
                    }
                    if(!ep[j]) continue;
                    {
                        int l2=j-ep[j]+1;
                        if(l2<=r1+1) ++pp[j+j-r1];
                    }
                }
            }
        }
        if(!ep[i]) continue;
        {
            int l1=i-ep[i]+1,r1=i+ep[i];
            if(l1==0){
                rep(j,r1+1,s.size()){
                    {
                        int l2=j-op[j]+1;
                        if(l2<=r1+1) ++pp[j+j-r1-1];
                    }
                    if(!ep[j]) continue;
                    {
                        int l2=j-ep[j]+1;
                        if(l2<=r1+1) ++pp[j+j-r1];
                    }
                }
            }
        }
    }

    i64 ans=0;
    rep(i,0,s.size()){
        rep(j,i+1,s.size()){
            if(i+1<j-op[j]+1 and j+op[j]-1==s.size()-1) ans+=pp[i];
            if(i+1<j-ep[j]+1 and ep[j] and j+ep[j]==s.size()-1) ans+=pp[i];
        }
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}
0