[THUPC2022 初赛] 挑战

· · 题解

诈骗题毒害人类。/fad

题意

题目传送门：Link to Luogu。

两个人玩一个博弈，每人每轮可以选择把棋子向前移不超过 p_i 格，然后选择是否发起一次挑战，挑战结果是根据所在格子的两个参数 p_i,q_i 随机产生的。根据挑战结果会发生下面事情之一：

  1. 什么都不发生。
  2. 这个人再行动一轮。
  3. 这个人的下一个回合被跳过。

求两人都用最优策略时先手的胜率，误差不超过 10^{-6}。

当然这里说的很糊，具体题面还要去原题仔细阅读。

题解

本来一看到博弈论+概率以为是线性规划啥的，结果是个动态规划的诈骗题。因为本质是诈骗所以题目不算难，题解还是写得清楚一点好，老少皆宜。

考虑自己能否选择挑战的情况：要么可以挑战；要么不能发起挑战；要么就是别人给我送了一轮，则我连续操作两次，根据题意，第一次不能挑战，第二次能挑战。

注意：这里的“可以挑战”不代表“必须挑战”。

于是设一个这样的状态：f_{i,0/1/2} 表示棋子在第 i 格，目前接手的这个人（有代入感地假设是自己）能否挑战的情况为上述三种里的哪一种（0/1/2 依次对应上面说的三种情况），此时这个人的胜率。

发现这样转移大概是 \mathcal O(np) 的还带 3 的常数所以刚好卡在了 10^8 线……

估计完复杂度了，来看怎么转移。倒序枚举 i。先考虑不能挑战的情况，只能向前移动棋子，此时我的最大胜率就应该是对方的最大败率，即：

f_{i,1} \gets \max_j^{p_i} (1-f_{i+j,0})

其中 j 枚举的是我移动多少步，后文和代码的 j 都是这个含义。

然后是第一步不能挑战，然后能挑战的情况，也比较显然（转移方程就是这句话的字面意思）：

f_{i,2} \gets \max_j^{p_i} (f_{i+j,0})

最后看看能挑战吧 =.=，显然能挑战并不代表必须挑战，此时 f_{i,0} 和 f_{i,1} 一样，重点是挑战的情况（这里说的“贡献”指的是对我的胜率的贡献）：

  1. 挑战成功，下一步继续移动，但不能挑战，产生的贡献是下一步移动的胜率（即 f_{i+j,1}）乘上挑战成功的概率。
  2. 挑战平局，下一步是对方，贡献是对方的败率（即 1-f_{i+j,0}）乘上挑战平局概率。
  3. 挑战失败，白给对方一步，贡献是对方连走两步的败率（即 1-f_{i+j,2}）乘上挑战失败的概率。

于是思路很清晰了，考虑成功、平局、失败的概率，因为三者加起来是 1，我们就只算前两个吧。

直接用成功/平局的结局数除以总的结局数 n\times(m+1) 即可，两种情况的结局数如下：

具体还可以看代码理解。

到这里所有的问题都已经解决了，复杂度是 \mathcal O(np)，带有约为 3 的常数因子。可以通过本题。

代码

注意一些小细节即可，比如 j=p_i 的时候是不能挑战的，等等。

#include<bits/stdc++.h>
using namespace std;
const int max_n=100005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

double f[max_n][3];
int n,p[max_n],q[max_n];

inline double P(int n,int m){ // 成功概率
    if(n<=m) return (n+1)/2.0/(m+1);
    return (2*n-m)/2.0/n;
}
inline double Q(int n,int m){ // 平局概率
    return min(n,m)*1.0/n/(m+1);
}
inline double R(int n,int m){ // 失败概率
    return 1-P(n,m)-Q(n,m);
}

signed main(){
    n=read();
    for(register int i=0;i<n;++i)
        p[i]=read();
    for(register int i=0;i<n;++i)
        q[i]=read();
    for(register int i=n-1;i>=0;--i){
        for(register int j=1,up=min(p[i],n-i);j<=up;++j){ // 不能移出界……
            f[i][1]=max(f[i][1],1-f[i+j][0]),
            f[i][2]=max(f[i][2],f[i+j][0]);
            if(j!=p[i])
                f[i][0]=max(f[i][0],max(f[i][1],f[i+j][1]*P(p[i]-j,q[i]+q[i+j])+(1-f[i+j][0])*Q(p[i]-j,q[i]+q[i+j])+(1-f[i+j][2])*R(p[i]-j,q[i]+q[i+j])));
            else
                f[i][0]=max(f[i][0],f[i][1]);
        }
    }
    printf("%.10lf",f[0][0]);
    return 0;
}