kmjp's blog

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

Google Code Jam 2014 Round 1A : C. Proper Shuffle

予選ならともかく、AとはいえRound1でこういうの出してくるか…。
https://code.google.com/codejam/contest/2984486/dashboard#s=p2

問題

初期状態で0~(N-1)の順で並んでいる数列がある。
ここで、数列のソートに2種類のアルゴリズム(問題文参照)を半々の確率で用いる。
片方は(偏りがなく)良いアルゴリズムで、片方は悪いアルゴリズムである。

ソート後の数列を見て、もともと良いアルゴリズムと悪いアルゴリズムどちらを用いたか推測せよ。

解法

悪いソートを行った場合、0~(N-1)の要素がそれぞれどこに行くか計算しておく。
DPで計算するとO(N^3)かかるが、この問題はNの要素が各テストケース固定のため、1回だけ1・2分かけて計算しても問題ない。

良いアルゴリズムなら、各要素は1/Nの等確率で各位置に移動する。
よってそれらをN要素分足すと1となるはずである。

この各要素が悪いアルゴリズムのソート後どの要素に行くかの確率を用いて、ソート後の各要素を足しこんだものをpとする。
pが1に近ければ正しいアルゴリズムと推測できる。
実際のテストケースに適用してみると、0.991<=p<=1.008程度の場合良いアルゴリズムと判定すると、良いケースと悪いケースが半々程度になるようだ。

別解としては、正しいアルゴリズムなら各要素が1/Nで各位置に行くので、加算ではなく掛け合わせて1/N^Nに近いか判定する方法もある。
ただ、こちらはそのまま計算するとアンダーフローするので、全要素を事前にN倍するとか対数を使うといった工夫が必要なようだ。

const int NN=1000;
double P[2][NN][NN];

int N,A[1001];
int nok=0;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	cin>>N;
	double tot=0;
	FOR(i,N) {
		cin>>A[i];
		tot+=P[NN%2][A[i]][i];
	}
	if(tot>=0.993 && tot<=1.008) _P("Case #%d: GOOD\n",_loop);
	else _P("Case #%d: BAD\n",_loop);
	
}

void init() {
	int i,x,y;
	FOR(i,NN) P[0][i][i]=1;
	FOR(i,NN) {
		int cur=i%2,tar=cur^1;
		ZERO(P[tar]);
		FOR(x,NN) FOR(y,NN) {
			if(y!=i) P[tar][x][y]=P[cur][x][y]*(NN-1)/NN+P[cur][x][i]/NN;
			P[tar][x][i]+=P[cur][x][y]/NN;
		}
	}
	/*
	FOR(x,NN) {
		FOR(y,NN) _P("%.5lf ",P[0][x][y]);
		_P("\n");
	}
	*/
}

まとめ

面白い問題だけど、時間に余裕のない予選以外では勘弁してほしい問題。