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