娱乐 每 周 概 率 挑 战 【第一期】

[yhz012]

第一期 年久失修的博丽神社

 

为了争取更多的信徒，东风谷早苗决定在博丽神社外的台阶上挖陷阱来阻碍人们前往博丽神社。现已知博丽神社外台阶共有100阶，参拜客从山脚下（即第0个台阶）开始上山，每次有各1/6的概率爬1、2、3、4、5、6阶。

 

1. 早苗是在凌晨3点想到的这个巧妙的办法，到日出之前只够挖1个陷阱的时间，请问早苗应该把这个陷阱挖在第几个台阶才更可能坑到参拜客？

2. 早苗决定等第二天晚上用一整晚时间挖陷阱，她一晚上可以挖2个陷阱，请问早苗应该把这两个陷阱分别挖在第几个台阶才更可能坑到参拜客？

3. 早苗决定利用河童重工的技术，一晚上挖5个陷阱，请问早苗应该把这些陷阱分别挖在第几个台阶才更可能坑到参拜客？（显然挖6个的话连挖6个肯定就坑死人了，所以5个是最复杂的情况了）

4. 众所周知，幻想乡是有残机这个概念的，被陷阱坑了一次也不会没命。假设参拜客都是被坑了两次才会没命，请问早苗应该把这5个陷阱分别挖到第几个台阶才更可能坑到参拜客？

5. 如果参拜客被坑3次才会没命的话，请问早苗应该把这5个陷阱分别挖在第几个台阶才更可能坑到参拜客？

 

运算量估计会比较大，不要求给出精确解，给出具体计算思路（或者伪代码）即可。

 

召唤阵

@Mr.K 018 @ZERC @alan00290

五月 5, 2020，由yhz012修改

[yhz012]

11 分钟前, applebird 说道:

第一个很简单吧，从0出发1-6的概率都是1/6，然后从1出发将1的概率/6加到2-7上，跑个循环就可以得到每个格子路过的概率了，最后从里面找个max取出来

第二个和第三个不知道有没有精确解，但我感觉贪心应该是比较近似的，反正这个计算量不大，先贪心取一个，然后去掉这一个解把剩下的后面半段跑一遍前面的概率算法，再继续取一个直到满足条件。

第四个第五个思路是一样的，必须踩多少次感觉也不是很重要？和23的埋法应该是一样的

第一问没问题

第二问和第三问是有精确解的，贪心取第一个之后，“去掉这一个解”的意思是？另外如果要用贪心的话，需要先证明贪心的正确性，即部分最优是全局最优？

第四问第五问和23问还是有一些区别的，2、3问的情况是一次就会死，所以不需要考虑连续踩坑的问题，但是4和5就不得不考虑了

 

极端一点的例子是，假设我埋6个坑，那1命的情况下，毫无疑问连挖6坑是最优解，但是2命的情况或许并不是最优解？

五月 5, 2020，由yhz012修改

[yhz012]

3 分钟前, 久帝 说道:

3的话 应该是23456吧 只有第一次1第二次6的欧洲人才不会被坑233

猜对了233居然反倒这个问题先被猜出来了答案233

[yhz012]

5 分钟前, Mr.K 018 说道:

第一问跟楼上说的一样，设p[k]表示踏上第k个台阶的概率，dp一下取出最大的那个就行。

第二问我觉得可以把第一问的算法做修改，设p‘[k][j]表示在已知第k个台阶没有被踏上的情况下，第j个台阶被踏上的概率。这样，假设要在k,j位置挖坑，那么访客掉坑里的概率就是p[k]+(1-p[k])p'[k][j]。O(n^2)搞定

我觉得推广到埋n个坑的情况应该也差不多

如果在上文看到了i，请把它理解成k（

是否可以尝试证明用这种方法连续挖六个坑肯定能行呢？正在尝试，感觉能行

那么p'[k][j]要怎么求呢？

[yhz012]

40 分钟前, Felix_ 说道:

2应该是5、6吧？原理同1

算了一下，如果我没算错的话，并不是第5个台阶和第6个台阶

我index标歪了，非常抱歉，答案是对的

