AT_iroha2019_day3_j Go to Heaven 题解

M1rai · 2024-10-31 20:13:11 · 题解

前言

题解区做法不太详细，来大致复述一下官方题解（不会日语，可以理解为机翻润色）。

思路

题面的第一句话表明了这题考察的是我们的 rp。

为了增加 rp，普通人可以采用以下方法来提升自己的运势：

• 去神社或寺庙祈福；
• 去教堂向上帝祈祷，请求他洗清你过去的罪孽；
• 讲究风水，合理摆放家具。

然而，这些做法大多都需要花费几个小时，无法在赛时完成。

因此这道题目的做法只剩下了“一直提交，直到获得 AC”的策略。假设你的运气一般，每次提交 AC 的几率正好是 \frac{1}{2}，若 p_i 为提交了 i 次至少获得了一次 AC 的概率，根据 p_i=1-\frac{1}{2^i}，可以得到 p_3=0.875,p_5=0.96875,p_{10}≈0.999，说明这种做法是可行的。

至此，这个问题得以解决。