結果

問題 No.464 PPAP
ユーザー tsutajtsutaj
提出日時 2019-06-14 17:06:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 96 ms / 2,000 ms
コード長 3,197 bytes
コンパイル時間 947 ms
コンパイル使用メモリ 79,980 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-25 14:41:46
合計ジャッジ時間 2,658 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 6 ms
6,940 KB
testcase_08 AC 6 ms
6,944 KB
testcase_09 AC 6 ms
6,944 KB
testcase_10 AC 96 ms
6,940 KB
testcase_11 AC 60 ms
6,944 KB
testcase_12 AC 94 ms
6,940 KB
testcase_13 AC 92 ms
6,944 KB
testcase_14 AC 94 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 91 ms
6,944 KB
testcase_24 AC 91 ms
6,940 KB
testcase_25 AC 92 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;

// Manacher のアルゴリズム
// 各インデックスについて回文半径を線形時間で求める
// ダミー文字を挟むことにより偶数長回文にも対応
template <typename ArrayType, typename ElemType>
struct Manacher {
    ArrayType v;
    ElemType dummy;
    vector<int> rad;

    ArrayType insert_dummy_elem(ArrayType vec, ElemType dummy) {
        int N = vec.size();
        ArrayType res(2*N - 1, dummy);
        for(int i=0; i<N; i++) res[2*i] = vec[i];
        return res;
    }

    void build() {
        int N = v.size(), i, j;
        rad = vector<int>(N);
        for(i=j=0; i<N; ) {
            while(i-j >= 0 and i+j < N and v[i-j] == v[i+j]) j++;
            rad[i] = j;

            int k;
            for(k=1; i-k >= 0 and rad[i]-k > rad[i-k]; k++) rad[i+k] = rad[i-k];

            i += k;
            j = max(0, j-k);
        }
    }

    Manacher(ArrayType v_, ElemType dummy_) :
        v(v_), dummy(dummy_) {
        v = insert_dummy_elem(v, dummy);
        build();
    }

    // idx を中心とする回文半径 (0-indexed)
    int get_rad(int idx) {
        return (rad[2*idx] + 1) / 2;
    }

    // 部分文字列 [l, r) が回文かどうか (0-indexed) 
    bool is_palindrome(int l, int r) {
        if(l == r) return true;
        int idx = l + r - 1, len = r - l;
        return rad[idx] >= len;
    }

    void dump(bool is_string = true) {
        int N = v.size();
        if(is_string) {
            for(int i=0; i<N; i++) fprintf(stderr, "%c%c", v[i], i+1==N?'\n':' ');
        }
        else {
            for(int i=0; i<N; i++) fprintf(stderr, "%d%c", v[i], i+1==N?'\n':' ');
        }
        for(int i=0; i<N; i++) fprintf(stderr, "%d%c", rad[i], i+1==N?'\n':' ');
        int len = (N+1) / 2;
        for(int i=0; i<len; i++) {
            fprintf(stderr, "rad %d: %d\n", i, get_rad(i));
        }
        for(int i=0; i<len; i++) {
            for(int j=i; j<=len; j++) {
                if(!is_palindrome(i, j)) continue;
                fprintf(stderr, "substr: [%d, %d) => Yes\n", i, j);
            }
        }
    }
};


void tiny_test_str() {
    string s; cin >> s;
    char dummy = '$';

    Manacher<string, char> man(s, dummy);
    man.dump();
}

void tiny_test_int() {
    int N; cin >> N;
    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];
    int dummy = 0;

    Manacher< vector<int>, int > man(v, dummy);
    man.dump(false);
}

void yuki_464() {
    string s; cin >> s;
    int N = s.size();
    Manacher<string, char> man(s, '$');

    long long int dp[5010][5] = {};
    dp[0][0] = 1;
    for(int i=0; i<N; i++) {
        for(int j=i+1; j<=N; j++) {
            for(int k=0; k<4; k++) {
                if(k != 2) {
                    if(!man.is_palindrome(i, j)) continue;
                    dp[j][k+1] += dp[i][k];
                }
                else {
                    dp[j][k+1] += dp[i][k];
                }
            }
        }
    }
    cout << dp[N][4] << endl;
}

int main() {
    // tiny_test_str();
    // tiny_test_int();
    yuki_464();
    return 0;
}
0