CF2181J Jinx or Jackpot 题解

P14791 [NERC 2025] Jinx or Jackpot

Link: https://codeforces.com/problemset/problem/2181/J

题目描述

Jack 正在他最喜爱的赌场里，身上有 1000 美元。赌场里除了一台老虎机外一无所有。Jack 知道这家赌场的历史。从前，赌场未来的主人正在散步时，突然看到了一个包含

n

n

n 个整数选项的数组

p

1

,

…

,

p

n

p_1, \\dots, p_n

p1​,…,pn​，每个选项都在 0 到 100 之间。他均匀随机地选取了一个索引

i

i

i (

1

≤

i

≤

n

1 \\le i \\le n

1≤i≤n)，并认为创建一个只有一台老虎机的赌场是个好主意，这台老虎机的中奖概率为

p

i

100

\\dfrac{p_i}{100}

100pi​​。于是他照做了。

Jack 知道主人散步时突然看到的选项数组

p

1

,

…

,

p

n

p_1, \\dots, p_n

p1​,…,pn​，但他不知道主人具体选取了哪个

i

i

i。然而，被选中的索引

i

i

i 是永久固定的；老虎机始终使用相同的

p

i

p_i

pi​，如下所述。

在老虎机上，Jack 可以下注

x

x

x 美元，其中

x

x

x 是一个 非负 整数，然后拉下拉杆。接着：

即使 Jack 下注 0 美元，他也能知道结果是失败还是中奖。

此外，老虎机不太耐用，因此 Jack 最多只能玩

k

k

k 轮。

通过最优策略，找出 Jack 能获得的最大期望 利润。这里的利润定义为 Jack 最终拥有的金额减去他初始的 1000 美元。

当然，Jack 不能下注超过他当前余额的金额。

输入格式

第一行包含两个整数

n

n

n 和

k

k

k (

1

≤

n

≤

100
 

000

1 \\le n \\le 100\\,000

1≤n≤100000；

1

≤

k

≤

30

1 \\le k \\le 30

1≤k≤30) —— 选项数量和轮数限制。第二行包含

n

n

n 个整数

p

1

,

…

,

p

n

p_1, \\dots, p_n

p1​,…,pn​ (

0

≤

p

i

≤

100

0 \\le p_i \\le 100

0≤pi​≤100) —— 选项。

输出格式

输出一个实数 —— Jack 通过最优策略能获得的期望利润。如果你的答案的绝对误差或相对误差不超过

10

−

4

10^{-4}

10−4，即被视为正确。

输入输出样例 #1

输入 #1

2 2
70 30

输出 #1

160

输入输出样例 #2

输入 #2

2 30
30 70

输出 #2

12099716.1778528057038784

输入输出样例 #3

输入 #3

2 5
40 50

输出 #3

0

输入输出样例 #4

输入 #4

6 6
10 20 60 30 40 50

输出 #4

29.40799999999990177457221

输入输出样例 #5

输入 #5

1 5
61

输出 #5

1702.708163199999489734182

Solution

1. 题意

• 玩家游玩一个中奖概率

  p

  p

  p 未知（但是已经知道的是一定在一个数组

  P

  =

  {

  p

  i

  }

  P=\\{p_i\\}

  P={pi​} 里选取，集合元素个数

  n

  =

  card

  (

  P

  )

  n = \\text{card}(P)

  n=card(P) 已知）的老虎机。

• 投入

  x

  x

  x 元后有

  p

  p

  p 的概率返还

  2

  x

  2x

  2x，

  1

  −

  p

  1-p

  1−p 的概率返还

  0

  0

  0。

• 只能玩

  k

  k

  k 轮，求收益的最大期望。

2. 分析

为简明起见，下面的

p

i

p_i

pi​ 全部都是已经归一化后的概率（更符合数学习惯）。

