ferinの競プロ帳

競プロについてのメモ

cf #427 div2 D. Palindromic characteristics

問題ページ
Problem - D - Codeforces

問題概要

k-palindromeを以下のように定義する。

  • 文字列の左半分と右半分が空文字列ではなく一致している
  • 左半分と右半分がともに(k-1)-palindromeである

1-palindromeは通常の回文と同様である。
文字列sが与えられる。この文字列に含まれる連続する部分文字列においてk-palindrome(1<=k<=|s|)の数はそれぞれ何個あるか求めろ。

解法

dp[l][r] = (lからrまでの部分文字列で最大のk)とおいたDPを考える。
lからrまでの文字列がk-palindromeである条件はlからrまでの文字列が回文であり、左半分が(k-1)-palindromeであることである。したがって、小さい幅の部分文字列の情報を先に得たいため、小さい幅のものから順番に計算していく。
l = r のときは明らかにdp[l][r] = 1
l = r-1 のときは s[l] = s[r] ならば dp[l][r] = 2、s[l] != s[r] ならば dp[l][r] = 0 となる。
これ以外のときは

  • s[l] != s[r] または dp[l+1][r-1] であれば回文にはなりえないため dp[l][r] = 0
  • それ以外の場合、左半分のdpの値+1が求める値になるため dp[l][r] = dp[l][m] + 1 (ただし m = ceil((l+r)/2) - 1)

となる。これはO(|S|^2)で計算できる。
ここでk-palindromeは(k-1)-palindromeでもあることを利用すると、k-palindromeの数はdp[l][r]の値がk以上の個数であると言える。cnt[k] = (dp[l][r] = kの数) として、後ろから累積和を取ることで、各k-palindromeの数を求めることができる。