読者です 読者をやめる 読者になる 読者になる

hir180のチラ裏

気が向いたら書きます

印象に残った問題(CF編)

Codeforces 245H 「Queries for Number of Palindromes」

累積和で解くのがよいそうです。

自分は、dp[a][b]=string[a]からstring[b]の部分文字列内に含まれる回文数として、string[a]からstring[b]の部分文字列が回文:

dp[a][b]=dp[a+1][b]+dp[a][b-1]-dp[a+1][b-1]+1

回文ではない:

dp[a][b]=dp[a+1][b]+dp[a][b-1]-dp[a+1][b-1]

と計算しました。

また、

回文のうち、すべての文字が等しくないと、後ろに1文字付け加えた時に回文にならない。すべての文字が等しく、かつ付け加える文字がその等しい文字だったときのみ回文になる。

という事実を使ったところ、TLE→ACになりました。

以下ソースコード↓(AC 2012/11/23)

http://codeforces.com/contest/245/submission/2630461