結果

問題 No.599 回文かい
ユーザー @abcde@abcde
提出日時 2019-05-03 18:35:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,122 ms / 4,000 ms
コード長 2,694 bytes
コンパイル時間 1,490 ms
コンパイル使用メモリ 167,416 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-30 05:50:06
合計ジャッジ時間 12,755 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 3 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 643 ms
4,380 KB
testcase_11 AC 353 ms
4,376 KB
testcase_12 AC 761 ms
4,380 KB
testcase_13 AC 394 ms
4,376 KB
testcase_14 AC 1,231 ms
4,376 KB
testcase_15 AC 1,504 ms
4,376 KB
testcase_16 AC 1,782 ms
4,376 KB
testcase_17 AC 2,122 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
evil_0.txt AC 990 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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