POJ 3015 Expected Difference

最小値と最大値の期待値を求めればいい。
たとえば、最初の数を使うことにした場合の数列のパターンは、
である。
なぜなら、全部のパターンから、1番目を使わないパターンを引けばいいからである。
一般化して、i番目の数を使うことにした場合の数列のパターンは、
となる。
期待値なので、これを全体のパターン で割れば、その確率になる。
それをうまいことやれば大丈夫。

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define rep(i,n) for(int i=0;i<(n);i++)
#define tr(it,container) for(typeof(container.begin()) it = container.begin(); \
                                                  it != container.end(); ++it)
#define mp(a,b) make_pair((a),(b))

typedef long long ll;
typedef complex<double> point;

// up right down left
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};

const double EPS = 1e-9;
const int days[]     = {31,28,31,30,31,30,31,31,30,31,30,31};
const int daysleap[] = {31,29,31,30,31,30,31,31,30,31,30,31};

int main(){
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(3);
    while(true){
        int n,m;
        cin >> n >> m;
        if(n==0) break;
        vector<int> A(n);
        rep(i,n) cin >> A[i];

        double k = 1.0*m / n;
        double ret = 0;
        for(int i=0;i<n;i++){
            ret += (A[n-i-1]-A[i]) * k;
            k *= 1.0*(n-m-i)/(n-i-1);
        }
        cout << round(ret*1000) / 1000.0 << endl;
    }
    return 0;
}