CF 303E Random Ranking

· · 题解

cnblogs。

首先对于浮点数的随机，可以忽略 = 的情况。

如果知道了 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;
}