天下一プログラマーコンテスト2016 予選B : C - 天下一プログラマーコンテスト1999

不参加でした。出てたらTシャツ狙えてたのかなぁ…？
http://tenka1-2016-qualb.contest.atcoder.jp/tasks/tenka1_2016_qualB_c

問題

N人が総当たりで互いに試合を行った記録がある。
別の人が同じ試合を記録した際、確率pで正しい記録を、(1-p)で誤った記録を付けていたことが分かった。
また、その記録は独立であり、「AがBに勝った」と「BがAに負けた」はそれぞれ独立に(1-p)の確率で誤っている。

総当たりの結果、勝ち数の多い順に順位を付けるとする。
勝ち数が同着の場合、元の番号が若い方が上の順位である。
別の人の(一部誤っている可能性のある)記録における順位が、元の正しい試合と一致する確率を求めよ。

解法

記録が独立であるということから、各人の勝ち数とその確率は、他人の勝ち負けと関係なく決まる。
よってまず各人の勝ち数とその確率を求めよう。これはDPでも組み合わせ計算でも求められる。
f(a,b) := 誤った記録において、a番の人がb勝する確率

順位付は推移律が成り立つので、最下位から順に以下を求めて行けば良い。
dp(i,w) := 誤った記録において、下からi番までの人の順位が正しく、かつi番の人がw勝である確率

A(x) := 下からx番目の人の番号 として、以下のDPで解くことができる。
dp(i+1,w) += f(A(i+1),w) * dp(i,x)
ただしxはwより小さいか、またはw=xかつA(i)＞A(i+1)である。

int N;
int A[32][32];
double P;

int win[32];
double dp[32][32];
double from[32],to[32];
double dpwin[32][32];

void solve() {
	int i,j,k,l,r,x,y; string s; char c;
	
	cin>>N>>x>>c>>y;
	P=x*1.0/y;
	vector<pair<int,int>> V;
	FOR(y,N) {
		FOR(x,N) cin>>A[y][x], win[y]+=A[y][x];
		V.push_back({-win[y],y});
	}
	sort(ALL(V));
	reverse(ALL(V));
	
	FOR(y,N) {
		ZERO(from);
		from[0]=1;
		FOR(x,N) {
			cin>>A[y][x];
			win[y]+=A[y][x];
			if(y==x) continue;
			ZERO(to);
			FOR(i,30) if(from[i]) {
				if(A[y][x]==1) to[i+1]+=from[i]*P,to[i]+=from[i]*(1-P);
				if(A[y][x]==0) to[i+1]+=from[i]*(1-P),to[i]+=from[i]*P;
			}
			swap(from,to);
		}
		FOR(x,N) dp[y][x]=from[x];
	}
	
	FOR(x,N) dpwin[V.front().second][x]=dp[V.front().second][x];
	FOR(i,N-1) {
		int pre=V[i].second;
		int cur=V[i+1].second;
		
		FOR(x,N) FOR(y,N) {
			if(x>y) continue;
			if(x==y && cur>pre) continue;
			dpwin[cur][y] += dpwin[pre][x] * dp[cur][y];
		}
	}
	
	double tot=0;
	FOR(i,N+1) tot+=dpwin[V.back().second][i];
	_P("%.12lf\n",tot);
	
	
}

まとめ

もう少しNが大きくても良さそうね。