Codeforces Round #427 Div. 2 D - Palindromic characteristics

http://codeforces.com/problemset/problem/835/D

問題概要

ある文字列に対して以下のようにk-palindromesが定義される。

    1. 文字列が回文ならば、その文字列は 1-palindrome である
    1. k > 1 のとき、文字列の左半分と右半分が等しく、かつ左半分が (k-1)-palindromeならば、その文字列は k-palindromeである

文字列Sが与えられるので、Sのすべての連続部分文字列においてk-palindromeが何個存在するかを、すべてのkについて求めよ。

|S| <= 5000

解法

i, j (0 <= i <= j < N) について

dp(i, j) = 部分文字列S[i..j]の最大のk

を求める。

dpの中で毎回愚直に回文判定してるとO(|S|^3)とかになるので事前に回文テーブルを作っておく。ある文字Xを中心にしたときに作れる最長の回文を考えると、テーブルはO(|S|^2)で作れる。部分文字列S[i..j]が回文かどうかはi, jの真ん中の点を中心にしたときに作れる回文の長さがi~jの長さを超えているかどうかで判定できる。これで前処理・dpともにO(|S|^2)になって間に合う。

またある文字列が k-palindrome であれば必ず (k-1) palindrome でもあるので、dpで最大のkを求めたら最後に累積和をとって答えが出せる。

この問題ではオーダーに効いてこないので意味ないが、Manacherのアルゴリズムとかいうのを用いると上で作ったような回文テーブルの計算がO(|S|)でできるらしいです。参考:文字列の頭良い感じの線形アルゴリズムたち2 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

感想

本番ではdp部分をループで書こうとしてわけわかんなくなってたけど再帰で書き直したらだいぶすっきりしました。とはいえ「k-palindrome であれば必ず (k-1) palindrome」のところがちゃんとわかってればどっちで書こうと大差ないですね。本番ではわかってなかったので終了でした。

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;


void main() {
    auto S = readln.chomp;
    auto N = S.length.to!int;

    auto P_odd = new int[](N);
    auto P_even = new int[](N);

    foreach (i; 0..N) {
        P_odd[i] = 1;
        for (int j = 1; i - j >= 0 && i + j < N && S[i - j] == S[i + j]; ++j) {
            P_odd[i] += 2;
        }
    }

    foreach (i; 0..N-1) {
        for (int j = 0; i - j >= 0 && i + j + 1 < N && S[i - j] == S[i + j + 1]; ++j) {
            P_even[i] += 2;
        }
    }


    auto mem = new int[][](N, N);
    foreach (i; 0..N) fill(mem[i], -1);

    int dfs(int i, int j) {
        if (mem[i][j] >= 0) return mem[i][j];
        if (i > j) return 0;
        if (i == j) return 1;

        int L = j - i + 1;
        int m = (i + j) / 2;
        int ret;
        
        if (L % 2 == 1) {
            if (P_odd[m] >= L)
                ret = dfs(i, m - 1) + 1;
            else
                ret = 0;
        } else {
            if (P_even[m] >= L)
                ret = dfs(i, m) + 1;
            else
                ret = 0;
        }

        return mem[i][j] = ret;
    }

    
    auto A = new int[](N + 2);
    foreach (i; 0..N) {
        foreach (j; i..N) {
            int ret = dfs(i, j);
            A[0] += 1;
            A[ret + 1] -= 1;
        }
    }

    foreach (i; 0..N) A[i + 1] += A[i];

    A[1..$-1].map!(a => a.to!string).join(" ").writeln;
}