Project Euler 298

发表于 分类于 阅读次数： 本文字数： 3.6k 阅读时长 ≈ 3 分钟

Project Euler 298

题目

Selective Amnesia

Larry and Robin play a memory game involving a sequence of random numbers between \(1\) and \(10\), inclusive, that are called out one at a time. Each player can remember up to \(5\) previous numbers. When the called number is in a player’s memory, that player is awarded a point. If it’s not, the player adds the called number to his memory, removing another number if his memory is full.

Both players start with empty memories. Both players always add new missed numbers to their memory but use a different strategy in deciding which number to remove:

Larry’s strategy is to remove the number that hasn’t been called in the longest time.

Robin’s strategy is to remove the number that’s been in the memory the longest time.

Example game:

Turn Called number Larry’s memory Larry’s score Robin’s memory Robin’s score
\(1\) \(1\) \(1\) \(0\) \(1\) \(0\)
\(2\) \(2\) \(1,2\) \(0\) \(1,2\) \(0\)
\(3\) \(4\) \(1,2,4\) \(0\) \(1,2,4\) \(0\)
\(4\) \(6\) \(1,2,4,6\) \(0\) \(1,2,4,6\) \(0\)
\(5\) \(1\) \(1,2,4,6\) \(1\) \(1,2,4,6\) \(1\)
\(6\) \(8\) \(1,2,4,6,8\) \(1\) \(1,2,4,6,8\) \(1\)
\(7\) \(10\) \(1,4,6,8,10\) \(1\) \(2,4,6,8,10\) \(1\)
\(8\) \(2\) \(1,2,6,8,10\) \(1\) \(2,4,6,8,10\) \(2\)
\(9\) \(4\) \(1,2,4,8,10\) \(1\) \(2,4,6,8,10\) \(3\)
\(10\) \(1\) \(1,2,4,8,10\) \(2\) \(1,4,6,8,10\) \(3\)

Denoting Larry’s score by \(L\) and Robin’s score by \(R\), what is the expected value of \(|L-R|\) after \(50\) turns? Give your answer rounded to eight decimal places using the format x.xxxxxxxx .

解决方案

这题使用概率动态规划来解决。

本题的随机过程长度固定为 \(T=50\) 回合，每回合报出的数在 \(\{1,...,M\}(M=10)\) 间独立等概率。两位玩家的记忆容量均为 \(N=5\)，但更新策略不同：

  • Larry：移除“最久没有被报到”的数（LRU）。
  • Robin：移除“在记忆里待得最久”的数（FIFO）。

我们记 Larry 的得分为 \(L\)，Robin 的得分为 \(R\)，目标是计算 \(T\) 回合后 \(\mathbb E[|L-R|].\)

由于策略依赖顺序信息，我们必须把每位玩家的记忆表示为有序序列。

对于 Larry 的记忆：令 \(A=(a_1,\dots,a_p)\) 表示 Larry 当前记忆\((0\le p\le N)\)，并约定：

  • \(a_1\) 是最久没被报到的数
  • \(a_p\) 是最近被报到的数
  • 拼接：\((a_1,\dots,a_p)\circ(x)=(a_1,\dots,a_p,x)\)
  • 删除：若 \(x=a_k\)，则\(A\ominus x=(a_1,\dots,a_{k-1},a_{k+1},\dots,a_p)\)
  • 取尾： $ (A)= \[\begin{cases} (a_2,\dots,a_p),&p\ge 1\\ (),&p=0 \end{cases}\] $

那么 Larry（LRU）的更新可写为

\[ U_L(A,x)= \begin{cases} (A\ominus x)\circ(x), & x\in A\\ A\circ(x), & x\notin A\land|A|<N\\ \mathrm{tail}(A)\circ(x), & x\notin A\land|A|=N. \end{cases} \]

令 \(B=(b_1,\dots,b_q)\) 表示 Robin 当前记忆\((0\le q\le N)\)，并约定：

  • \(b_1\) 是最早进入记忆、因此“驻留时间最长”的数（将被 FIFO 淘汰）
  • 命中时 Robin 不改变顺序

则 Robin（FIFO）的更新可写为

\[ U_R(B,x)= \begin{cases} B, & x\in B,\\ B\circ(x), & x\notin B \land |B|<N,\\ \mathrm{tail}(B)\circ(x), & x\notin B \land |B|=N. \end{cases} \]

令分差 \(D=L-R\)。当报到数字为 \(x\) 时，设\(\Delta(A,B,x)=\mathbf 1[x\in A]-\mathbf 1[x\in B]\in\{-1,0,1\}.\)那么每回合分差更新为$ DD+(A,B,x).$因此我们只需在动态规划过程中追踪记忆状态和当前分差。

