結果

問題 No.599 回文かい
コンテスト
ユーザー @abcde
提出日時 2019-05-03 18:35:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,995 ms / 4,000 ms
コード長 2,694 bytes
コンパイル時間 1,645 ms
コンパイル使用メモリ 169,248 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-31 16:01:27
合計ジャッジ時間 12,085 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

// TODO: 高速化(C++14).
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;
LL DP[10001];

int main() {
    
    // 1. 入力情報取得.
    char ch[10001];
    scanf("%10000s", ch);
    string S = ch;
    // int debug = 0;
    
    // 2. 文字列中央から, DP適用.
    // ex.
    // abacaba なら c からスタート.
    int N = S.size();
    int h = (N - 1) / 2;
    DP[0] = 1;
    // 2-1. N が 偶数の場合.
    if(N % 2 == 0){
        for(int i = 0; i <= h; i++){
            DP[i + 1] = 1;
            // aaabbaaa
            // i = 2 の場合, 
            // 1回目: a と a を比較     -> 等しいので, DP[3] に DP[2] を 加算.
            // 2回目: aa と aa を比較   -> 等しいので, DP[3] に DP[1] を 加算.
            // 3回目: aab と baa を比較 -> 等しくないので, 何もしない.
            for(int j = 0; j <= i; j++){
                // 中央から見て, 左半分, 右半分 の文字列 を比較.
                string lStr = S.substr(h - i, j + 1);
                string rStr = S.substr(h + 1 + i - j, j + 1);
                if(lStr == rStr) DP[i + 1] += DP[i - j], DP[i + 1] %= MOD;
                // debug++;
            }
        }
        printf("%llu\n", DP[h + 1]);
    }
    
    // 2-2. N が 奇数の場合.
    if(N % 2 != 0){
        for(int i = 0; i < h; i++){
            DP[i + 1] = 1;
            // abacaba
            // i = 2 の場合, 
            // 1回目: a と a を比較     -> 等しいので, DP[3] に DP[2] を 加算.
            // 2回目: ab と ba を比較   -> 等しいので, DP[3] に DP[1] を 加算.
            // 3回目: aba と aba を比較 -> 等しいので, DP[3] に DP[0] を 加算.
            for(int j = 0; j <= i; j++){
                // 中央から見て, 左半分, 右半分 の文字列 を比較.
                string lStr = S.substr(h - 1 - i, j + 1);
                string rStr = S.substr(h + 1 + i - j, j + 1);
                if(lStr == rStr) DP[i + 1] += DP[i - j], DP[i + 1] %= MOD;
                // debug++;
            }
        }
        printf("%llu\n", DP[h]);
    }
    
    // 3. 後処理.
    // ex.
    // [入力値]
    // abacaba
    // -> ["abacaba"], ["a", "bacab", "a"], ["a", "b", "aca", "b", "a"], ["aba", "c", "aba"], 
    // ["a", "b", "a", "c", "a", "b", "a"]
    // -> 5 で OK ???.
    // [入力値]
    // aaa ... aaa (10000文字)
    // -> 860192575 で OK ???, debug=12502500, 3798[ms] 程度だったので, ギリギリ と思う.
    // for(int i = 0; i < N; i++) cout << DP[i] << " ";
    // cout << endl;
    // cout << "debug=" << debug << endl;
    return 0;

}
0