hotpepsiの練習帳

SRM 654

DP | 22:27

https://competitiveprogramming.info/topcoder/srm/round/16318/div/1

https://competitiveprogramming.info/topcoder/srm/round/16318/div/2

Div1 Easy (250) SquareScores

問題

• アルファベットと?からなる文字列Sがある
• ?がどの文字になるかの確率が与えられる
• Sから連続した文字を取り出したものを部分文字列とする
• 全て同じ文字からなる部分文字列の総数をスコアとする
• スコアの期待値を求める

方針

• DP
• 文字a-zについてそれぞれ計算する
• 1文字のときの計算は、位置iがcならスコア1.0、?ならスコアp[c]
• n文字はn-1文字からDPで計算できる
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_654/SquareScores.cpp

結果

o-- 138.33pts 134th/350 rating 1454 -> 1504

今年初黄色。DP必要ないっぽい。

http://togetter.com/li/799762