TopCoder Open 2015のRound2の2回目
朝6時開始に寝坊して間に合わなかったのだけど、開始が1時間遅れたので参加できた(?)
残念ながら例のごとく1問も解けず
323位, 0点, +0/-0 challenge
Volatility: 201->192
Round2の3回目はオンサイト(ドワンゴ)でやるっぽいのかな?appirio.co.jp
250: Bitwisdom
\(N\)桁のビット列のそれぞれのビットについてビットが\(1\)になる確率\(p\)が与えられる
ある位置から左右いずれかすべてのビットを反転させるという操作を行える時に、すべてのビットが\(0\)になるまでの最小回数の期待値を答える
\(01\)や\(10\)のようにビットが\(0\)か\(1\)のどちらかからどちらかへ変化した時だけ必要な回数が増える
期待値の線形性よりそれぞれの位置で\(01\)と\(10\)になる確率を足し合わせればよい
ただしビット列すべてが\(1\)になる場合があるので、その確率を足す(\(1\)回の操作ですべて\(0\)にできる)
# -*- coding: utf-8 -*- import math,string,itertools,fractions,heapq,collections,re,array,bisect,operator class Bitwisdom: def expectedActions(self, p): p = map(lambda x: x/ 100.0, p) result = 0 for i in xrange(len(p) - 1): result += (1 - p[i]) * p[i + 1] + p[i] * (1 - p[i + 1]) return result + reduce(operator.mul, p)