hotpepsiの練習帳

TCO15 Algorithm Round 2B

23:14

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を書いたが、正解は出力するものの意味不明なので書き直した。

http://togetter.com/li/837322