如果直接把数字当作 \(\{1,...,10\}\)，状态数会爆炸。但注意：数字本身没有任何区别，策略只依赖“相等/不等”和“是否在记忆里”的结构。

因此我们把当前出现过的数字做规范化重命名：

  • 给当前状态中出现的所有数字依次编号为 \(0,1,...,m-1(m\le 10)\)
  • 编号规则取一个确定性的方式即可，例如：从左到右先扫描 \(A\) 再扫描 \(B\)，某数字第一次出现就赋予下一个新编号

记这个规范化映射为 \(\varphi\)。于是我们把真实状态映射到一个规范状态：\(A',B'=\varphi(A,B)\)。

这一步的意义在于：任意两个仅仅是把 \(\{1,...,M\}\) 重新置换的状态，在规范化后都会落到同一个 \(S\)，从而极大减少状态数。

令 \(f_t(s,d)\) 表示进行了 \(t\) 回合后，处于规范状态 \(s\)，且分差为\(d\)的概率。其中\(0\le t\le T,-d\le t\le d\)。

初始状态为两人记忆为空、分差为 0：\(f_0[S_0][0]=1, S_0=((),()).\)

设当前规范状态为 S=(A,B)\(。定义并集大小\)m=|{A}{B}|.$

那么下一次报到的数字分两类：

  1. 报到一个已出现过的编号 \(x\in\{0,1,\dots,m-1\}\) 每个具体数字概率都是 \(1/M\)，因此这一类一共有 \(m\) 个分支、每个权重 \(1/M\)。

  2. 报到一个完全没出现过的数字（即不在 \(A\) 也不在 \(B\) 中） 这样的数字共有 \(M-m\) 个，总概率为 \((M-m)/10\)。并且它们对后续的影响完全等价，因此我们可以把它们聚合成一个“新编号” \(x=m\) 来处理。

