Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

Codeforces 258D - Little Elephants and Broken Sorting

問題文 : Little Elephants and Broken Sorting

解法 :

dp[i][j] : 場所i, j の数をA[i], A[j] として, A[i] > A[j] となる確率, とすると,

この配列の初期値はA[i] > A[j] なら 1, A[i] < A[j] 0 となる.

k 回目において,1 / 2 の確率でa[k] 番めの数とb[k] 番目の数が交換されるので,

dp[i][a[k]] = dp[i][b[k]] = 0.5 * (dp[i][a[k]] + dp[i][b[k]])

となる.
また, a[k] と b[k] の位置が変わる確率が0.5 なので, この2 つについてA[a[k]] > A[b[k]] となる確率は0.5 となるので, dp[a[k]][b[k]] = dp[b[k]][a[k]] = 0.5 となる.

このとき, 反転数の期待値は, $ \displaystyle \sum_{i < j} dp[i][j] $ となる.

コード :

#include <cstdio>
#include <cstring>

using namespace std;

double dp[1024][1024];

int main()
{
	int n, m;
	int p[1000], a[1000], b[1000];
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; i++) scanf("%d", p + i);
	for (int i = 0; i < m; i++) scanf("%d %d", a + i, b + i);
	
	for (int i = 0; i < 1024; i++)
		for (int j = 0; j < 1024; j++)
			dp[i][j] = 0;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (p[i] > p[j]) dp[i][j] = 1.0;
	
	for (int x = 0; x < m; x++){
		for (int i = 0; i < n; i++){
			dp[i][a[x] - 1] = dp[i][b[x] - 1] = 0.5 * dp[i][a[x] - 1] + 0.5 * dp[i][b[x] - 1];
			dp[a[x] - 1][i] = 1.0 - dp[i][a[x] - 1];
			dp[b[x] - 1][i] = 1.0 - dp[i][b[x] - 1];
		}
		dp[a[x] - 1][b[x] - 1] = dp[b[x] - 1][a[x] - 1] = 0.5;
	}
	
	double ans = 0;
	
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			ans += dp[i][j];
	
	printf("%.9lf\n", ans);
	
	return (0);
}