某島

… : "…アッカリ~ン . .. . " .. .
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();
    }
};