本题描述的模型通常称为部分可观测马尔可夫决策过程，也是强化学习里一种非常经典的探索学习模型。就本提而言，这个“探索”的核心就是根据每次老虎机的结果，在概率层面上逐渐推断系统到底选择了哪一个

p

i

p_i

pi​。

由于目标是最优化期望利润，且收益与下注金额呈线性关系，因此根据线性规划以及期望的线性的性质，最优策略一定是这样一种非常极端主义的策略：在每一轮，要么下注

0

0

0 美元（纯探索/学习）观望一下积累一下经验，要么直接无脑选择 All-in。

由于允许不下注只观望，因此本题环境下，大多数人感性认识上倾向的“投一两块钱试试水”其实是不明智的——这其实很好理解：

• 投进去一块钱试水结果发现赚了——你一定会后悔为何没有把全部身家都押上去；
• 投进去一块钱发现亏了——你同样会后悔为何不投 $0$

回顾一下题意，如果中奖概率是

p

p

p，则有

p

p

p 的概率返回

2

x

2x

2x，

1

−

p

1-p

1−p 概率返回

0

0

0。因此数学期望是

x

(

2

p

−

1

)

x(2p-1)

x(2p−1)。我们不妨把

2

p

−

1

2p-1

2p−1 这个倍率（和投入的钱无关）称为投入产出比或者价值率，记为

V

V

V。

初始时不知道老虎机的胜率到底选择了哪个

p

i

p_i

pi​。在没有任何其他信息的情况下，我们会假设所有

p

i

p_i

pi​ 以相等的概率被选择，均为

1

n

\\dfrac{1}{n}

n1​。

随着游戏的进行，持续得到游戏结果（经验）后，我们就可以根据每个时刻的游戏结果给出这些

p

i

p_i

pi​ 被选择的概率的后验分布，调整自己的判断。笼统地说，如果赢多输少，那么我们会倾向于认为较大的

p

i

p_i

pi​ 被选择的概率大一些；如果输多赢少，那么我们会认为较小的

p

i

p_i

pi​ 更可能被选中。

具体说来，比如我们观测到某个时刻的状态是

w

w

w 胜

l

l

l 负，则

p

i

p_i

pi​ 的后验权重

W

i

W_i

Wi​ 会按照类似于二项分布的方式给出

W

i

(

w

,

l

)

=

p

i

w

⋅

(

1

−

p

i

)

l

W_i(w,l) = p_i^w \\cdot (1-p_i)^l

Wi​(w,l)=piw​⋅(1−pi​)l

注意这里使用的是“权重”一词是因为上面的

W

i

W_i

Wi​ 不满足概率的归一化条件，但是依然能够定量反映“谁更有可能被选中”，一般也会说

p

i

p_i

pi​ 的似然度正比于

W

i

W_i

Wi​。并记后验权重的总和（注意：没有归一化）为

S

(

w

,

l

)

=

∑

j

=

1

n

W

j

(

w

,

l

)

=

∑

j

=

1

n

p

j

w

⋅

(

1

−

p

j

)

l

S(w,l) = \\sum_{j=1}^n W_j(w,l) = \\sum_{j=1}^n p_j^w \\cdot (1-p_j)^l

S(w,l)=j=1∑n​Wj​(w,l)=j=1∑n​pjw​⋅(1−pj​)l

我们设

p

∗

p^*

p∗ 表示的是

w

w

w 胜

l

l

l 负时下一轮中奖的条件概率，也就是贝叶斯后验期望概率，那么再获胜一次后，期望概率更新为后验概率的均值，也就是

p

∗

←

(

∑

j

=

1

n

p

j

⋅

W

j

(

w

,

l

)

)

/

(

∑

j

=

1

n

W

j

(

w

,

l

)

)

p^* \\leftarrow \\Big(\\sum_{j=1}^n p_j \\cdot W_j(w,l) \\Big) \\Big/ \\Big(\\sum_{j=1}^n W_j(w,l) \\Big)

