Qualification Round 2011 D: GoroSort

解法

既に正しい数字は動かさない、という仮定(これは正しいらしい)を置くと、完全順列などの知識を用いてO(N^3+T*N)のメモ化解法がすぐに思いつく。これで小さいテストケースをいくつか試すと法則性が見えてくる。以下はメモ化解法のほう(本番で提出したのは法則性を予想したもの)。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX_N = 1009;
bool vis1[MAX_N];
bool vis2[MAX_N][MAX_N];
bool vis3[MAX_N];
double memo1[MAX_N];
double memo2[MAX_N][MAX_N];
double memo3[MAX_N];

double rec(int, int);
double rec2(int);

double solve(int n){
	if(vis1[n]) return memo1[n];
	if(n == 0 || n == 1){
		vis1[n] = true;
		return memo1[n] = (n==0?0.0:1e100);
	}
	double ret = 1e200;

	for(int k=2; k<=n; k++){
		double p = rec(k, 0), t = 0.0;
		//if(1-p < 1e-8) continue;
		for(int i=1; i<=k; i++){
			t += rec(k,i)*(1.0 + solve(n-i));
		}
		double tmp = (p + t)/(1-p);
		ret = min(ret, tmp);
	}

	vis1[n] = true;
	return memo1[n] = ret;
}

double rec(int n, int k){
	if(vis2[n][k]) return memo2[n][k];
	vis2[n][k] = true;
	return memo2[n][k] = (n==k?1.0/tgamma(k+1):(rec2(n-k)/tgamma(k+1)));
}

double rec2(int n){
	if(vis3[n]) return memo3[n];
	if(n==0 || n==1 || n==2){
		vis3[n] = true;
		return memo3[n] = (n==2?0.5:0.0);
	}
	vis3[n] = true;
	return memo3[n] = (n-1)*(rec2(n-1)/n + rec2(n-2)/n/(n-1));
}

int main(){
	int T;
	scanf("%d",&T);
	for(int c=1; c<=T; c++){
		int N, x, cnt=0;
		scanf("%d",&N);
		for(int i=1; i<=N; i++){
			scanf("%d",&x);
			if(x!=i) cnt++;
		}
		printf("Case #%d: %.9f\n", c,solve(cnt));
	}
	return 0;
}