P9477 [_-0 C] 猜数 题解

· · 题解

题目链接

出题人题解实际上在正确性这一块完全是乱说明的，没有任何逻辑，纯粹是名词堆砌：

下面给出一种我想的一种正确性的合理说明方式。

贝叶斯公式可以如下理解：有若干件不同的事 A_1,A_2,\cdots, A_n，它们之中必定发生且只发生一件。设 A_i 的发生概率为 p_i，A_i 发生时 B 的发生概率为 q_i，则 B 发生时 A_i 的发生概率，即为将 p_iq_i 进行归一化（全部乘以特定值使得和为 1）后的结果。

为了简化下面的说明，用 p 代表原题中的 p\%。

对于此题来说，可以定义 1\le i\le n 都对应一个权值 a_i，初始 a_i=1/n。假设询问 y 后返回了 <，那么将 a_y 归零，对所有 i<y 将 a_i 乘上 p，对所有 i>y 将 a_i 乘上 1-p。这样，任何时刻，a_i 都代表此刻结果是 i 的“概率权值”，归一化后即为实际概率。

直到答对之前，每一次询问后，a_x 将以 p 的概率乘以 p，1-p 的概率乘以 1-p，即 \ln a_x 将以 p 的概率增加 \ln p，1-p 的概率增加 \ln (1-p)。

相信大家都听说过大数定律，即一个随机变量多次试验后的均值总是会趋于它的期望。它有一个更“精确”的版本，即中心极限定理：如果随机变量 X 的期望是 E，方差是 \sigma^2，则 n 次试验求平均后，结果的分布会趋向于正态分布 N(E,\sigma^2/n)。

应用在上面即说明，在 q 次询问没猜出来后，

\dfrac{\ln a_x-\ln(1/n)}{q}\sim N(p\ln p+(1-p)\ln (1-p),p(1-p)\ln^2(1/p-1)/q)

现在已经搞清楚了概率权值的分布。既然在求出最终结果前需要归一化，那么下面就研究归一化的分母，即 \sum a_i。

我们希望最终能够以大概率选中答案，即 a_x/\sum a_i 尽量大，那么应该让归一化的分母尽量小。

以贪心策略来说，在每一步询问时，应该让 \max(p\sum\limits_{i<y}a_i+(1-p)\sum\limits_{i>y}a_i,(1-p)\sum\limits_{i<y}a_i+p\sum\limits_{i>y}a_i) 尽量小。

显然，将 y 选为 \sum\limits_{i<y}a_i\le \sum a_i/2 与 \sum\limits_{i<y}a_i>\sum a_i/2 的交界点时，\sum\limits_{i<y}a_i\le \sum a_i/2,\sum\limits_{i>y}a_i\le \sum a_i/2，那么上面的式子就不会超过 \sum a_i/2。

如此一来，就能保证每次 \sum a_i 至少减少一半。

现在假设已经按照上面的方法进行了 q 次询问且没猜出来，此时 \sum a_i\le 2^{-q}。可以发现， 一旦 a_x> \sum a_i/2，下一次询问必定会询问 x，即猜中，那么下一次猜中的概率至少为 a_x> 2^{-q-1} 的概率。

根据上面的正态分布结论，将 p,n,q 带进去计算可以就可以得到一个单点通过概率的下界了。

现在就是把各 Subtask 的数据范围一个一个带进去看了。可以使用 WolframAlpha。

以最后一个 Subtask 为例，带入 p=0.49,n=10^{18},q=249999（需要保留最后一次回答）。这里舍入误差相对比较大，考虑移一些项，记 t=q\left(\dfrac{\ln a_x-\ln (1/n)}{q}-(p\ln p+(1-p)\ln (1-p))\right)，则 t\sim N(0,qp(1-p)\ln^2(1/p-1))=N(0,99.9863)，需要求的概率是 P(a_x>2^{-q-1})=P(t>-9.24975)=82.2527\%。那么，通过整个 Subtask 的概率至少为 (10p^3(1-p)^2+5p^4(1-p)+p^5)|_{p=82.2527\%}=95.7926\%。

可以算出来通过各个 Subtask 的概率依次至少为 100\%,100\%,100\%,100\%,100\%,98.751\%,96.39\%,95.9417\%,95.8114\%,95.7926\%（第一个以后的 100\% 是失败概率低于输出精度了），乘起来也有 83.8166\%。而且实际上这些概率被低估了很多，有可能不需要等到最后一次询问就已经猜到了，实际的通过概率可能有 99\% 以上。

由此，就得到了一个正确性有保证的做法。

具体实现来讲，使用动态开点线段树即可。为了防止概率权值小于实数精度，每次修改时立即归一化即可，整体乘一个常数并不会改变上面的论证的正确性。实现起来没那么麻烦就不附代码了。