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; }