五月 5, 2020，由yhz012修改

[yhz012]

7 分钟前, PhoeniXLL 说道:

我怎么感觉没有五次以下的做法……

计算复杂性的知识都还给老师了

实话来说我现在用的方法是O(n^5)的，不过从结果来看应该有变成常数级的方法，但是应该要一些数学基础证明一些性质

[yhz012]

3 分钟前, PhoeniXLL 说道:

n^5我现在的想法是枚举坑然后容斥算概率问题应该不大

不行就找规律

实际上2、3问我就是这么算的（x

规律这事，你也需要证明这个规律对于任意更多的台阶也一样符合

[yhz012]

1 分钟前, PhoeniXLL 说道:

就算增加台阶答案也不会变，这个还是挺容易想的

但我想不出来增加陷阱/残机的时候变化会不会有一定规律

问题是你要证明增加台阶后面的概率也不会超过前面，举例来说，如果我只有5个台阶，那挖2个陷阱的答案和6个台阶挖2个陷阱的答案（挖5、6）肯定不一样，因为根本就没有第六个台阶。

数学一点的说法就是你要证明这个函数在某一点之后是凸的，或者至少是不大于之前的最大值的。我个人从结果来看证明是凸的可行性似乎比较大

[yhz012]

49 分钟前, PhoeniXLL 说道:

5->6肯定会变，我的意思就是在某一点之后答案不会变化这一点还是挺好理解的，因为我现在知道p(0) = 1, 但是他出现在后面的概率越来越趋向于2/7, 就不容易去找了

我感觉这个点应该不超过40

从实验结果来说其实除了最后一道题，其他的问题可以比这个限制的更多。但是问题还是必须要严格证明才能用这个性质……

对于单个坑很显然会趋于2/7，但是多个坑的情况前面会影响后面的坑，这里就不是很好说了……

五月 5, 2020，由yhz012修改

[yhz012]

3 小时前, Mr.K 018 说道:

因此考虑走个邪道：GA

艹233居然真的开始炼丹了

感觉似乎可以跑，不过感觉可能很容易卡在suboptimal里

常规方法的话，作为提示，先考虑下如果早苗只能挖2个陷阱的时候，参拜客有2条命，要怎么挖？

然后扩展成3陷阱，2命的情况

最后是5陷阱，2命

实际上计算复杂度还是能在O(n^5)的级别，只是比之前的O(n^5)的系数要大很多

[yhz012]

3 小时前, applebird 说道:

精确解的时间复杂度可能比较炸吧

精确解时间复杂度至少我现在手里能用的是O(n^5)级别。当然从结果反推，如果有一些证明，似乎可以压到O(1)不过常数项很大的级别

3 小时前, applebird 说道:

但是去掉了这一次选出的概率最大的坑，因为这个坑选过了，然后再往后推一遍，求个次大的

这个方法有一点问题

举例来说第一问答案是6，按照这个方法似乎只能找6之后的坑？但是实际上第二问答案是5、6

[yhz012]

5 小时前, 可洛 说道:

干脆粗暴点跑个Monte Carlo拉倒了

如果能跑蒙特卡洛的话，稍微调整一下就可以做成particle filter 粒子滤波，因为状态转移方式很简单。然后在这个基础上再调整一下其实就可以求精确解了，要来试试吗？

5 小时前, 可洛 说道:

题4比较麻烦不想做了，但思路基本上一致，比如题4，建立一个二维矩阵P_2(i,j)，P_2(i,j)是踩到i后又踩到j的概率

前面的思路是对的，不过这样求出来的是仅挖2个坑的结果，要怎么继续求出来另外3个坑挖在哪呢？

[yhz012]

17 分钟前, 可洛 说道:

PF没学过www，就学过卡尔曼www

PF其实想法就是先抽样，比如说100,000个样本，然后转移一次。转移后根据限制条件砍掉不符合要求的样本。比如条件是走到了第i个台阶，那么把所有已经超过了i但是没踩过i上的样本直接删掉，再根据比例扩充样本。比如删完之后只剩下50,000个样本，那就把剩下的每个样本复制一个进来，从而恢复到100,000样本。然后继续做下一次转移

