CF 303E Random Ranking

首先对于浮点数的随机，可以忽略

=

的情况。

如果知道了

x

的排名为

y

，那么就说明除

x

外有

y - 1

个数比

x

小，这说明在对于单个数考虑时我们只关系其他数比这个数大还是小。

那么如果知道了

x

的值

v

，会发现对于每个其他的数都可以知道比这个数小和大的概率，那么应该可以写成一个

p_ix + (1 - p_i)

的形式并卷起来。

不过现在的问题是

v

的值可能是很多样的，这该怎么办？

发现其实

p_i

也是可以表示成带

v

的多项式的，不过会发现

v < l_i, l_i < v < r_i, r_i < v

三种情况的

p_i

是不同的。
于是这启发对

l_{1\sim n}, r_{1\sim n}

保留下来的极小区间

[L, R]

单独求解。

不过这样做在最后会遇到求

E(v^p)(0\le p < n)

这个问题，积分后得到的幂次太大或许精度会很烂，我并没有尝试过。

此时考虑另外一个想法，不去考虑分析

v

的具体求值，而是只当作

v

在这个区间

(L, R)

里。
不过这就有问题了，如果一个数的值

< L

或者

> R

肯定是好算的，但是如果这个数的值也在

(L, R)

内怎么办？

有以下结论：若有

c

个实数是在同一范围内均匀随机的，那么每一个数在

1\sim c

的排名的概率都是

\frac{1}{c}

。
感性理解一下，因为不用考虑相等的关系，就可以当作是随机一个排列代表这

c

个数的大小关系，就可以得到这个值了。

于是考虑枚举

x

后直接 dp 记

f_{i, x, y}

表示考虑前

i

个数中有

x

个数

< L

，有

y

个数在

(L, R)

之间的方案数。

转移直接暴力枚举这一个数的三种情况即可，可以做到

\mathcal{O}(n^5)

。

要做到更优，可以考虑缺一分治，可以参考这篇题解做到

\mathcal{O}(n^4\log n)

。
有一个想法是通过背包撤销做到

\mathcal{O}(n^4)

，不过因为带除法，精度感觉也并不是很友好。

我的代码是

\mathcal{O}(n^5)

的，听说比较卡常，实际上我把最后求解答案由暴力枚举变成差分就过了。

// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

constexpr double eps = 1e-9;

constexpr int maxn = 80;

int n, m;
int l[maxn], r[maxn], val[maxn * 2];

double low[maxn], eq[maxn], upp[maxn];

double f[maxn][maxn];
double ans[maxn][maxn];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &l[i], &r[i]);
        val[i << 1] = l[i], val[i << 1 | 1] = r[i];
    }
    std::sort(val, val + n * 2);
    m = std::unique(val, val + n * 2) - val;
    
    for (int s = 0; s + 1 < m; s++) {
        const int sl = val[s], sr = val[s + 1];
        for (int i = 0; i < n; i++) {
            if (l[i] <= sl && sr <= r[i]) {
                low[i] = 1.0 * (sl - l[i]) / (r[i] - l[i]);
                eq[i] = 1.0 * (sr - sl) / (r[i] - l[i]);
                upp[i] = 1.0 * (r[i] - sr) / (r[i] - l[i]); 
            } else if (r[i] <= sl) {
                low[i] = 1.0, eq[i] = upp[i] = 0.0;
            } else {
                upp[i] = 1.0, eq[i] = low[i] = 0.0;
            }
        }
        
        for (int u = 0; u < n; u++) {
            if (eq[u] < eps) continue;
            
            for (int x = 0; x < n; x++) {
                for (int y = 0; x + y < n; y++) f[x][y] = 0.0;
            }
            f[0][0] = eq[u];
            
            for (int i = 0, lim = 0; i < n; i++) {
                if (u == i) continue;
                
                lim++;
                if (upp[i] > 1 - eps) continue;
                if (low[i] > 1 - eps) {
                    for (int x = lim; x >= 0; x--) {
                        for (int y = 0; x + y <= lim; y++) {
                            f[x][y] = x ? f[x - 1][y] : 0.0;
                        }
                    }
                    continue;
                }
                
                for (int x = lim; x >= 0; x--) {
                    for (int y = lim - x; y >= 0; y--) {
                        f[x][y] *= upp[i];
                        if (x) f[x][y] += f[x - 1][y] * low[i];
                        if (y) f[x][y] += f[x][y - 1] * eq[i];
                    }
                }
            }
            
            for (int x = 0; x < n; x++) {
                for (int y = 0; x + y < n; y++) {
                    const double prob = f[x][y] / (y + 1);
                    ans[u][x] += prob, x + y + 1 < n && (ans[u][x + y + 1] -= prob, 1);
                }
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        printf("%.10lf ", ans[i][0]);
        for (int j = 1; j < n; j++) {
            printf("%.10lf ", ans[i][j] += ans[i][j - 1]);
        }
        puts("");
    }
    return 0;
}

文章操作

相关推荐

评论

CF 303E Random Ranking