2015-11-15
SRM 654
DP |
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必要ないっぽい。
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20151115
リンク元
- 31 https://topcoder-g-hatena-ne-jp.jag-icpc.org/
- 18 https://topcoder-g-hatena-ne-jp.jag-icpc.org/
- 10 https://www.google.co.jp/
- 4 http://t.co/71cbJblEpy
- 3 https://topcoder-g-hatena-ne-jp.jag-icpc.org
- 1 https://www.google.co.in/
- 1 http://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&ved=0CCMQFjAF&url=https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/&ei=Z7tJVseqH8eg2AGKNg&usg=AFQjCNF7OCqzkXGK7X8vh6Y-RjeI_uDApQ
- 1 https://github.com
- 1 https://topcoder-g-hatena-ne-jp.jag-icpc.org/keyword/SRM
- 1 https://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=8&ved=0CE0QFjAHahUKEwiq342qxprJAhWFL6YKHSK8CdM&url=https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20130908/1378642797&usg=AFQjCNEnZ_AuYiQgz_HQ5zCJNgmspiJBNQ&sig2=AdemkftlA4fdhyUqL0s2Mw