TopCoder SRM 784 : Div1 Medium SpeedingUpBozosort

割と面倒な問題。
https://community.topcoder.com/stat?c=problem_statement&pm=16113

問題

N要素の整数列Aが与えられる。
Bozosortでは以下の手順を取る。

• Aがソート済みか、先頭から順に隣接要素を比較して確認する。
• ソート済みなら終了
• A中の要素を2か所重複可でランダムに選び、その要素を入れ替える、ということをS回行う。
• 先頭に戻る。

Aがソートされるまでにかかる隣接要素の比較回数の期待値を求めよ。

解法

まず途中に登場しうる数列として、Aの並べ替えを列挙し、連番を振っておく。P(i)は番号に対応するAの並べ替え数列とする。
加えて、各P(i)について、隣接要素の比較回数を求めておこう。これをf(i)とする。

各状態から、要素入れ替えをS回行うとどの状態に遷移するか、その確率を求めたい。
しかしP(i)→P(j)の遷移を愚直に求めようとするとO((N!)^2*N^2*S)かかりかねない。ここを高速化しよう。

(1...N)という数列を考え、これをS回遷移させるとどこに行くか、を前処理として行おう。
これで長さNの数列一般について、S回の入れ替えでどの状態に遷移するかわかるようになる。
これはO(S*N!*N^2)なので何とか間に合う。

g(i,j) := P(i)の状態からS回入れ替えを行ってP(j)になる確率
h(i) := P(i)の状態からソート済みの状態に至る比較回数の期待値
とする。

• P(i)=Aの時
• それ以外のとき

とすると、これは連立方程式なので掃き出し法でh(i)を求められる。

int pat;
map<vector<int>,int> M;
vector<int> T[720];
int num[720];

double from[720];
double to[720];

double dp[720][720];

const int MAT=720;
int Gauss(int n,double mat_[MAT][MAT],double v_[MAT],double r[MAT]) {
	int i,j,k;
	double mat[MAT][MAT],v[MAT];
	memmove(mat,mat_,sizeof(mat));
	memmove(v,v_,sizeof(v));
	
	FOR(i,n) {
		if(mat[i][i]==0) {
			for(j=i+1;j<n;j++) if(mat[j][i]) break;
			if(j>=n) return i;
			FOR(k,n) swap(mat[i][k],mat[j][k]);
			swap(v[i],v[j]);
		}
		v[i]/=mat[i][i];
		for(k=n-1;k>=i;k--) mat[i][k]/=mat[i][i];
		for(j=i+1;j<n;j++) {
			v[j]-=v[i]*mat[j][i];
			for(k=n-1;k>=i;k--) mat[j][k]-=mat[i][k]*mat[j][i];
		}
	}
	
	for(i=n-1;i>=0;i--) {
		for(j=n-1;j>i;j--) v[i]-=mat[i][j]*v[j],mat[i][j]=0;
		r[i]=v[i];
	}
	return n;
}

double mat[MAT][MAT];
double v[MAT],r[MAT];

class SpeedingUpBozosort {
	public:
	double expectedComparisons(vector <int> A, int numSwaps) {
		int N=A.size();
		int y,x,i,j;
		
		if(N==1) return 0;
		
		vector<int> B=A;
		sort(ALL(B));
		pat=0;
		M.clear();
		do {
			T[pat]=B;
			M[B]=pat;
			v[pat]=0;
			FOR(i,N-1) {
				v[pat]--;
				if(B[i]>B[i+1]) break;
			}
			pat++;
		} while(next_permutation(ALL(B)));
		
		
		vector<int> W;
		vector<vector<int>> X;
		FOR(i,N) W.push_back(i);
		map<vector<int>,int> D;
		do {
			X.push_back(W);
			D[W]=X.size()-1;
		} while(next_permutation(ALL(W)));
		
		ZERO(from);
		from[0]=1;
		
		vector<int> cand[720];
		FOR(j,X.size()) {
			FOR(y,N) FOR(x,N) {
				swap(X[j][x],X[j][y]);
				cand[j].push_back(D[X[j]]);
				swap(X[j][x],X[j][y]);
			}
		}
		FOR(i,numSwaps) {
			ZERO(to);
			FOR(j,X.size()) FORR(c,cand[j]) to[c]+=from[j]/(N*N);
			swap(from,to);
		}
		
		ZERO(mat);
		mat[0][0]+=-1;
		for(i=1;i<pat;i++) {
			FOR(j,X.size()) {
				vector<int> R(N);
				FOR(x,N) R[X[j][x]]=T[i][x];
				mat[i][M[R]]+=from[j];
			}
			mat[i][i]+=-1;
		}
		Gauss(pat,mat,v,r);
		
		return r[M[A]];
	}
}

まとめ

ステップは多いが、個々の手順はそこまで難しくない。