kmjp's blog

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

Google Code Jam 2016 Round 2 : B. Red Tape Committee

ラスト15分で実験始めて気が付いて、ラスト10分で実装をはじめ、ラスト6分で通すという綱渡りをしていた。
https://code.google.com/codejam/contest/10224486/dashboard#s=p1

問題

N人の人がいる。
各人がYes/Noの投票をするとき、Yesを投じる確率はP[i]である。

N人中K人を選んで投票させたとき、Yesを投じる人がちょうどK人の半分となる確率の最大値を求めよ。

解法

SmallはK人の選び方を2^N通り列挙し、かつK人中Yesに投じる人を2^K通り総当たりしても間に合う。

その時、どのK人が選ばれたかを見てみるとP[i]の小さい方と大きい方からのみ数人ずつ選ばれることがわかる。
真ん中の人が選ばれたり、飛び飛びに選ばれたりしない。

Largeもこの知見をもとに解くことができる。
小さい方からb人、大きい方からK-b人選ぶケースを総当たりし、うちK/2人yesに投じる確率を求めよう。
bの選び方はK通りで、K/2人yesに投じる確率を求めるDPはO(K^2)なので、全体でO(N*logN + K^3)で解ける。

なぜ確率が両極端な人を選ぶのがいいかを少し考えてみる。
一件確率が0.5に近い人を選ぶのがよさそうだが、そのような人はYes/Noどちらを答えるかわからないので使いにくいともいえる。
むしろYesと答えやすい人とNoと答えやすい人を半々にそろえた方が結果的にYes/Noを均等にしやすい。
実際はP[i]の値にはばらつきがあるので、常に正確に半々が良いとは限らないようだ。

int N,K;
double P[1010];
double from[202];
double to[202];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	FOR(i,N) cin>>P[i];
	sort(P,P+N);
	double ma=0;
	FOR(x,N) {
		ZERO(from);
		ZERO(to);
		from[0]=1;
		
		FOR(i,K) {
			j=(i+x)%N;
			ZERO(to);
			FOR(y,201) if(from[y]) {
				to[y]+=from[y]*(1-P[j]);
				to[y+1]+=from[y]*P[j];
			}
			
			swap(from,to);
		}
		ma=max(ma,from[K/2]);
		
	}
	
	
	_P("Case #%d: %.12lf\n",_loop,ma);
}

まとめ

途中散々O(N^3)位のDPを検討して悩んだけど、最終的にはどうにかなったので良かった。
これ両端取るのがいいのは感覚としてはわかるけど、正確に証明するにはどうしたらいいんだろうな。