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

[PhoeniXLL]

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

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

[PhoeniXLL]

6 分钟前, yhz012 说道:

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

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

不行就找规律

[PhoeniXLL]

1 小时前, yhz012 说道:

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

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

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

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

[PhoeniXLL]

2 分钟前, yhz012 说道:

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

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

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

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

[PhoeniXLL]

于 2020/5/5 于 PM8点11分, Mr.K 018 说道:

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

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

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

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

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

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

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

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

要解决以下几个问题：

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

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

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

---

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

后两问和前三问没有本质区别，只不过是必须要踩的坑变多了而已吧

[PhoeniXLL]

49 分钟前, yhz012 说道:

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

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

五月 7, 2020，由PhoeniXLL修改