Codeforces 98E Help Shrek and Donkey 纳什均衡

题意

有n+m+1张牌，牌上的数字互不相同且均在[1,n+m+1]中。A有n张牌，B有m张牌，还有一张牌盖在桌上。现在A和B轮流操作，当前操作的那一方有两种操作：

猜盖在桌上的牌是什么，若猜对则直接获胜，猜错则直接输。

猜一张对方的手牌，若猜对则对方需要把该牌扔掉，猜错则没有影响。

假设双方都绝顶聪明，问先手获胜的概率是多少。

n , m ≤ 1000 n,m\le1000 n,m≤1000

分析

想看比较详细的题解的话可以参考sam队长写的博客。

这题难就难在先手有“欺骗”操作，也就是说，先手可以选择猜一张我手中的手牌，若后手认为先手在“欺骗”，则先手会丢失一张手牌；反之后手则会认为这张牌就是盖在桌上的那张，然后直接GG。

首先注意到若无法确定桌上的牌，则先手必然不会去猜桌上的牌。

如果我们把猜对方的手牌称为“指定”，那么这时先手就只剩下两种操作，分别是“欺骗”和“指定”。后手也存在两种决策，分别是相信和不相信。

若先手选择“欺骗”，后手选择“相信”，收益为 1 1 1；

若先手选择“欺骗”，后手选择“不相信”，收益为 1 − f ( m , n − 1 ) 1-f(m,n-1) 1−f(m,n−1)；

若先手选择“指定”，后手选择“相信”，收益为 m m + 1 ( 1 − f ( m − 1 , n ) ) \frac{m}{m+1}(1-f(m-1,n)) m+1m​(1−f(m−1,n))

若先手选择“指定”，后手选择“不相信”，收益为 m m + 1 ( 1 − f ( m − 1 , n ) ) + 1 m + 1 \frac{m}{m+1}(1-f(m-1,n))+\frac{1}{m+1} m+1m​(1−f(m−1,n))+m+11​。

我们设先手选择“指定”的概率为 p p p

那么后手选择“相信”时先手获胜概率为 ( 1 − p ) + m m + 1 ( 1 − f ( m − 1 , n ) ) p (1-p)+\frac{m}{m+1}(1-f(m-1,n))p (1−p)+m+1m​(1−f(m−1,n))p

同理后手选择“不相信”时先手获胜的概率为 ( 1 − f ( m , n − 1 ) ) ( 1 − p ) + ( m m + 1 ( 1 − f ( m − 1 , n ) ) + 1 m + 1 ) p (1-f(m,n-1))(1-p)+(\frac{m}{m+1}(1-f(m-1,n))+\frac{1}{m+1})p (1−f(m,n−1))(1−p)+(m+1m​(1−f(m−1,n))+m+11​)p

由于后手需要让先手获胜的概率尽量小，所以先手获胜的概率就是两者之中的较小值。而先手又要选择一个p好让自己获胜的概率尽量大。

注意到这是两条直线，且一条斜率大于0另一条斜率小于0，那么显然二者的交点即为答案。

时间复杂度 O ( n 2 ) O(n^2) O(n2)。

说实话纳什均衡真很有趣，关于纳什均衡的一些介绍可以看这篇文章。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

const int N=1005;

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

double dp(int n,int m)
{
	if (f[n][m]>0) return f[n][m];
	if (!m) return 1;
	if (!n) return 1.0/(m+1);
	double k1=(1.0-dp(m-1,n))*m/(m+1)-1.0,k2=dp(m,n-1)-dp(m-1,n)*m/(m+1);
	double b1=1,b2=1.0-dp(m,n-1);
	double p=(b2-b1)/(k1-k2);
	return f[n][m]=1.0-p+p*(1.0-dp(m-1,n))*m/(m+1);
}

int main()
{
	scanf("%d%d",&n,&m);
	double ans=dp(n,m);
	printf("%.10lf %.10lf\n",ans,1.0-ans);
	return 0;
}