p∗←(j=1∑n​pj​⋅Wj​(w,l))/(j=1∑n​Wj​(w,l))

即

p

∗

←

S

(

w

+

1

,

l

)

S

(

w

,

l

)

p^* \\leftarrow \\dfrac{S(w+1,l)}{S(w,l)}

p∗←S(w,l)S(w+1,l)​

笼统地说，这个

p

∗

p^*

p∗ 反映了 Jake 根据历史结果“更新信念”后，认为下一把能赢的概率。若此值大于或等于

0.5

0.5

0.5，意味着局面对他有利，反之亦然。注意这里的

p

∗

p^*

p∗ 用的是赋值符号，也就是每次循环都会计算出一个新值用于后续计算。

在上面的基础上就可以考虑怎么实施状态转移了。由于我们把获胜和失败的局数

w

,

l

w,l

w,l 作为 dp 的两个状态维度，因此我们从投入产出比

V

(

w

,

l

)

V(w,l)

V(w,l) 入手。我们有两种决策。

学习（不下注，纯观望一下获得一步经验）：

不会改变余额，但是能免费获得一次结果反馈。根据这个结果，得到学习策略下的价值率

V

learn

=

p

∗

⋅

V

(

w

+

1

,

l

)

+

(

1

−

p

∗

)

⋅

V

(

w

,

l

+

1

)

V_{\\text{learn}} = p^* \\cdot V(w+1, l) + (1-p^*)\\cdot V(w,l+1)

Vlearn​=p∗⋅V(w+1,l)+(1−p∗)⋅V(w,l+1)

全押（所有的钱全部投出去）：

破釜沉舟之策，没有退路，一条路走到黑。要么余额翻倍要么余额归零，这也就意味着继续学习的收益已被当前决策覆盖。因此一旦选择全押，那最优做法是连续全押直到游戏结束。期望价值率

V

all-in

=

2

k

−

w

−

l

⋅

(

p

∗

)

k

−

w

−

l

=

2

k

−

w

−

l

⋅

(

S

(

k

−

l

,

l

)

S

(

w

,

l

)

)

k

−

w

−

l

V_{\\text{all-in}} = 2^{k-w-l} \\cdot (p^*)^{k-w-l} = 2^{k-w-l} \\cdot \\left( \\dfrac{S(k-l,l)}{S(w,l)}\\right)^{k-w-l}

Vall-in​=2k−w−l⋅(p∗)k−w−l=2k−w−l⋅(S(w,l)S(k−l,l)​)k−w−l

然后每个状态的最大期望价值率就是上面两个选项中的大者，即

V

(

w

,

l

)

=

max

⁡

(

V

learn

,

V

all-in

)

V(w,l) = \\max(V_{\\text{learn}}, V_{\\text{all-in}})

V(w,l)=max(Vlearn​,Vall-in​)

从后往前不断反着推出前面的最优价值率，直到算出初始状态的最优价值率

V

(

0

,

0

)

V(0,0)

V(0,0)，根据题意，

1000

⋅

(

V

(

0

,

0

)

−

1

)

1000 \\cdot (V(0,0) – 1)

1000⋅(V(0,0)−1) 就是答案。

总体的时间复杂度是

O

(

n

k

2

)

O(nk^2)

O(nk2)。

3. 代码

C#

using System;
using System.Linq;

