kmjp's blog

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

TopCoder SRM 664 Div2 Hard BearSortsDiv2

わかってしまうとだいぶラク。
http://community.topcoder.com/stat?c=problem_statement&pm=13941

問題

1~Nが順に並んだ数列がある。
ここに対し、問題文で与えられた手段でマージソートを行う。

マージソートはその過程で2値の大小比較を行う。
仮に、この大小比較が実際の数字とは関係なく、ランダムで50%の確率で大/小それぞれを返すとする。

1~NのPermutationが与えられる。
1~Nが順に並んだ数列に対し、上記変則マージソートの結果、入力のPermutationと同じ結果になる確率を求め、その対数を答えよ。

解法

マージソートはその過程で同じ2値の比較は複数回行わない。
よってマージソート過程の2値比較では、50%のうち毎回どちらか最終結果と等しくなる方を引き当てなければならない。

よってマージソートアルゴリズムに沿って2値の比較回数Pを求めたら、log(2^(-P))が解。

class BearSortsDiv2 {
	public:
	
	int dodo(vector<int> VV) {
		if(VV.size()<=1) return 0;
		int i,N=VV.size();
		vector<int> V[2];
		FOR(i,N) V[i<N/2].push_back(VV[i]);
		
		int ret=dodo(V[0])+dodo(V[1]);
		sort(V[0].begin(),V[0].end());
		sort(V[1].begin(),V[1].end());
		int x=0,y=0;
		while(x<V[0].size()&&y<V[1].size()) {
			ret++;
			if(V[0][x]<V[1][y]) x++;
			else y++;
		}
		return ret;
	}
	
	double getProbability(vector <int> seq) {
		int N=seq.size(),x;
		vector<int> V(N,0);
		
		FOR(x,seq.size()) V[seq[x]-1]=x;
		return log(pow(2,-dodo(V)));
	}
}

まとめ

50%じゃないようにしたらもう少し面白かったかも?