从一道赌博概率题说开去(三)

插进来说说我为什么忽然想起写这个问题。在刚刚结束的 ACM ICPC 2013 全球总决赛中,我大闵行理工学院再创佳绩,勇夺金奖第二名,值得祝贺!看看最后的比分榜,发现我们比获得桂冠的圣彼得堡国立信息机械与光学学院少做出一道 Problem B (Hey, Better Bettor) —— 这道题一共只有两支队伍做出来,分别是冠军/东道主和第三名的东京大学。我不是搞 ACM 的,但看到这个题目还是很感兴趣跃跃欲试。原题在这里

这道题实际上说的就是我们前面讨论的问题,不过这次换成了有“良心”的赌场。题目大意就是我们每次还是赌 1 块钱,你的胜率是 \( p\), \( 0\leq p< 50\),可以无限制地玩下去。玩到最后,如果你赢了钱自然都归你;如果你亏了钱,赌场可以返还你一个比例 \( x\%\), \( 0\leq x<100\)。返还没有时间和额度的限制,但是只能返还一次。现在要写一个程序,给定胜率和返还比例(精确到两位小数),要求出在任意策略下赢钱的最大期望。

这道题的比较吓人的地方在于“任意策略”,到底什么策略能够赢钱呢?接着昨天的讨论,由于我们的胜率不到一半,所以只要你开始玩而没有返还,最后手上钱数的期望一定小于最初。鉴于只能返还一次,中间去拿退款然后接着玩肯定是不行的。那实际上就只能是赢了走人,输了退款,唯一的变量就是到底什么时候离场。

我们昨天已经算出,如果拿 \(x\) 块钱来赌,每次赌 1 块钱,赢到 \(b\) 块钱或者输到 \(a\) 块钱离场,那么赢钱的概率
\[
P= \frac {(p/q)^{b-x} -(p/q)^{b-a}}{1 -(p/q)^{b-a}}
\]

由于这道题目中所计算的盈亏的部分,所以开始拿多少钱并不重要,不妨设为 0(反正相当于可以赊欠)。知道了赢钱的概率和输赢离场的条件,只要加在一起就可以计算期望——别忘了输钱的时候还要打个折扣。现在的任务就是求出 \(a\) 和 \(b\) ——暴力搜索吧!

在赛后的讨论中,分析员提到这道题本来评委会以为是中等难度,但没想到几乎成了最难的一道题。由于胜率和返还率给定两位小数,所以最极端的是返还 99.99%,胜率 49.99% 之类的情况。选手需要尝试设置暴力搜索的范围,以便能够处理这类极端情况,在赛场上很可能机时不够而导致做不出。由于题目本身还有时间限制,所以暴力搜索也要逐渐细化以提高运行速度。

我用 python 写了一个程序来算,已经通过了 Online Judge,用时 0.19s:

import sys

def P(p, a, b):
    f = p / (1 - p)
    return (f ** b - f ** (b - a)) / (1 - f ** (b - a))

def BestE(discount, p):
    best = bb = ba = 0
    (alow, ahigh, blow, bhigh) = (-40000, 0, 0, 40000)
    for step in (10000, 1000, 100, 10, 1):
        for a in xrange(alow, ahigh, step):
            for b in xrange(blow, bhigh, step):
                pw = P(p / 100, a, b)
                E = pw * b + ((1 - discount / 100) * (1 - pw)) * a
                if E > best:
                    (best, ba, bb) = (E, a, b)
        (alow, ahigh, blow, bhigh) = (ba-step, min(ba+step, 0), max(bb-step, 0), bb+step)
    return best

for line in sys.stdin:
    discount, p = map(float, line.split())
    print BestE(discount, p)

输出大概是这样的:

$ pypy bettor.py
50 49.85
7.1017845299
0 49.9
0
99.99 49.99
918.243317281

真的是很有意思的题目!明天再来继续谈赌注大小的问题。

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据