Mighty Rock Tower & Game on Sum

__ryp__ · 2024-10-07 10:38:22 · 个人记录

Mighty Rock Tower

题意：一个石子堆，初始为空，每次操作可以放上一枚石子。设当前石子的数量是 x，那么这一轮有 P_x 的概率一个石子掉落（石子掉落后 x 仍不变）。求石子堆到 n 个的期望步数。

设 f_i 表示由 i - 1 个石子堆到第 i 个的期望步数。考虑从第 i - 1 个石子堆上后发生了什么。

一种可能是全掉完了。概率是 P_i^i，代价是 \sum\limits_{j=1}^i f_j；

另一种可能是掉到某一个 j 就不再掉，概率是 P_i^{i-j} (1 - P_i)，代价是 \sum\limits_{k=j+1}^i f_j。这里 j\in [1, i]。

还有根本没有掉的，但是根本没有贡献。

这个式子拆开 1 - P_i 项化简，可以得到一个 O(N) 转移。由于 P_i 只有 100 种，因此可以对每一种 P_i 前缀优化。最终复杂度是 O(n\max P)。

Game on Sum (Hard Version)

先看 Subtask 1。设 f(i, j) 表示 Bob 已经进行了 i 轮，已经选择了 j 轮加法，最后的值。

现在我们不知道 Alice 会选什么。但是设她会选 t，那么

Bob 会让答案尽可能小，所以外面套一个 \min。这个式子显然是在取到均值的时候最大，因此 Alice 会取这两个转移路径的均值。于是我们得到

边界是 j = 0 和 i = j。j = 0 时，Bob 全都选减法，因此 Alice 全给 0。j = i 时，Bob 全选加法，因此 Alice 全给 k。

对于 Subtask 2，考虑每个位置对 f(n, m) 的贡献。能贡献的位置只有 f(i, i) = ki，贡献路径是 (i, j) \rightarrow (i + 1, j), (i + 1, j + 1)，也就是竖着或者斜着走，方案数是 n - i - 1\choose m - j。贡献是多少？一开始的贡献是 ki，随着往下走一行，会除以一个二。一共走 n - i 行，因此除以 2^{n-i}。

所以最后的答案是

比较奇妙。