kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2015 Round2B Easy Bitwisdom

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してしまった。