实际上可以理解为是带条件概率的蒙特卡洛

 

思路是对的，然后计算量嘛……会真的很大……至少我在服务器上如果跑100个台阶的情况跑20分钟没跑完……

 

稍微有一点问题的是，比如说题4的情况，参拜客有2条命，但是我有5个坑。对100*100的二维矩阵找最大值可以得到最佳的2个坑的位置，但是一共可以挖5个坑，还有3个坑应该挖在哪？

[yhz012]

21 分钟前, 可洛 说道:

理论上用一个5维的矩阵是可以的，但是计算量不是家用电脑可以考虑的。

在PF的基础上再调整调整，就可以避免抽样的情况，从而直接求概率值

用这个方式来建立5维矩阵是可以做的，不过，首先要猜一个上限，前面有人提40台阶作为上限，实际上其实可以比40台阶还能再少一些。（←但是这里我只是从实验结果来看的，没有证明）

 

  

21 分钟前, 可洛 说道:

但坑的位置对结果会造成影响....可以试试对加入两坑之后的情况进行模拟，然后取概率最高的台阶加坑，再次模拟，再加坑，模拟，再加，看看如果后加的坑在先加的坑后面就没有影响，反之....那就重来吧

实际上坑在后面我觉得大概也会有影响？

比如现在挖了坑在5和6，然后求到新的坑在7。之前是只有踩了5和6才会死，但是现在变成了可以56、57、67三种情况了。仅仅第一个踩5，也多了一个情况要考虑了

五月 6, 2020，由yhz012修改

[yhz012]

2 分钟前, applebird 说道:

不是呀，是说去掉6之后6之前的概率不会变，6之后的发生了变化，因此重新求一下，最后选出最大的会发现是5

但是这样的话，最开始选6似乎就有问题了？

因为之所以最开始选6是因为6是没有坑的时候概率最大的

但是现在6前面有坑，所以6的概率也会变化？

 

数学一点的说法是最后答案是5和6，那么被坑的概率是P(5) + P(6 | not 5)，但是这里我们求的概率是P(5 | not 6) + P(6)，这两个是不等的

[yhz012]

58 分钟前, 可洛 说道:

先算了一次二维矩阵，现在来看两命挖两坑是6和12最优。接下来要细解的话可以考虑继续用蒙特卡洛。做法就是把踩到两坑（6和12）的人摘出去，根据接下来的结果加第三坑....

还有一个有趣的小结果，对于命多的人，最好的办法是每隔六个台阶加一坑...

这个结果我在第五问似乎复现出来了，很有趣的现象，但是我不知道为什么会这样

标记一下等我糖重置之后补糖

[yhz012]

1 小时前, applebird 说道:

确实，但是这样应该可以在O（n）里面求出一个较为优的解？

我不太确定这个解的次优程度是否有界，如果证明有界的话，我觉得确实是不错的算法？

毕竟这个问题可以扩展成每次丢个n+1面骰子，然后挖n个坑，一共m个台阶，可以把复杂度从O(m^n)拉到O(m)，算是非常大的提升了

五月 6, 2020，由yhz012修改

[yhz012]

11 小时前, 可洛 说道:

其实是可以理解的，从起点开始，踩到6的概率最高，那接下来的任何一个被踩到的台阶都可以当做一个新的“起点”。基本上我是这么理解的

有道理！极端例子就是n个坑n条命，那么意味着每个坑都必须要踩，于是条件概率下新起点就和之前的起点是等价的了

[yhz012]

1 小时前, PhoeniXLL 说道:

但是好像不太满足贪心，我记得我前天跑的2条命3个坑和2条命4个坑的时候不满足

2命5坑也不满足，不过3命5坑看起来比较容易出现这个效果

 

[yhz012]

15 小时前, 莫得姓名 说道:

莫非你就是魔鬼二号吗，隔壁一个算法挑战，现在又多一个概率挑战

我这边的问题还能挣扎一下的吧？隔壁算法挑战看着就超痛苦的啊（笑）