于是对任意 \(x\)（包括 \(\{0,...,m-1\}\) 以及聚合的新编号 \(m\)），定义：

  • 分差增量：\(\Delta=\Delta(A,B,x)\)
  • 更新后的真实序列：\(A' = U_L(A,x), B'=U_R(B,x)\)
  • 更新后的规范状态：\(S'=\varphi(A',B')\)

那么转移可以写成：\(f_{t+1}(S',d+\Delta)\leftarrow f_t(s,d)\cdot \Pr(x).\)

其中\(\Pr(x)=\left\{ \begin{aligned} &\dfrac{1}{M} &&\text{if}\quad 0\le x\le m-1\\ &\dfrac{M-m}{M} &&\text{else} \\ \end{aligned}\right.\)

最终，\(T\) 回合后分差分布为\(\displaystyle{P(D=d)=\sum_{S} f_{T}(s,d)}.\)

所以答案为

\[E[|D|]=\sum_{d=-T}^{T}|d| \cdot\sum_{S} f_{T}[S][d].\]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
from collections import defaultdict
import numpy as np

R = 50                    # 回合数（总共报数 50 次）
SIZE = 2 * R + 1          # 分差 d = L-R 的可能取值范围 [-R, R]，共 2R+1 个
OFF = R                   # 将 d 映射到数组下标：idx = d + OFF，使得 d=0 对应 idx=OFF
M = 10                    # 每回合报数均匀独立地从 {1..10} 选一个
N = 5                     # 两位玩家记忆容量都是 5

# ---------------------------------------------------------
# normalize(A, B)：状态规范化（对称性压缩）
# ---------------------------------------------------------
# 关键观察：
#   真实数字 1..10 本身没有区别，只要保持“是否相等 / 是否在记忆中 / 顺序”即可。
#   因此可以把当前出现过的数字重新命名成 0..m-1（m 为并集大小），以合并等价状态。
#
# 规范化规则（确定性）：
#   先从左到右扫描 A，再从左到右扫描 B。
#   某个数字第一次出现时分配一个新的编号（0,1,2,...），以后都用该编号替代。
#
# 这样任何仅靠“数字重命名置换”不同的状态都会被压到同一个规范状态，从而大幅减少状态数。
def normalize(A, B):
    mp = {}              # 原始数字 -> 规范编号
    A2, B2 = [], []

    # 先扫描 A：按首次出现顺序分配编号
    for x in A:
        if x not in mp:
            mp[x] = len(mp)
        A2.append(mp[x])

    # 再扫描 B：若该数字未出现过则继续分配新编号
    for x in B:
        if x not in mp:
            mp[x] = len(mp)
        B2.append(mp[x])

    # 用 tuple 作为 dict key
    return tuple(A2), tuple(B2)


# ---------------------------------------------------------
# step_state(state, x)：给定当前状态与本回合报到的编号 x，返回新状态与分差增量
# ---------------------------------------------------------
# state = (A, B)
#   A：Larry 的记忆顺序（LRU 顺序）
#      A[0] 最久没被报到（最旧），A[-1] 最近被报到（最新）
#   B：Robin 的记忆顺序（FIFO 顺序）
#      B[0] 最早进入（驻留最久），B[-1] 最近进入
#
# x：本回合报到的“规范编号”
#   - 如果 x < m（m = |A ∪ B|），表示报到的是并集内某个已有数字
#   - 如果 x == m，表示报到了一个“完全没出现过的新数字”（把所有新数字聚合成一类）
#
# delta：本回合分差变化 = (Larry 是否得分) - (Robin 是否得分) ∈ {-1,0,1}
#
# 更新规则：
#   Larry（LRU）：
#     命中：把 x 移到末尾（变成最新）
#     未命中：若满则弹出头部（最旧），再把 x 加到末尾
#   Robin（FIFO）：
#     命中：不改变顺序
#     未命中：若满则弹出头部（最老驻留），再把 x 加到末尾
def step_state(state, x):
    A, B = state

    # 判断命中与否
    hitA = x in A
    hitB = x in B

    # 本回合分差增量：Larry 命中 +1，Robin 命中 -1
    delta = hitA - hitB

    # -------- Larry：LRU 更新 --------
    A2 = list(A)
    if hitA:
        # 命中：把 x 从原位置移除
        A2.remove(x)
    else:
        # 未命中：若满则移除最久没被报到的元素（队头）
        if len(A2) == N:
            A2.pop(0)
    # 无论命中/未命中，最终都把 x 放到末尾（最新）
    A2.append(x)

    # -------- Robin：FIFO 更新 --------
    B2 = list(B)
    if not hitB:
        # 仅未命中时才插入/淘汰
        if len(B2) == N:
            # 淘汰最早进入的元素（队头）
            B2.pop(0)
        B2.append(x)
    # 命中时 B2 不变（不移动）

    # 返回规范化后的新状态 + 分差增量
    return normalize(A2, B2), delta


# =========================================================
# 概率动态规划定义
# =========================================================
# f[state] 是一个长度 SIZE 的数组 dist
# dist[OFF + d] 表示：到当前回合结束时，处于该规范状态 state 且分差 D = d 的概率
#
# 初始：回合 0，双方记忆为空，分差为 0，概率 1
f = defaultdict(lambda: np.zeros(SIZE, dtype=np.float64))
f[((), ())][OFF] = 1.0


# =========================================================
# 进行 R 回合转移
# =========================================================
for _ in range(R):
    nf = defaultdict(lambda: np.zeros(SIZE, dtype=np.float64))

    # 遍历所有当前可达状态
    for state, dist in f.items():
        A, B = state

        # m = 当前并集大小 |A ∪ B|
        # 在规范状态下，出现过的编号恰好是 0..m-1
        m = len(set(A + B))

        # ----------------------------------------------
        # 情况 1：报到的是并集内某个已有编号 x ∈ [0..m-1]
        # ----------------------------------------------
        # 原问题每个真实数字概率都是 1/M。
        # 对于规范状态中每个已有编号 x，都对应一个具体真实数字，因此每个分支概率都是 1/M。
        for x in range(m):
            ns, delta = step_state(state, x)
            w = 1.0 / M
            arr = nf[ns]

            # 把 dist 按 delta 平移后累加到 arr
            # 用 numpy 切片完成“整体平移”，避免逐 d 循环
            if delta == 0:
                arr += dist * w
            elif delta == 1:
                # d -> d+1，对应数组右移 1
                arr[1:] += dist[:-1] * w
            else:  # delta == -1
                # d -> d-1，对应数组左移 1
                arr[:-1] += dist[1:] * w

        # ----------------------------------------------
        # 情况 2：报到的是“全新数字”（不在 A ∪ B 中）
        # ----------------------------------------------
        # 这样的真实数字有 (M - m) 个，总概率 (M-m)/M。
        # 它们完全对称，因此可以聚合成一个分支：用 x = m 代表“新编号”。
        if m < M:
            x = m
            ns, delta = step_state(state, x)
            w = (M - m) / M
            arr = nf[ns]

            if delta == 0:
                arr += dist * w
            elif delta == 1:
                arr[1:] += dist[:-1] * w
            else:
                arr[:-1] += dist[1:] * w

    f = nf


# =========================================================
# 汇总：把所有状态的分差分布加起来，然后算 E[|D|]
# =========================================================
total = np.zeros(SIZE, dtype=np.float64)
for dist in f.values():
    total += dist

# 下标 0..SIZE-1 对应的分差是 -R..R
d_vals = np.arange(-R, R + 1)

# 期望：sum |d| * P(D=d)
ans = float(np.sum(np.abs(d_vals) * total))

# 按题目要求输出 8 位小数
print(f"{ans:.8f}")