class P14791
{
static void Solve()
{
var input = Console.In.ReadToEnd().Split();

int n = int.Parse(input[0]);
int k = int.Parse(input[1]);

int[] cnt = new int[101];
for (int i = 0; i < n; i++)
{
int val = int.Parse(input[2 + i]);
cnt[val]++;
}

double[][] powv = new double[101][];
double[][] pow100 = new double[101][];
for (int v = 0; v <= 100; v++)
{
powv[v] = new double[k + 1];
pow100[v] = new double[k + 1];
powv[v][0] = 1.0;
pow100[v][0] = 1.0;
double pv = (double)v;
double p100 = 100.0 – pv;
for (int e = 1; e <= k; e++)
{
powv[v][e] = powv[v][e – 1] * pv;
pow100[v][e] = pow100[v][e – 1] * p100;
}
}

double[][] S = new double[k + 1][];
for (int w = 0; w <= k; w++)
{
S[w] = new double[k + 1];
for (int l = 0; l <= k – w; l++)
{
double total = 0.0;
for (int v = 0; v <= 100; v++)
{
if (cnt[v] != 0)
{
total += cnt[v] * powv[v][w] * pow100[v][l];
}
}
S[w][l] = total;
}
}

double[][] V = new double[k + 1][];
for (int w = 0; w <= k; w++)
{
V[w] = new double[k + 1];
}

for (int r = 0; r <= k; r++)
{
for (int w = 0; w <= k – r; w++)
{
int l = k – r – w;
if (S[w][l] < 1e-9)
{
V[w][l] = 1.0;
continue;
}
if (r == 0)
{
V[w][l] = 1.0;
continue;
}

double p_win = S[w + 1][l] / (100.0 * S[w][l]);
double exp_bet0 = p_win * V[w + 1][l] + (1.0 – p_win) * V[w][l + 1];

double exp_all_in = Math.Pow(2.0, r) * S[w + r][l] / (Math.Pow(100.0, r) * S[w][l]);

V[w][l] = Math.Max(exp_bet0, exp_all_in);
}
}

double ans = 1000.0 * (V[0][0] – 1.0);
Console.WriteLine($"{ans:F20}");
}

static void Main()
{
Solve();
}
}

Python

import sys

def solve() –> None:
input_data = sys.stdin.read().split()
if not input_data:
return
it = iter(input_data)

n = int(next(it))
k = int(next(it))

cnt = [0] * 101
for _ in range(n):
cnt[int(next(it))] += 1

powv = [[1.0] * (k + 1) for _ in range(101)]
pow100 = [[1.0] * (k + 1) for _ in range(101)]
for v in range(101):
pv = float(v)
p100 = 100.0 – pv
for e in range(1, k + 1):
powv[v][e] = powv[v][e–1] * pv
pow100[v][e] = pow100[v][e–1] * p100

S = [[0.0] * (k + 1) for _ in range(k + 1)]
for w in range(k + 1):
for l in range(k + 1 – w):
total = 0.0
for v in range(101):
if cnt[v]:
total += cnt[v] * powv[v][w] * pow100[v][l]
S[w][l] = total

V = [[0.0] * (k + 1) for _ in range(k + 1)]

for r in range(k + 1):
for w in range(k + 1 – r):
l = k – r – w
if S[w][l] < 1e-9:
V[w][l] = 1.0
continue
if r == 0:
V[w][l] = 1.0
continue

p_win = S[w+1][l] / (100.0 * S[w][l])
exp_bet0 = p_win * V[w+1][l] + (1.0 – p_win) * V[w][l+1]

exp_all_in = (2.0**r) * S[w+r][l] / (100.0**r * S[w][l])

V[w][l] = max(exp_bet0, exp_all_in)

ans = 1000.0 * (V[0][0] – 1.0)
print(f"{ans:.20f}")

if __name__ == "__main__":
solve()

4. 轶事

本题用后验分布作为状态进行 dp 的思路是强化学习（Reinforcement Learning）中处理部分可观测马尔可夫决策过程的标准流程。

在强化学习中：

• 本题中的 Jake 称为智能体（Agent）；
• 真实的中奖概率 $p_i$
• 已经观察到的 $(w,l)$
• 每轮决定下注金额 $x$
• 最后的收益 $1000V(0,0)-1000$
• 剩余轮数 $k-w-l$

本题用于 dp 的逆向归纳法，在 RL 中称为价值迭代（Value Iteration）算法。