六月算法竞赛选题——概率与期望（一）

[[ slider_text ]]

[[ item.c ]]

六月算法竞赛选题——概率与期望（一）

发布时间 2025-06-09 作者：zhangminchen 来源：算法小站

期望dp

## 期望dp
### 2022 metacamp程序设计大赛 3
**[吃啥](https://pintia.cn/problem-sets/1547474014070099968/exam/problems/type/7?problemSetProblemId=1556536449766744065)**
**问题描述**
小M有两个队友小A小B，平时小A小B每天都会去外面吃，并且试图拉小M也去，但是小M习惯吃食堂
如果小M和队友一起去，有时候需要承担打车的费用

现在小M有$$T$$元的晚餐预算，需要度过未来的$$n$$天，第$$i$$天有`2`种决策
1.在食堂吃，小M获得$$a_i$$满意度，同时花去$$b_i$$元
2.和小A小B出去吃，小M获得$$c_i$$满意度，同时花去$$d_i$$元

另外，在第$$i$$天有额外的$$e_i$$打车费用，如下执行
1.如果没有特殊情况，小A有$$p_i$$的概率来付钱，小B有$$1-p_i$$来付钱
2.如果小M也来了，那么从小M上一次付打车钱（没有付过钱的话，就从第一天算起）以来，小A和小B都各自至少支付一次打车费
那么这次费用由小M承担，否则就按第1条规则来
3.小A和小B每天都会出去吃饭，就算小M没有出去吃，小A和小B打车也会被记入次数，并且小M在第$$i$$天知道前面第$$i-1$$天队友打车情况的（即使他没有出去吃）

小M要保证每天都要有饭吃的前提下，最大化最后获得满意值的期望，输出这个最大的期望值

**算法分析**
这个问题，状态定义是可以比较显然的，$$dp(i, T, dA, dB)$$表示第$$i$$天，小M剩下$$T$$元，并且小A小B的打车状态分别是$$dA, dB$$时，最大的期望值

> 先考虑 dp 的起点和终点，不难发现，最开始时候，$$dp(1, T, 0, 0)$$，而终止状态有很多种
可能是$$dp(n, T', \\{0, 1\\}, \\{0, 1\\}), \quad (0 \leqslant T' \leqslant T)$$

那么可以考虑**倒着递推**，枚举当前阶段$$i$$所有可能的状态，最后$$dp(1, T, 0, 0)$$就是我们需要的答案

> 考虑转移

倒着递推，枚举当前$$i$$所有的状态，$$(T, dA, dB)$$，期望 dp，你还需要考虑上一个阶段，**每个状态的权重**
当前$$(dA, dB)$$，上一个状态，$$(dA \mid 1, dB)$$，权重是$$p_i$$，$$(dA, dB \mid 1)$$，权重是$$(1 - p_i)$$

1.吃食堂，小M的满意度转移如下
```math
dp(T, dA, dB) \leftarrow \begin{cases} last(T-b_i, dA \mid 1, dB) \cdot p_i + a_i \\
last(T - b_i, dA, dB \mid 1) \cdot (1 - p_i) + a_i\end{cases}
```
2.出去吃
特别考虑$$(T, 1, 1)$$的情况，$$dp(T, 1, 1) \leftarrow last(T-d_i-e_i, 0, 0) + c_i$$
其他情况，枚举$$dp(T, dA, dB)$$，$$dA, dB$$不同时为$$1$$
```math
dp(T, dA, dB) \leftarrow \begin{cases} last(T-d_i, dA \mid 1, dB) \cdot p_i + c_i \\
last(T - d_i, dA, dB \mid 1) \cdot (1 - p_i) + c_i\end{cases}
```

### 算法实现
```bash
void solve(int cas) {
    int n, T;
    cin >> n >> T;

vector<int> a(n+5, 0), b(n+5, 0), c(n+5, 0), d(n+5, 0), e(n+5, 0), P(n+5, 0);
    vector<double> p(n+5, 0), q(n+5, 0);

for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i] >> e[i] >> P[i];
        p[i] = 1.0 * P[i] / 100;
        q[i] = 1.0 * (100 - P[i]) / 100;
    }
    // debug(p);

vector dp(T+5, vector<vector<double> >(2, vector<double>(2, 0)));
    vector last(T+5, vector<vector<double> >(2, vector<double>(2, 0)));

for (int i = n; i >= 1; i--) {
        last = dp;
        dp.assign(T+5, vector<vector<double> >(2, vector<double>(2, 0)));

for (int t = 0; t <= T; t++) for (int da = 0; da < 2; da++) for (int db = 0; db < 2; db++) {
            if (t - b[i] >= 0) {
                auto lastA = last[t-b[i]][da|1][db], lastB = last[t-b[i]][da][db|1];

chmax(dp[t][da][db], lastA * p[i] + lastB * q[i] + 1.0 * a[i]);

}

if (da & db) {
                if (t - d[i] - e[i] >= 0) {
                    auto lastv = last[t-d[i]-e[i]][0][0];
                    chmax(dp[t][da][db], lastv + 1.0 * c[i]);
                }
            }
            else {
                if (t - d[i] >= 0) {
                    auto lastA = last[t-d[i]][da|1][db], lastB = last[t-d[i]][da][db|1];
                    chmax(dp[t][da][db], lastA * p[i] + lastB * q[i] + 1.0 * c[i]);
                }
            }
        }
    }

auto ans = dp[T][0][0];
    if (fabs(ans - 0.0) <= eps) cout << "-1\n";
    else cout << ans << "\n";
}

```

## 擅长解密的小红同学
**[擅长解密的小红同学](https://ac.nowcoder.com/acm/contest/32282/A)**
密码由`0-9`的数字组成，并且数字$$i$$的出现次数是$$a_i (\in [0, 10^6])$$
每次尝试之后密码会发生改变，但是其数字的出现次数不变（方案之间都是等概的）
求直到成功，尝试次数的期望

### 算法分析
首先，把所有数字的出现次数加起来，$$m = \sum cnt(i)$$，就是**密码有`m`位**

> 概率是多少？

```math
\displaystyle
tot = \binom{m}{n_1, n_2, \cdots, n_k} = \dfrac{m!}{n_1!n_2!\cdots n_k!} \\
\quad \\
p = \dfrac{1}{tot}
```

> 怎么计算期望？

假设尝试$$i$$次后成功，那么$$i$$次成功的概率是$$(1-p)^{i-1} \cdot p$$，从而期望是
```math
\displaystyle
\sum_{i = 1}^{+\infty} i\cdot (1-p)^{i-1} \cdot p = p \cdot \left( \sum_{i = 1}^{\infty} i(1-p)^{i-1} \right)
```
```math
\displaystyle
f(x) = \sum_{k = 1}^{\infty} x^k = \dfrac{x}{1-x} \Rightarrow f'(x) = \sum_{k = 1}^{\infty} k \cdot x^{k-1} = \dfrac{1}{(1-x)^2}
```
所以实际上，期望等于
```math
p \cdot f'(1-p) = \dfrac{1}{p} = tot
```

## Codeforces Round 259 (Div. 1)
### A
**[A. Little Pony and Expected Maximum](https://codeforces.com/contest/453/problem/A)**
**问题描述**
给定$$m$$个面的骰子，第$$i$$个面的点数是$$i$$，$$1 \leqslant i \leqslant m$$，投掷到每一个面的概率都是$$1 / m$$
求独立投掷$$n$$次的最大点数的期望

**算法分析**
**想法一**
不妨设最大点数是$$x$$，那么$$n$$次中，可能有$$1\leqslant i \leqslant n$$次掷出$$x$$，
剩下的呢？剩下的掷出点数$$\leqslant x - 1$$
```math
\displaystyle
\sum_{i=1}^{n} \binom{n}{i} \left(\dfrac{1}{m} \right)^i \left( \dfrac{x-1}{m} \right)^{n - i} \\
\quad \\
= \left( \dfrac{x}{m} \right)^n - \left(\dfrac{x-1}{m} \right)^{n}
```

**想法二**
```math
P(X = x) = P(X \leqslant x) - P(X \leqslant x-1) = \left(\dfrac{x}{m} \right)^n - \left(\dfrac{x-1}{m} \right)^{n}
```
期望很简单了
```math
\displaystyle
\sum_{x = 1}^{m} x \left( \left(\dfrac{x}{m} \right)^n - \left(\dfrac{x-1}{m} \right)^n \right)
```

## Educational Codeforces Round 117
### E
**[E. Messages](https://codeforces.com/contest/1612/problem/E)**
**问题描述**
有$$n$$个学生，$$m$$则消息，第$$i$$个学生需要知道第$$m_i$$则消息，现在贴出$$t$$则消息
对于学生$$i$$，给定一个值$$k_i$$，如果$$t \leqslant k_i$$，学生$$i$$会读完$$t$$则消息
否则的话，学生$$i$$等概率地读$$t$$则消息中的$$k_i$$则，求贴消息的方案，使得读到自己所需要的消息的学生数量的期望最大
其中$$t$$是未知的，需要你去构造

**算法分析**
> 考虑期望怎么求

设随机变量$$x$$表示读到自己希望消息的学生的数量，这个很难算，可以根据**期望的线性可加**来处理
```math
x = x_1 + x_2 + \cdots + x_i + \cdots + x_n, \quad x_i =  \begin{cases} 1 & (\text{第 i 个人 ok}) \\ 0 & (\text{第 i 个人 fail})\end{cases}
```
这里，如果一个人能够顺利读到相关消息，将其记为`ok`，否则记为`fail`

> 如果$$t$$已知，那么就比较好做了

不妨设当前已经贴出来的消息是$$S = \\{ s_1, s_2, \cdots, s_t \\}$$，那么对于第$$i$$个人

1.如果$$m_i \notin S$$，那么很显然$$p(x_i = 1) = 0$$

2.否则的话有两种情况
(1).如果$$t \leqslant k_i$$，那么$$p(x_i = 1) = 1$$
(2).否则的话，$$t > k_i$$，是**条件概率**，$$\displaystyle p(x_i = 1) = p(k_i \mid t) = \dfrac{k_i}{t}$$

实际上条件概率等于$$\displaystyle p(A \mid H) = \dfrac{N(A \cap H)}{N(H)}$$

注意到$$k$$很小，最多只有$$20$$，所以
1.对于$$t \leqslant 20$$的情况，可以暴力每一个$$t$$，`for t`
对于每一个人$$i$$，要读的消息$$m_i$$而言，我们算每一个消息的贡献$$g(m_i)$$
如果$$t \leqslant k_i$$，那么$$g(m_i) += 1$$

否则，$$g(m_i) += \dfrac{k_i}{t}$$

**贪心策略**
这样处理完之后，对所有$$g \neq 0$$的消息，按照$$g$$从大到小排个序，取前$$t$$大即可

2.考虑$$20 < t \leqslant n$$的情况，此时$$t \leqslant k_i$$这一项就没有了，只有$$\sum_i \dfrac{k_i}{t}$$

那么对于消息$$id$$而言，它的贡献是多少呢？根据期望的可加性，$$\displaystyle \dfrac{1}{t} \cdot \sum_i [m_i = id] \cdot k_i$$

同样地，可以贪心，对每条消息按$$k_i$$从大到小排个序，放在`b`中，然后遍历$$t$$的时候
另一个指针$$i$$同时遍历$$b$$，`t`没走一步，`b`中就再增加一个元素，然后维护`b`中已选元素的和$$sum$$
用$$sum / t$$来更新答案即可

## 期望 dp 中的 DAG 模型
给定一个 DAG，每条边有一个权值$$w(u, v)$$，一个人从节点$$x$$出发，假设当前位于节点$$u$$
1.如果节点$$u$$没有连向其他任何节点，那么过程停止
2.人从$$u$$随机走向它的相邻节点$$v$$，概率是$$P(u, v)$$，其中$$\sum_v P(u, v) = 1$$，并且走的路程是$$w(u, v)$$

求一个人从$$x$$出发直到停止时候，走的总路程的期望

> 期望式子的推导
![](/media/content_img/dagexpect.png)

```math
\displaystyle
\mathbb{E}(D_u) = \sum_{v \in G(u)} P_{u, v} \cdot \left( \mathbb{E}(D_v) + w_{u, v} \right)
```

公式理解起来并不难，$$dp(v) + w(u, v) \to dp(u)$$，但这里$$dp(v)$$并不是全部都能转移过来
能转移过来的权重只是其中的$$P(u, v)$$这么多

## AtCoder Beginner Contest 184
### D
**[D - increment of coins](https://atcoder.jp/contests/abc184/tasks/abc184_d)**
当前袋子里有金币$$A$$枚，银币$$B$$枚，铜币$$C$$枚，如果袋子里面某种硬币超过100个，那么结束
每次操作等概率拿出一枚硬币，然后把两个同类型的硬币放回袋子，求操作次数的期望，$$0\leqslant A, B, C \leqslant 99$$

**算法分析**
![](/media/content_img/abc184d.png)

## Codeforces Good Bye 2017
### D
**[D. New Year and Arbitrary Arrangement](https://codeforces.com/contest/908/problem/D)**
给定整数$$k, p_a, p_b$$，一开始序列是空的，每次都会以$$\dfrac{p_a}{p_a + p_b}$$的概率往末尾加入一个`a`
以$$\dfrac{p_b}{p_a + p_b}$$的概率往末尾加入一个`b`，直到序列中有$$\geqslant k$$个的`ab`子序列操作停止
求直到停止时候的操作次数的期望，子序列可以不连续

**算法分析**
![](/media/content_img/bye2017d1.png)
![](/media/content_img/bye2017d2.png)

> 说明，codeforces上原题问的并不是操作次数，而是`ab`子串个数的期望
所以转移的时候，$$p_a \cdot dp(i+1, k) + p_b \cdot dp(i, k+i) \to dp(i, k)$$即可，并不需要`dp(i+1, k) + 1`后转移

上一篇：五月算法竞赛选题（二）下一篇：五月算法竞赛选题（一）

看完文章有啥想法