# 某島

… : "…アッカリ～ン . .. . " .. .
April 1, 2020

## 900 TheKFactor

\begin{align} \sum_{i=1}^{n} a_i &= 1 \newline \ \sum_{i=1}^{j-1} a_i v_i + v_j \sum_{i=j}^{n} a_i &\le z , j = 1, 2, \ldots, n \newline \ \sum_{i=1}^{j} a_i &\le \frac{j}{n} , j = 1, 2, \ldots, n \newline \ a_i &\ge 0 , i = 1, 2, \ldots, n \newline \ \end{align}

\begin{align} \sum_{i=1}^{j-1} x_i v_i + v_j \sum_{i=j}^{n} x_i &\le 1 , j = 1, 2, \ldots, n \newline \ \sum_{i=1}^{j} x_i &\le \sum_{i=1}^n x_i \frac{j}{n} , j = 1, 2, \ldots, n \newline \ x_i &\ge 0 , i = 1, 2, \ldots, n \newline \ \end{align}

const int MOD = 1000000007;
const DB EPS = 1e-9;
const DB OO = 1e20;

inline int sgn(DB x){return x < -EPS ? -1 : x > EPS;}
inline int sgn(DB x, DB y){return sgn(x - y);}

const int N = 50;

struct Simplex {
const static int N = int(100) + 9, M = int(50) + 9;
DB a[N][M];
int n, m;

void init(int _n,int _m) { //a矩陣m行n列
n = _n+1; m = _m+1;
REP(i, n) REP(j, m) a[i][j] = 0;
}
void pivot(int in, int out) {
REP(i, m) if(i!=in) a[out][i] /= -a[out][in]; //重置out約束
a[out][in] = 1/a[out][in];

REP(i, n) if (i!=out && sgn(a[i][in])) { //重新計算其他約束
DB t = a[i][in]; a[i][in] = 0;
REP(j, m) a[i][j] += t*a[out][j];
}
}

DB run() {
while (true) {
int in=0, out=0; DB Min=OO;
REP_1(i, m) if(sgn(a[0][i])>0) {
in=i;
break;
}
if(!in) return 1/a[0][0];
REP_1(i, n) if(sgn(a[i][in])<0&&a[i][0]/-a[i][in]<Min) {
Min=a[i][0]/-a[i][in];
out=i;
}
if(!out){
return 0;
throw ; //unbounded
}
pivot(in, out);
}
}
} S;

class TheKFactor {
public:
double expectedScore(vector <int> values) {
int n = values.size();
S.init(2*n, n);
REP_1(i, n) S.a[0][i] = 1;
REP_1(i, n) {
S.a[i][0] = 1;
REP_1(j, i-1) S.a[i][j] = -values[j-1];
FOR_1(j, i, n) S.a[i][j] = -values[i-1];
}
REP_1(i, n) {
REP_1(j, n) S.a[n+i][j] = (DB)i/n;
REP_1(j, i) S.a[n+i][j] -= 1;
}
return S.run();
}
};