100問マラソン 3問目 SRM 664 Div2 Hard: BearSortsDiv2

問題

配列に対しマージソートを適用する．
しかし，そのマージソートは大小比較部分が間違いがあり，数字の大小関係なしに，確率で大小を判定する．
seqという配列が入力として渡されるので，先のマージソートを適用した時，その配列が1,2,...,Nとなるような確率を求め，対数を取って答えよ

制約

1 <= N <= 40

解法

大小比較するごとに50%を選ばないといけないので，大小比較関数が呼び出されるごとに0.5ずつ掛けてlogを取った．

class BearSortsDiv2 {

	public:

	vector<vector<int> > ls;
	double ret;
	bool LESS(int a,int b){
		ret *= 0.5;
		if(ls[a][b] == 1){
			return true;
		}
		else return false;
	}
	double mergeSort(int left,int right,vector<int>& T){
		if(left+1 >= right)return 0;
		int mid = (left+right) / 2;
		mergeSort(left,mid,T);
		mergeSort(mid,right,T);

		int p1 = left,p2 = mid;
		vector<int> merged;
		while(p1 < mid or p2 < right){
			if(p1 == mid){
				merged.push_back(T[p2]);
				p2 += 1;
			}else if(p2 == right){
				merged.push_back(T[p1]);
				p1 += 1;
			}else{
				if(LESS(T[p1],T[p2])){
					merged.push_back(T[p1]);
					p1 += 1;
				}else{
					merged.push_back(T[p2]);
					p2 += 1;
				}
			}
		}
		for(int i=left;i<right;i++){
			T[i] = merged[i-left];
		}
	}

	double getProbability(vector<int> seq) {
		ls.resize(seq.size()+1);
		for(int i=0;i<=seq.size();i++)ls[i].resize(seq.size()+1);

		for(int i=0;i<seq.size();i++){
			for(int j=i+1;j<seq.size();j++){
				ls[seq[i]][seq[j]] = 1;
			}
		}

		ret = 1;
		vector<int> T(seq.size());
		for(int i=0;i<seq.size();i++)
			T[i] = i + 1;

		mergeSort(0,seq.size(),T);

		return log(ret);
	}
};

system test通しておらず．