Computer Game

Ivan plays some computer game. There are \(n\) quests in the game. Each quest can be upgraded once, this increases the reward for its completion. Each quest has \(3\) parameters \(a_i, b_i, p_i\): reward for completing quest before upgrade, reward for completing quest after upgrade (\(a_i<b_i\)) and probability of successful completing the quest.

Each second Ivan can try to complete one quest and he will succeed with probability \(p_i\). In case of success Ivan will get the reward and opportunity to upgrade any one quest (not necessary the one he just completed). In case of failure he gets nothing. Quests do not vanish after completing.

Ivan has \(t\) seconds. He wants to maximize expected value of his total gain after \(t\) seconds. Help him to calculate this value.

\(n\leq 10^5,t\leq 10^{10}\)

题解

这个升级操作看上去很诡异。但是稍加思考我们就能发现，一旦某个quest成功过后，我们的最优策略一定是升级\(p_ib_i\)最大的那个quest然后后面一直尝试完成它就行了。

那么问题来了，第一次成功之前呢？大胆猜想，我们一定重复地尝试完成某个固定的quest（比如说\(p\)最大的那一个）。令\(m=\max_{i=1}^n\{p_ib_i\}\)，有

\[\text{ans}=\max_{i=1}^n\left\{\sum_{j=1}^t(1-p_i)^{j-1}p_i(a_i+(t-j)m)\right\} \]

发现过了样例。化简一下公式，写代码提交

constexpr int N=1e5+10;
int a[N],b[N];
double p[N];

int main(){
    int n=read<int>();
    int64 t=read<int64>();
    double mx=0;
    for(int i=1;i<=n;++i){
        read(a[i]),read(b[i]),scanf("%lf",p+i);
        mx=max(mx,b[i]*p[i]);
    }
    double ans=0;
    for(int i=1;i<=n;++i){
        double sum=(p[i]*(a[i]+t*mx))*(1-pow(1-p[i],t))/p[i];
        sum-=p[i]*mx*(1+(1-p[i]-pow(1-p[i],t))/p[i]-pow(1-p[i],t)*t)/p[i];
        ans=max(ans,sum);
    }
    printf("%.9lf\n",ans);
    return 0;
}

然后Wrong answer on test 105。看看这组hack数据

2 10
1000 1001 0.1
10 1000 0.5

问题出在虽然\(0.1<0.5\)但是\(0.1\times 1000>0.5\times 10\)，也就是“高风险高收益”和“低风险低收益”的抉择。

这下我们普通人类就想不出来一个普适的最优方案了。那么就交给计算机走一步算一步地处理，也就是使用动态规划。

设\(f(i)\)表示剩余\(i\)秒且之前未成功过哪怕一次时的最大期望，则\(f(0)=0\)

\[f(i)=\max_{j=1}^n\{p_j(a_j+(i-1)m)+(1-p_j)f(i-1)\} \]

把转移方程的加法因子按照与\(i,j\)的关系分类得到

\[f(i)=f(i-1)+\max_{j=1}^n\{p_ja_j+p_j(m(i-1)-f(i-1))\} \]

令\(B_j=p_ja_j\)，\(A_j=p_j\)，\(X_i=m(i-1)-f(i-1)\)，则

\[f(i)=f(i-1)+\max_{j=1}^n\{A_jX_i+B_j\} \]

那么维护直线组\(y=A_jx+B_j,j=1,2,\dots,n\)构成的上半平面交，转移的时候二分即可。时间复杂度\(O(t\log n)\)，显然不行。

进一步观察性质，发现因为\(f(i)-f(i-1)\leq m\)，所以\(X_i\)是单调不降的。也就是说，可以把\(f(1),f(2),\dots,f(n)\)划分成若干个连续段，每个连续段内部的\(f(i)\)转移的时候使用的直线（即决策\(j\)）是相同的。

转移一模一样，而使用这个转移的状态又特别多，这让我们联想到矩阵乘法。

\[f(i)=(1-p_j)f(i-1)+p_jm(i-1)+p_ja_j \]

\[\begin{bmatrix} f(i)\\ i\\ 1 \end{bmatrix} = \begin{bmatrix} 1-p_j & p_jm & p_ja_j\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} f(i-1)\\ i-1\\ 1 \end{bmatrix} \]

我们预处理出每条上半平面交上的直线作为最优转移时所要求的\(x\)的范围，然后对每个连续段使用倍增转移。那么决定连续段长度的就是\(X_i\)的变化情况了。

预处理倍增数组以卡常数，时间复杂度\(O(27n\log t)\)。

实现的时候可以不写半平面交（虽然这只是个简单情况），而是用斜率优化的套路转化成\(B_j=xA_j-y\)，然后求下凸包。可能要简单一点，不过没有必要。

constexpr int N=1e5+10;
struct quest{
    int a,b;
    double p;
}Q[N];

struct line{
    double a,b,r;
}L[N];

int build(int n){
    sort(L+1, L+n+1, [](const line& x, const line& y)->bool{
        return x.a!=y.a ? x.a<y.a : x.b>y.b;
    });
    n=unique(L+1, L+n+1, [](const line& x, const line& y)->bool{
        return x.a==y.a;
    })-L-1;
    int t=0;
    L[0]={-1e9,0}; // x=0
    for(int i=1; i<=n; ++i){
        for(; t>=1; --t){
            double x=(L[t-1].b-L[i].b)/(L[i].a-L[t-1].a);
            if(L[i].a*x+L[i].b<L[t].a*x+L[t].b) break;
        }
        L[++t]=L[i];
    }
    return t;
}

using matrix=array<array<double,3>,3>;

matrix operator*(const matrix& a, const matrix& b){
    matrix c={};
    for(int i=0; i<3; ++i)for(int j=0; j<3; ++j)
        for(int k=0; k<3; ++k) c[i][j]+=a[i][k]*b[k][j];
    return c;
}

matrix T[N][34];

int main(){
    int n=read<int>(); int64 t=read<int64>();
    double m=0;
    for(int i=1; i<=n; ++i){
        read(Q[i].a), read(Q[i].b), scanf("%lf",&Q[i].p);
        m=max(m, Q[i].p*Q[i].b);
        L[i]={Q[i].p, Q[i].p*Q[i].a};
    }
    n=build(n);
    for(int i=1; i<n; ++i)
        L[i].r=(L[i].b-L[i+1].b)/(L[i+1].a-L[i].a);
    L[n].r=t*m;
    // for(int i=1; i<=n; ++i)
    //     cerr<<i<<" L="<<L[i].a<<" "<<L[i].b<<" "<<L[i].r<<endl;
    for(int i=1; i<=n; ++i){
        T[i][0]={
            1-L[i].a, L[i].a*m, L[i].b,
            0, 1, 1,
            0, 0, 1
        };
        for(int j=1; (1LL<<j)<=t; ++j)
            T[i][j]=T[i][j-1]*T[i][j-1];
    }
    matrix F={
        0, 0, 0,
        0, 0, 0,
        1, 0, 0
    };
    for(int i=1; i<=n && F[1][0]<t; ++i){
        if(m*F[1][0]-F[0][0]>L[i].r) continue;
        for(int j=floor(log2(t-F[1][0])); j>=0; --j){
            if(F[1][0]+(1LL<<j)>t) continue;
            matrix G=T[i][j]*F;
            if(m*G[1][0]-G[0][0]<=L[i].r) F=G;
        }
        if(F[1][0]<t) F=T[i][0]*F;
    }
    printf("%.9lf\n",F[0][0]);
    return 0;
}