Codeforces #492 Div1 D. Game

なんだこりゃ。
http://codeforces.com/contest/995/problem/D

問題

N個の0/1のバイナリ値X[i]により値が決まる関数f(X)がある。
初期状態でf(X)の値はすべて与えられている。

この状態で以下のゲームを行う。
初期状態ではX[i]が全て未確定である。
２人のうち片方が等確率でランダムに選択されると、選択された方は未確定の値のいずれか１つを選び、値を確定できる。
f(X)を片方は最大化、片方は最小化するように最適手を取ると、f(X)の期待値はどうなるか。

また、Q個のクエリが与えられ、各クエリではf(X)の値が１か所更新される。
その都度f(X)の値を求めよ。

解法

実はf(X)の期待値は結局全f(X)の平均である。
片方はf(X)を最大化、片方は最小化しようとすると、両者ともf(X)の期待値にもっとも寄与するビットを選択しようとするが、これは結局あるビットが0/1等確率で選択されるのと同じである。
よって適宜平均値を更新するだけでよい。

int N,R;
ll C[1<<18];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>R;
	double sum=0;
	FOR(i,1<<N) {
		cin>>C[i];
		sum+=C[i];
	}
	
	_P("%.12lf\n",sum/(1<<N));
	while(R--) {
		cin>>x>>y;
		sum-=C[x];
		sum+=y;
		C[x]=y;
		_P("%.12lf\n",sum/(1<<N));
	}
	
}

まとめ

Bぐらいで出てもいい問題。