TCO Round2Bに参加。
レートはほぼ変動無し。
Mediumに知見の無いテクが出たのでしょうがないか…。
http://community.topcoder.com/stat?c=problem_statement&pm=13778
問題
01で構成されるビット列がある。
このビット列に対し1回処理を行うと、先頭何ビットかまたは末尾何ビットかを反転できる。
ここでNbitのビット列を考える。
先頭からi bit目はp[i]の確率で1であり、そうでなければ0となる。
確率p[i]が与えられたとき、ビット列を0にするまでの最小処理回数の期待値を求めよ。
解法
ビット列において、隣接するビットが0と1で異なっている場合、
- 10の順なら、その箇所が00となるよう先頭を反転する。
- 01の順なら、その箇所が00となるよう末尾を反転する。
というように1回の処理で1か所異なっている場所を解消できる。
すなわち、隣接ビットが異なる値になる確率p[i]*(1-p[i+1])+(1-p[i])*p[i+1]の和を取ればよい。
また、例外的に全ビットが1の時は、隣接するビットがすべて同じでも全体で1回反転が必要なので、その分も足しこむ。
class Bitwisdom { public: double expectedActions(vector <int> p) { int i; double ret=1; FOR(i,p.size()) ret *= p[i]/100.0; FOR(i,p.size()-1) ret += ((100-p[i])*p[i+1]+p[i]*(100-p[i+1]))/10000.0; return ret; } }
まとめ
わかってしまえば単純なコードだが、本番は長々DPしてしまった。