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

[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修改

[applebird]

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

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

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

[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修改

[久帝]

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

[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（

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

五月 5, 2020，由Mr.K 018修改

[yhz012]

3 分钟前, 久帝 说道:

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

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

[Felix_]

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

[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]要怎么求呢？

[Mr.K 018]

4 分钟前, yhz012 说道:

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

p'[k][j]求法跟p[k]差不多，唯一的区别是到p'[k][k]的值强行设为0，跟其他地方的运算规则不一样

同样的道理适用于p⁽ⁿ⁾[k]₁[k]₂⋯[k]_n

五月 5, 2020，由Mr.K 018修改

[yhz012]

40 分钟前, Felix_ 说道:

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

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

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

五月 5, 2020，由yhz012修改

[PhoeniXLL]

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

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

[yhz012]

7 分钟前, PhoeniXLL 说道:

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

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

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

[PhoeniXLL]

6 分钟前, yhz012 说道:

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

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

不行就找规律

[yhz012]

3 分钟前, PhoeniXLL 说道:

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

不行就找规律

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

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

[PhoeniXLL]

1 小时前, yhz012 说道:

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

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

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

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

[yhz012]

1 分钟前, PhoeniXLL 说道:

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

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

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

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

[PhoeniXLL]

2 分钟前, yhz012 说道:

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

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

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

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

[yhz012]

49 分钟前, PhoeniXLL 说道:

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

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

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

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

五月 5, 2020，由yhz012修改

[Mr.K 018]

看大佬讨论问题，流下了不懂数学的泪水……

前三问都可以直接计算的，大不了O(n^5)嘛，有些情况下多项式时间已经不错了，参考我上午的回答和其他人的讨论

后面两问暂时没想出来有效的算法，因此考虑走个邪道：GA

先随机初始化n个解当作初始种群，然后迭代执行以下操作：

1. 对种群中的每个解打分

2. 按一定比例去掉打分最低的解。设去掉了n个解

3. 进行n次繁殖，补回去掉的解。繁殖方法可以是随机抽取两个解（解的评分越高，被抽中的概率也应越高），两个解的编码做适当的交叉互换，并按一定概率突变以后作为新的解加入到种群中。

重复以上迭代操作直至收敛或执行完了指定的轮数或时间为止。

要解决以下几个问题：

1)评分算法。考虑进行若干次模拟，统计因中陷阱而GG的情况的占比，作为评分。考虑到计算代价，模拟次数似乎不必做特别多，几十次就行？

2)解的编码。假设要挖出k个坑，考虑将每个坑的位置用一个整数表示。不必从小到大排列。

3)交叉互换和突变。考虑将交叉互换算法设置为：对每一个子代基因编码中的整数，均随机地从两个亲本的对应数字中抽出一个。如果出现重复数字，则将其中一个赋随机值。突变可考虑设置为将某一个数字赋上随机值。

---

这个算法不知道行不行得通，但是调参多半是没跑了

五月 5, 2020，由Mr.K 018修改

[applebird]

7 小时前, yhz012 说道:

第一问没问题

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

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

 

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

精确解的时间复杂度可能比较炸吧，最近大数据做多了都往近似里面去了，近似的话就是再重复一次第一问的算法，但是去掉了这一次选出的概率最大的坑，因为这个坑选过了，然后再往后推一遍，求个次大的

[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

[可洛]

概率全还给老师了www，干脆粗暴点跑个Monte Carlo拉倒了

以下：

剧透

没往多了跑，matlab模拟了十万次爬到顶。

根据上图：

题1：6 （之前手滑了打成5www）

题2：肯定有6www，再蒙个5吧

题3好像前面有人蒙出来了

题4比较麻烦不想做了，但思路基本上一致，比如题4，建立一个二维矩阵P_2(i,j)，P_2(i,j)是踩到i后又踩到j的概率（matlab里面我保留了原始跑台阶的数据，所以这个很容易做出来），然后P(i)从上图可得，解出P(i)*P(i,j)就好

题5和上题一致，建立一个二维矩阵后再建一个三维矩阵就好，一样的

五月 5, 2020，由可洛修改

[yhz012]

5 小时前, 可洛 说道:

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

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

5 小时前, 可洛 说道:

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

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

[可洛]

1 小时前, yhz012 说道:

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

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

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

三个坑其实和两个坑是一样的，不过运算量会大很多。

我现有的矩阵是100,000*100的，以防万一扔出100个1....可以把出现过1的行集中一下，然后是出现2的...以此类推到100

重新整理出的矩阵会是100*100。这个是两个坑的矩阵

三个坑的情况需要整理原始矩阵两次。第一次先做出两个坑的矩阵，第二次的话，比如说一个踩了1阶又踩了2阶和3阶的情况：逐行扫，出现了1，出现了2，又出现3的情况就记录一下，以此类推....是个非常非常粗暴的方法...做出来会是一个100*100*100的矩阵。不过算这个的话跑10w次的sample好像不太够www