[ABC257Ex] Dice Sum 2 Solution

更好的阅读体验戳此进入

题面

存在 $n$$n$ 个正六面体骰子，第 $i$$i$ 个骰子六个面的数值分别为 $A_{i,1},A_{i,2},\cdots ,A_{i,6}$$A_{i, 1}, A_{i, 2}, \cdots, A_{i, 6}$，购买第 $i$$i$ 个骰子的花费为 $C_i$$C_i$。你要在其中购买 $k$$k$ 个骰子，以最大化收益的期望。定义收益为将购买的 $k$$k$ 个骰子各扔一遍，其朝上的数的和的平方减去买 $k$$k$ 个骰子花费的总费用。输出模 $998244353$$998244353$ 意义下的收益期望最大值。

Solution

果然难题的尽头是推式子。

首先令买的 $k$$k$ 个骰子为 $A_1,A_2,\cdots ,A_k$$A_1, A_2, \cdots, A_k$，不难根据期望定义列出式子：

然后考虑将中间的 $\sum _{i=1}^k{A}_{i,x_i}$$\sum_{i = 1}^kA_{i, x_i}$ 转化一下，并去掉外面的一堆求和（关于这步，可以考虑钦定一个骰子为 $A$$A$ 时，剩下 $k-1$$k - 1$ 个骰子可以任选，即 $6^{k-1}$$6^{k - 1}$，而钦定两个骰子并钦定顺序之后则为 $6^{k-2}$$6^{k - 2}$），即：

然后将前面的分式带进去并进一步化简：

发现 $i\ne j$$i \neq j$ 难以处理，尝试通过类似容斥的思想，从平方中去除 $i=j$$i = j$ 的部分，化简为：

发现式子中出现了大量的 $\sum _{x_i=1}^6{A}_{i,x_i}$$\sum_{x_i = 1}^6A_{i, x_i}$，考虑令：

然后发现第二项可以转化为：

然后考虑一三项，同样尽量用 $X_i$$X_i$ 转化：

此时若我们令：

则原式转化为：

写的更明显一点，我们就是要求：

显然购买方案一共有 $(\genfrac{}{}{0ex}{}{n}{k})$$n \choose k$ 种，我们可以考虑将每一种购买方案抽象成二维平面中坐标为 $(\sum X,\sum Y)$$(\sum X, \sum Y)$ 的点，记作 $(x,y)$$(x, y)$，那么我们也就是要在若干个点最大化 $x^2+y$$x^2 + y$。

显然我们是需要尽量使 $|x|$$\lvert x \rvert$ 和 $y$$y$ 都大一些，所以最终可能成为答案的点一定在点集组成的上凸包中。所以理论上我们可以通过枚举每个实数斜率，然后以该斜率的直线去切这个凸包，截距最大的即为凸包上的点。这里理论上截距应该是 $-kx+y$$-kx + y$，但是为了便于计算我们可以认为是一条斜率为 $-k$$-k$ 的直线，那么截距即为 $kx+y$$kx + y$，同时注意这里我们只求截距最大值是因为只需要维护上凸包。具体来说就是对于每个 $k$$k$ 找到最大的 $k\sum X+\sum Y$$k \sum X + \sum Y$，显然可以转化为对所有点求一次 $kX+Y$$kX + Y$，然后从中选择前 $k$$k$ 大（注意这里的 $k$$k$ 不是斜率的 $k$$k$，而是买的 $k$$k$ 个骰子）求和即可。

然后这里我们显然不能枚举实数，于是考虑什么时候骰子之间的大小关系会发生变化，考虑存在以下情况，当 $k\to k^{\prime }$$k \rightarrow k'$ 使得 $i,j$$i, j$ 之间顺序变化时显然有以下式子（举个例子，大小关系相反亦可）：

显然对于这两种情况的转折点存在于：

并且此时仅有 $i,j$$i, j$ 之间的大小关系会改变。

所以我们 $O(n^2)$$O(n^2)$ 枚举并预处理，然后遍历一下 $k$$k$，第一次排个序，后面的 $O(1)$$O(1)$ 修改即可，最终复杂度卡在排序上，为 $O(n^2\log n^2)$$O(n^2 \log n^2)$，可以通过。

Tips：实现时为了便于排序，且 $X,Y$$X, Y$ 远小于 long long 的范围，我们可以考虑按照 $(36X,36Y)$$(36X, 36Y)$ 排序，这样就不可能有分数了，然后最后乘一个 $36$$36$ 的逆元即可。

Tips：还有一个我调了很久的细节，就是过程中不能取模，否则大小关系会变化，导致答案错误。

然后按照这个思路实现之后大概是这样：

xxxxxxxxxx
94
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
ll inv36;
28
int N, K;
29
ll C[1100];
30
ll A[1100][10];
31
ll X[1100], Y[1100];
32
struct MyPair{int first, second;};
33
map < ld, basic_string < MyPair > > mp;
34
bitset < 1100 > inAns;
35
ll ansX(0), ansY(0);
36
ll ans(LONG_LONG_MIN);
37
int idx[1100];
38

39
ll qpow(ll a, ll b){
40
    ll ret(1), mul(a);
41
    while(b){
42
        if(b & 1)ret = ret * mul % MOD;
43
        b >>= 1;
44
        mul = mul * mul % MOD;
45
    }return ret;
46
}
47

