某岛

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

SRM 682

300 SmilesTheFriendshipUnicorn

给定一个 n = 2000 无向图,求是否存在长度为 4 的简单路径。

500 SuccessfulMerger

给定一个 n 个点 n 条边的连通图,要求通过若干次合并操作将该图缩成高度 <= 2,问至少需要执行多少次合并操作。

900 TheKFactor

给定一个长度为 n 的格子,每个格子有一个收益 \(v_i\)。
你可以从左出发选择移动到某个格子上拿走那个格子的收益,但在某个位置 a 会有一堵墙,当你停留的位置 b > b 时,会最终停留在 b 上。

现在假设墙的概率分布为 \({a_n}\),满足 \( \sum a_i = 1 \) 且 \( \sum_{j=1}^i a_j <= \frac{i}{n}, 1 <= i <= n \)。
求决策的概率分布 \({b_n}\),要求最大化最小得分。

根据博弈论的知识,(参见 TCO 2019 2B 1000, SlightlyBigger
我们可以将原文题表述为线性规划问题,既。。

最小化 \( z \)
满足约束
$$\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}$$

接着转化成标准型,我们仿照 上个题 里的代数技巧,进行代数变换。设 \(x_i z = a_i\),代入第一个等式约束,
原问题既最小化 \( \frac{1}{\sum_{i=1}^n x_i} \),等价于最大化分母,\( \sum_{i=1}^n x_i \)
满足约束
$$\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();
    }
};