hotpepsiの練習帳

SRM 607

DP, palindrome | 01:32

Div1 Easy (250) PalindromicSubstringsDiv1

問題

• a-zと?からなる文字列が与えられる
• ?はa-zのどれかに置換される
• 左右対称な部分文字列の個数の期待値を求める

方針

• O(N^3)でがんばって計算
• Challenge Succeeded
• (終了後)
• 奇数と偶数で、1つずつ左右に幅を広げながら数えるとO(N^2)
• 左右のどちらかが?のとき、確率が1/26になるが、1個だけのときは必ず左右対称
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_607/PalindromicSubstringsDiv1.cpp

結果

x-- -1 -25pt 700th/719 rating 1405 -> 1242 (-163)

単純だけど思いつかなかった。

http://togetter.com/li/624676