48
int main(){
49
    inv36 = qpow(36ll, MOD - 2);
50
    N = read(), K = read();
51
    for(int i = 1; i <= N; ++i)C[i] = read(), idx[i] = i;
52
    for(int i = 1; i <= N; ++i){
53
        for(int j = 1; j <= 6; ++j)
54
            A[i][j] = read(),
55
            X[i] += A[i][j], //6Xi
56
            Y[i] += 6 * A[i][j] * A[i][j]; //36Yi
57
        Y[i] -= X[i] * X[i] + 36 * C[i];
58
    }
59
    for(int i = 1; i <= N; ++i)for(int j = i + 1; j <= N; ++j)
60
        mp[(ld)(Y[j] - Y[i]) / (ld)(X[i] - X[j])] += MyPair{i, j};
61
    ld k = mp.begin()->first - 0.1;
62
    sort(idx + 1, idx + N + 1, [=](const int &a, const int &b)->bool{return k * (ld)X[a] + (ld)Y[a] > k * (ld)X[b] + (ld)Y[b];});
63
    for(int i = 1; i <= K; ++i)
64
        ansX += X[idx[i]], ansY += Y[idx[i]], inAns[idx[i]] = true;
65
    ans = max(ans, ansX * ansX + ansY);
66
    for(auto mdf : mp){
67
        for(auto Pair : mdf.second){
68
            int l = Pair.first, r = Pair.second;
69
            if(inAns[l] ^ inAns[r]){
70
                if(!inAns[l] && inAns[r])swap(l, r);
71
                inAns[l] = false, inAns[r] = true;
72
                ansX += -X[l] + X[r], ansY += -Y[l] + Y[r];
73
            }
74
        }ans = max(ans, ansX * ansX + ansY);
75
    }printf("%lld\n", (ans % MOD * inv36 % MOD + MOD) % MOD);
76
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
77
    return 0;
78
}
79

80
template < typename T >
81
inline T read(void){
82
    T ret(0);
83
    int flag(1);
84
    char c = getchar();
85
    while(c != '-' && !isdigit(c))c = getchar();
86
    if(c == '-')flag = -1, c = getchar();
87
    while(isdigit(c)){
88
        ret *= 10;
89
        ret += int(c - '0');
90
        c = getchar();
91
    }
92
    ret *= flag;
93
    return ret;
94
}

看起来没什么问题，但是交上去就会发现错了很多点，感觉可能是精度之类的问题，于是我们考虑去掉所有浮点数相关运算。

首先对于初始的排序，不难想到若将 $k$$k$ 升序，那么我们可以认为初始 $k=-\mathrm{\infty }$$k = -\infty$，则 $Y$$Y$ 对大小关系影响忽略不计，仅比较 $X$$X$ 即可。

然后对于修改之间的排序把式子推一下换成乘法即可。还有个细节就是我们在修改的时候应仅保留一些满足 $X$$X$ 偏序关系的，可以大概理解为保证我们变的这个 $k$$k$ 是单调的，当然这个点我也没有完全弄明白，如果有大佬知道的话欢迎解惑。

Code

xxxxxxxxxx
96
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
ll inv36;
28
int N, K;
29
ll C[1100];
30
ll A[1100][10];
31
ll X[1100], Y[1100];
32
struct Node{
33
    int l, r;
34
    friend const bool operator < (const Node &a, const Node &b){
35
        return (Y[a.r] - Y[a.l]) * (X[b.l] - X[b.r]) < (Y[b.r] - Y[b.l]) * (X[a.l] - X[a.r]);
36
    }
37
};
38
basic_string < Node > mdfs;
39
multimap < ld, pair < int, int > > mp;
40
bitset < 1100 > inAns;
41
ll ansX(0), ansY(0);
42
ll ans(LONG_LONG_MIN);
43
int idx[1100];
44

45
ll qpow(ll a, ll b){
46
    ll ret(1), mul(a);
47
    while(b){
48
        if(b & 1)ret = ret * mul % MOD;
49
        b >>= 1;
50
        mul = mul * mul % MOD;
51
    }return ret;
52
}
53

54
int main(){
55
    // freopen("in.txt", "r", stdin);
56
    inv36 = qpow(36ll, MOD - 2);
57
    N = read(), K = read();
58
    for(int i = 1; i <= N; ++i)C[i] = read(), idx[i] = i;
59
    for(int i = 1; i <= N; ++i){
60
        for(int j = 1; j <= 6; ++j)
61
            A[i][j] = read(),
62
            X[i] += A[i][j], //6Xi
63
            Y[i] += 6 * A[i][j] * A[i][j]; //36Yi
64
        Y[i] -= X[i] * X[i] + 36 * C[i];
65
    }
66
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)if(X[i] < X[j])mdfs += Node{i, j};
67
    sort(mdfs.begin(), mdfs.end());
68
    sort(idx + 1, idx + N + 1, [](const int &a, const int &b)->bool{return X[a] < X[b];});
69
    for(int i = 1; i <= K; ++i)
70
        ansX += X[idx[i]], ansY += Y[idx[i]], inAns[idx[i]] = true;
71
    ans = max(ans, ansX * ansX + ansY);
72
    for(auto mdf : mdfs)
73
        if(inAns[mdf.l] && !inAns[mdf.r])
74
            inAns[mdf.l] = false, inAns[mdf.r] = true,
75
            ansX += -X[mdf.l] + X[mdf.r], ansY += -Y[mdf.l] + Y[mdf.r],
76
            ans = max(ans, ansX * ansX + ansY);
77
    printf("%lld\n", (ans % MOD * inv36 % MOD + MOD) % MOD);
78
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
79
    return 0;
80
}
81

82
template < typename T >
83
inline T read(void){
84
    T ret(0);
85
    int flag(1);
86
    char c = getchar();
87
    while(c != '-' && !isdigit(c))c = getchar();
88
    if(c == '-')flag = -1, c = getchar();
89
    while(isdigit(c)){
90
        ret *= 10;
91
        ret += int(c - '0');
92
        c = getchar();
93
    }
94
    ret *= flag;
95
    return ret;
96
}

UPD

update-2022_12_19 初稿