0298 选择性遗忘
* * * *
拉格朗日计划
* * * *
选择性遗忘

张三和李四正在玩一个记忆游戏,该游戏需要一个由1到10之间的数字组成的随机序列,每轮按顺序叫一个数。

每位玩家都能记住至多5个出现过的数。当被叫到的数存在于某玩家的记忆中时,该玩家就得一分,否则该玩家需将该数加入他的记忆,若记忆已满了,则需先从记忆中去掉一个数再添加。

初始时双方记忆均为空,而移除记忆时双方分别使用如下的不同策略:

张三总是移除最久未被叫到的数,而李四总是移除在记忆中存在最久的数。

记张三的得分为L,李四的得分为R,求50轮后$|L-R|$的期望值,答案四舍五入到八位小数,即x.xxxxxxxx的形式。

本题难度:



解答

用一个字典记录来记录不同的状态,其中字典的键值为$(a,b,d)$,分别表示张三的记忆、李四的记忆、目前的分差,对应的值为该状态的概率。

每次枚举状态和下一个数字,按规则更新记忆并计分即可。

此处唯一的技巧是利用对称性来压缩状态总数,由于数字之间没有区别,因此可以通过重新标记使得张三记忆中的数始终为1,2,3,4,5。

最终结果是$1.76882294$。

注:为便于浮点计算和使用*运算符,以下为Python 3代码。此外,代码中打印了进度信息。

f={((0,0,0,0,0),(0,0,0,0,0),0):1.0}

for t in range(50):
    print("round:",t,"total status:",len(f))
    g={}
    for (a,b,d),v in f.items():
        for x in range(1,11):
            s=0
            if x in a:
                a2=[*a]
                s+=1
            else:
                a2=[*a[1:]]+[x]

            if x in b:
                b2=[i for i in b if i!=x]+[x]
                s-=1
            else:
                b2=[*b[1:]]+[x]

            c,labels=[],{}
            for i in a2+b2:
                if i==0:
                    c.append(0)
                else:
                    if i not in labels:
                        x=len(labels)+1
                        labels[i]=x
                    c.append(labels[i])
            a3,b3,d3=tuple(c[:5]),tuple(c[5:]),d+s
            g[(a3,b3,d3)]=g.get((a3,b3,d3),0)+v/10
    f=g

print(f"{sum(p*abs(d) for (a,b,d),p in f.items()):.8f}")