2016-03-06
TCO15 Algorithm Round 2B
https://competitiveprogramming.info/topcoder/srm/round/16500/div/1
Easy (250) Bitwisdom
問題
- Nビットの文字列が与えられる
- 1回の操作で、先頭または末尾から連続するビットを反転できる
- 各ビットの生起確率が与えられる
- 全ビットを0にするための操作回数の期待値を求める
方針
- 適当にメモ化する
- 死
- (終了後)
- ビットが異なっている部分を反転する必要があるので、それを数える
- ただし全ビットが1のときは反転部分がないので、その確率も期待値に追加する
- https://github.com/firewood/topcoder/blob/master/tco_2015/Bitwisdom.cpp
結果
--- 0pt 323rd/554 rating 1379 -> 1325 (-54)
翌日すごく面倒なDPを書いたが、正解は出力するものの意味不明なので書き直した。
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20160306
リンク元
- 28 https://topcoder-g-hatena-ne-jp.jag-icpc.org/
- 22 https://topcoder-g-hatena-ne-jp.jag-icpc.org/
- 15 https://www.google.co.jp/
- 3 https://topcoder-g-hatena-ne-jp.jag-icpc.org
- 1 https://topcoder-g-hatena-ne-jp.jag-icpc.org/?sid=20b95348f45cd373
- 1 https://topcoder-g-hatena-ne-jp.jag-icpc.org/calendar?date=2015-06-30
- 1 https://www.google.com.eg/
- 1 https://topcoder-g-hatena-ne-jp.jag-icpc.org/calendar?date=2015-07-06
- 1 https://www.google.com/
- 1 https://github.com/