yukicoder : No.1682 Unfair Game

確証をもって答えるのしんどそう。
https://yukicoder.me/problems/no/1682

問題

N個のコインがあり、それぞれ投げたときに表が出る確率はP[i]である。
N枚中何枚かコインを選ぶことを考える。
それらをまとめて投げたとき、表の枚数が奇数になる確率が0.5を超えるような選び方は何通りか。

解法

P[i]=0.5のコインがある場合、そのコインを最後に投げると表の枚数が偶奇になる確率は半々になるので、そのようなコインは選べない。
厳密な証明はEditorialに譲るとして、結局各コインについて、表が出る確率が以下のいずれかで決まる。

• P[i]＜0.5となるコインは選んでも選ばなくても良い。それが枚数に及ぼす影響は小さいため。
• P[i]=0.5となるコインは選んではいけない。そのコインを最後に投げると表の枚数が偶奇になる確率は半々になる。
• P[i]＞0.5となるコインは奇数枚だけ選ぶ。

int N;
int A,B;
const ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		if(x<50) A++;
		if(x>50) B++;
	}
	
	if(B==0) {
		cout<<0<<endl;
	}
	else {
		ll ret=1;
		FOR(i,A+B-1) ret=ret*2%mo;
		cout<<ret<<endl;
	}
	
}

まとめ

勘で法則を求めることはできても、ちゃんと式変形して証明するのはちょっとしんどそう。