Algoogle

Algorithm for Programming Contest

Codeforces 258 D Little Elephant and Broken Sorting

Category: Codeforces Tag: dp, probabilities

Little Elephant and Broken Sorting

問題概要


長さnの数列をm回スワップして昇順にソートしたい(各ステップでスワップする組は決まっている).
しかし各ステップスワップするかどうかは半々の確率である.
m回のステップが終了した時, 数列にある順序が正しくない組の個数の期待値を求めよ.

解法


DP
dp[i][j] := i番目がj番目より大きい確率
として入れ替える場所をa, bとする.
まずa, bの位置を入れ替えるかどうかなので2つの大小関係は1/2の確率でどちらにもなりうる.
またiとa, iとbの大小関係が1/2の確率でそれぞれ入れ替わってiとb, iとaの大小関係になるので
dp[i][a] = dp[i][b] = (dp[i][a] + dp[i][b]) / 2
dp[a][i] = dp[b][i] = (dp[a][i] + dp[b][i]) / 2
となる.
最後に全ての組の確率を足し合わせれば求める期待値になる.

コード


(258D.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

typedef pair<int,int> pii;
int seq[1024];
int n, m;
double dp[1024][1024];

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> seq[i];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = (seq[i] > seq[j]);

    while(m--){
        int a, b; cin >> a >> b;
        a--; b--;
        dp[a][b] = dp[b][a] = .5;
        for(int i = 0; i < n; i++){
            if(i == a or i == b) continue;
            dp[i][a] = dp[i][b] = (dp[i][a]+dp[i][b]) * .5;
            dp[a][i] = dp[b][i] = (dp[a][i]+dp[b][i]) * .5;
        }
    }
    double ans = 0.;
    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            ans += dp[i][j];
    printf("%.8f\n", ans);
    return 0;
}

Comments