M_sea

CF98E Help Shrek and Donkey
CodeforcesLuogu分析博弈论好题。首先可以发现,不到最后是不会选择猜的。假设你问了一张牌,对手没有,那...
扫描右侧二维码阅读全文
24
2019/07

CF98E Help Shrek and Donkey

Codeforces

Luogu

分析

博弈论好题。

首先可以发现,不到最后是不会选择猜的。

假设你问了一张牌,对手没有,那么对手就会怀疑这张牌是桌上那张。

考虑这样一种神奇的操作:询问一张自己手上有的牌。这样子对手就会怀疑这张牌是桌上的,然后如果他问了他就输了。我们把这种操作称为欺骗

考虑 DP 。设 $f_{n,m}$ 表示先手有 $n$ 张牌、后手有 $m$ 张牌时,先手的获胜概率。

我们列一个表格,表示在先手如何操作后手如何操作时先手的获胜概率:

先手$\backslash$后手猜测欺骗
猜测$\displaystyle\frac{m}{m+1}(1-f_{m-1,n})$$\displaystyle\frac{1}{m+1}+\frac{m}{m+1}(1-f_{m-1,n})$
欺骗$\displaystyle 1$$\displaystyle 1-f_{m,n-1}$

为了方便,设 $\displaystyle A=\frac{m}{m+1}(1-f_{m-1,n})$ ,$B=1$ ,$\displaystyle C=\frac{1}{m+1}+\frac{m}{m+1}(1-f_{m-1,n})$ ,$D=1-f_{m,n-1}$ 。

双方都会走最优策略,所以会达成混合策略纳什均衡。

假设先手猜测的概率是 $p$ ,欺骗的概率是 $1-p$ ,那么可以解得 $\displaystyle p=\frac{D-B}{A-B-C+D}$ 。

具体解的过程是这样子的:

$$ \displaystyle\begin{aligned} pA+(1-p)B&=pC+(1-p)D\\ pA+B-pB&=pC+D-pD\\ (A-B-C+D)p&=D-B\\ p&=\frac{D-B}{A-B-C+D} \end{aligned} $$

然后就可以直接转移了。

DP 的边界是 $f_{0,m}=\frac{1}{m+1},f_{n,0}=1$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;

int n,m;
double dp[N][N];

inline double dfs(int n,int m) {
    if (!n) return 1.0/(m+1);
    if (!m) return 1.0;
    if (dp[n][m]) return dp[n][m];
    double A=1.0*m/(m+1)*(1.0-dfs(m-1,n)),B=1.0;
    double C=1.0/(m+1)+A,D=1.0-dfs(m,n-1);
    double P=(D-B)/(A-B-C+D);
    return dp[n][m]=P*A+(1-P)*B;
}

int main() {
    n=read(),m=read();
    printf("%.10lf %.10lf\n",dfs(n,m),1-dfs(n,m));
    return 0;
}
最后修改:2019 年 07 月 24 日 07 : 33 PM

发表评论