印象に残った問題（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)
