Google Code Jam 2013 Round 1A : C. Good Luck

ようやく1AのCも解けた。
本番はsmall1しか解けなかったけど、ようやくsmall2も解けた。
https://code.google.com/codejam/contest/2418487/dashboard#s=p2

問題

2～Mまでの整数を重複可でN個ランダムに選択した数値群をAとする。
この選択した数値群に対し、各数値を1/2の確率で選択したものの積をとる、という処理をK回繰り返す。
K個の積が与えられたとき、元のAを答える。
ただし、全て当てる必要はなく、R回の試行でsmall1・small2それぞれ決まった回数以上正解すればよい。

解法(small1)

small1はN=3、M=5、K=7で、R=100回中50回当てればよい。
N=3と少ないので、222～555の全パターン20通りのAに対し、K個の積を実現できるものを答えればよい。
N=3・K=7なので、K個の積でN個の要素をそれぞれ選択する場合・しない場合の2^N通りをほぼ網羅できているので、大体これで絞れる。

解法(small2)

small2では、M=8、N=12、K=12、R=8000回中1120回当てればよい。
以下はEditorialを参考に回答。
まず、M=8・N=12の時のAのパターンは一見M^(N-1)通りあるように見えるが、順序を無視すると通りと意外と少ない。

そこでまず、事前処理としてこの18574通りがそれぞれM^(N-1)通り中に登場する確率P(A)を求める。
また、Aにおいて各数値を1/2で選択したときの積pの発生確率P(p|A)を求める。こちらは2^12通り。
18574*(2^12)通りはなかなか大きな数値だが、手元の環境では22秒で完了した。

さてここから、R回の試行を処理していく。
K個の積p[0]～p[K-1]が与えられるので、P(A)*P(p[0]|A)*P(p[1]|A)*…*P(p[K-1]|A)が最大となるようなAを答えればよい。
手元の環境ではR=100個あたりで1秒程度かかったので、前処理と合わせて100秒かかった。

ll R,N,M,K;
vector<pair<ll,map<ll,int> > > C;

void dfs(int L,ll V) {
	if(L==N) {
		map<ll,int> TM;
		
		int num[10];
		ZERO(num);
		ll v=V;
		while(v) {
			num[v%10]++;
			v/=10;
		}
		ll tp=1;
		for(int i=2;i<=M;i++) while(num[i]>1) tp*=num[i]--;
		TM[0]=tp;
		
		for(int mask=0;mask<(1<<N);mask++) {
			ll t=1;
			ll v=V;
			for(int i=0;i<N;i++) {
				if(mask&(1<<i)) t *= v%10;
				v /= 10;
			}
			TM[t]++;
		}
		
		C.push_back(make_pair(V,TM));
		return;
	}
	
	for(int i=max(2,(int)(V%10));i<=M;i++) dfs(L+1,V*10+i);
}


void solve2(vector<ll>& V) {
	int i,x;
	ll mv=0;
	double ma=0;
	vector<ll> c;
	
	FOR(i,C.size()) {
		double sc=1.0/C[i].second[0];
		FOR(x,V.size()) {
			ll tv=V[x];
			if(C[i].second.find(tv)==C[i].second.end()) {
				sc=0;
				break;
			}
			sc *= C[i].second[tv];
		}
		
		if(sc>ma) {
			ma=sc;
			mv=C[i].first;
		}
	}
	_P("%lld\n",mv);
}

void solve(int _loop) {
	int i,j,x,y,ne=0;
	
	_PE("Case #%d:\n",_loop);
	
	cin >> R >> N >> M >> K;
	C.clear();
	dfs(0,0);
	
	FOR(y,R) {
		_E("%d\n",y);
		vector<ll> V;
		FOR(x,K) V.push_back(GETi());
		sort(V.begin(),V.end());
		solve2(V);
	}
	
}

まとめ

GCJでも珍しい一定数以上の正答率を求める問題。
今回は予選で２種類のLargeを用意したり、今回は２種類のSmallを用意したり問題のバリエーションが広いな。