yhz012

我直觉是这俩问题难度一样？但是我还没想好怎么构造问题来互相归约 如果一样，那某种意义上我们可以用最小生成树来求bounded approximate solution。 在想如果我允许vertex的weight是负的，但是agent的weight始终是max(1, tempW)，是不是在原点处增加n个负w顶点就可以归约了…… 我需要证明回家一定只会吃掉手上相同的权重的负w顶点……多吃肯定是亏的，主要问题是少吃的情况……

我觉得这问题本身确实很有意思，而且直球来说其实我最近在做和这边有关的算法 感觉有一些能挣扎的地方，但是我的大脑现在处于罢工状态……

艹基础题是缓存命中问题 附加题……曼哈顿距离，边的权重可变，求traveling sales man…… 我觉得这已经不是不保证了吧，完全可以规约到普通的TSP问题，只要令所有商店的物品重量为0即可……

让我把最近期末的事情处理完开始更概率挑战 目前第二期的题目我有点想法了，不过我大概得先自己代码跑一下（ 这题如果只求模拟的话，大概是我专业了（x 不过解析解……我估计求积分我要疯

我以为会卡住一部分人的问题居然反倒直接被猜出来了，而且逻辑是如此清晰流畅，岂可修233

原题链接： https://sstm.moe/topic/255008-每-周-概-率-挑-战-【第一期】/ 已有的优质答案： 第一问实际上等价于求参拜客踩到各个台阶上的概率，然后选取概率最大的台阶挖坑即可。 为了方便，我们不妨假设还有-1、-2、-3、-4、-5层台阶。现在已知参拜客最开始必然出现在0号台阶。因此我们可以初始化概率 P[0] = 1 P[-5: 0] = 0 考虑参拜客在台阶i上，下一步会有各P / 6出现在i+1到i+6上。把这个想法重复6次，我们即可得到参拜客出现在台阶j上的概率是由j-6到j-1这6个台阶的概率的1/6组成的，即： P[j] = sum(P[j - 6 : j]) / 6 现在我们有了初始状态和递推公式，即可把全部100层台阶的概率全写出来 def forward(startIndex, initP) for index in range(startIndex, 101): initP[index] = sum(initP[index - 6 : index]) / 6 P[0] = 1 P[-5: 0] = 0 P = forward(1, P) 接下来只要找到这里面的最大值在哪即可 return argmax(P[1 : 101]) 第二问因为早苗可以挖2个坑，而参拜客只有1条命，那么实际上坑到参拜客只有2种情况：1. 参拜客被第一个陷阱坑了， 2. 参拜客躲过了第一个陷阱但是被第二个坑了。这两个事件是互斥事件，因此被坑的概率可以直接求和 所以最暴力的方案就是我们搜索所有可能的2个坑的情况，即： for index1 in range(1, 101): for index2 in range(index1 + 1, 101): p1 = #TODO p2 = #TODO prob = p1 + p2 情况1可以直接参考第一问，列出参拜客走到各台阶的概率。 p1 = P[index1] 情况2会麻烦一些，因为我们需要先保证参拜客没有走到前一个陷阱，因此我们新开一个数列计算。显然在index1之前的概率不会有影响，但是index1的概率我们需要强制置为0来保证参拜客没有走到这个台阶上，随后我们可以继续进行递推公式 def evade(index, P): newP = copy(P) newP[index] = 0 newP = forward(index1 + 1, newP) return newP newP = evade(index1, P) p2 = newP[index2] 接下来就是找到使得prob最大的index1和index2即可 if prob > tempMaxProb: tempMaxProb = prob tempMaxIndex = (index1, index2) 第三问实际上就是第二问的推广，最坏情况下我们可以用index1到index5建立5重循环，暴搜就好了 第四问我们有5个坑，但是参拜客有2条命。我们把情况分解来看，参拜客可能踩到12,13,14,15,23,24,25,34,35,45。总计10种情况，且每种情况都是互斥的，所以还是直接都加起来就好了（笑） 实际上我们可以把这些情况稍微整理下。考虑第一个坑踩到的是1，那么为了坑到参拜客，参拜客必须要在2345里面踩到1个。同理，如果第一个坑是2（即参拜客躲开了1），那么必须在345里踩一个。如果第一个是3（即躲开了12），那么必须踩45里的一个。如果是第一个是4,（躲开了123），那么必须要踩5。 作为举例，我们考虑情况第一个是3,（躲开了12），接着在45里踩一个。 首先我们要求参拜客确实第一个踩的是3的概率p3： for index1 in range(1 : 101): for index2 in range(index1 + 1 : 101): for index3 in range(index2 + 1 : 101): for index4 in range(index3 + 1 : 101): for index5 in range(index4 + 1 : 101): prob1 = #TODO: case 1 + 2345 prob2 = #TODO: case 2 + 345 newP1 = evade(index1, P) newP2 = evade(index2, newP1) p3 = newP2[index3] p34 = #TODO p35 = #TODO prob3 = p3 * (p34 + p35) prob4 = #TODO: case 4 + 5 prob = prob1 + prob2 + prob3 + prob4 接下来变成了假定参拜客确实踩在了3上，给定这个条件，实际上我们并不需要再去考虑之前参拜客踩过哪里了，因为这些信息不再影响下一步参拜客踩在哪的概率。形象一点的说法，就像我们知道参拜客最开始在0号台阶上，我们不会关心他是坐着幻想乡里不存在的公交车，还是从紫maslkdjflw的隙间里过来来到0号台阶的，因为之后无论如何，他都是1/6概率走到123456号台阶上。同样的道理也在index3上有效，之后无论如何，他都是1/6的概率走到了index3 + 123456上。我们在某种意义上可以把index3视作新的“0号台阶”。 def trap(index): newP[index] = 1 newP[index - 5 : index] = 0 newP = forward(index + 1, newP) return newP newP3 = trap(index3) 那么之后的问题就变成了在newP3的分布上，参拜客要么踩到4，要么躲开了4踩到5的概率： p34 = newP3[index4] newP4 = evade(index4, newP3) p35 = newP4[index5] 同样的道理用在其他的情况上，最后再找到使得prob最大的index就完成了。 第五题其实就是第四题的推广。我们的情况变成了1 + 2 + 345， 1 + 3 + 45， 1 + 4 + 5， 2 + 3 + 45， 2 + 4 + 5， 3 + 4 + 5 这6大种情况了

所以这个算法的推论是，均值最后会趋于强连通分量的最小均值环（无论是否包含该顶点）？ 全图-x这个做的是真的漂亮

那最坏情况是在强连通部分暴搜所有环，然后判断环是否包含该顶点……

附加题至少有一些预处理可以做 给定有向图，那首先可以获取给定顶点的强连通部分strongly connected components，任何包含这个顶点的环必然只在这个部分里 说起来题目要求简单环么，如果要求的话，甚至可以根据双联通bi-connected再砍一次？

噗，那最坏情况就给每个路径单独维护一个closed list，然后dfs限定最大深度s跑起来就完了（

艹我想了半天这是谁，然后我想起来了brute force ↓我真的以为有现成的算法来判定无向图中2顶点间是否存在给定长度路径的算法，然后百度搜到是字符串匹配算法，就很迷惑

反正先跑一遍1的算法不亏，同样的道理，如果最短路径d < s,或者d - s是奇数，就可以直接放弃治疗了 对于d-s是偶数的情况那就需要额外判断是否存在指定长度的迂回路径了…… 感觉可以考虑用类似iterative dfs的想法解？就是限制dfs深度在s上，如果求到了K-S路径，那就能跑，求不到就凉了 不对，似乎有问题，除非同时维护多个closed list，否则idfs也一样会出现incomplete的问题 所以还是考虑迂回路径似乎更靠谱一点 如果迂回路径存在，那首先这个图要存在环，所以不存在环的情况可以直接打死了 （总觉得这回问题比我想的要难了……我甚至怀疑是NP级别的 自信点，把觉得删了。我可以不断增加s大小，这样这个问题可以用来找到一个图里的最长简单路径。已知最长简单路径是NPC，这问题没跑了

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

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

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

上一题我可以绕开有限状态机，纯靠栈来写，这个我大概是真的绕不开了吧…… 另外至少把上一期的参与者也拉来啊（x不能只有我一个人面对恐惧（x @北冥有鱼1573

我不太确定这个解的次优程度是否有界，如果证明有界的话，我觉得确实是不错的算法？ 毕竟这个问题可以扩展成每次丢个n+1面骰子，然后挖n个坑，一共m个台阶，可以把复杂度从O(m^n)拉到O(m)，算是非常大的提升了

这个结果我在第五问似乎复现出来了，很有趣的现象，但是我不知道为什么会这样 标记一下等我糖重置之后补糖

艹是语法检查 我这是被钦定了吗，瑟瑟发抖

但是这样的话，最开始选6似乎就有问题了？ 因为之所以最开始选6是因为6是没有坑的时候概率最大的 但是现在6前面有坑，所以6的概率也会变化？ 数学一点的说法是最后答案是5和6，那么被坑的概率是P(5) + P(6 | not 5)，但是这里我们求的概率是P(5 | not 6) + P(6)，这两个是不等的

在PF的基础上再调整调整，就可以避免抽样的情况，从而直接求概率值 用这个方式来建立5维矩阵是可以做的，不过，首先要猜一个上限，前面有人提40台阶作为上限，实际上其实可以比40台阶还能再少一些。（←但是这里我只是从实验结果来看的，没有证明） 实际上坑在后面我觉得大概也会有影响？ 比如现在挖了坑在5和6，然后求到新的坑在7。之前是只有踩了5和6才会死，但是现在变成了可以56、57、67三种情况了。仅仅第一个踩5，也多了一个情况要考虑了

PF其实想法就是先抽样，比如说100,000个样本，然后转移一次。转移后根据限制条件砍掉不符合要求的样本。比如条件是走到了第i个台阶，那么把所有已经超过了i但是没踩过i上的样本直接删掉，再根据比例扩充样本。比如删完之后只剩下50,000个样本，那就把剩下的每个样本复制一个进来，从而恢复到100,000样本。然后继续做下一次转移 实际上可以理解为是带条件概率的蒙特卡洛 思路是对的，然后计算量嘛……会真的很大……至少我在服务器上如果跑100个台阶的情况跑20分钟没跑完…… 稍微有一点问题的是，比如说题4的情况，参拜客有2条命，但是我有5个坑。对100*100的二维矩阵找最大值可以得到最佳的2个坑的位置，但是一共可以挖5个坑，还有3个坑应该挖在哪？

最坏情况其实可以先单独用栈处理一遍rd来变成()d的模式，接着再用常规调度场算法。因为反正都是线性扫一遍，不影响最后O(n)的结果（虽然会加大常数）

如果能跑蒙特卡洛的话，稍微调整一下就可以做成particle filter 粒子滤波，因为状态转移方式很简单。然后在这个基础上再调整一下其实就可以求精确解了，要来试试吗？ 前面的思路是对的，不过这样求出来的是仅挖2个坑的结果，要怎么继续求出来另外3个坑挖在哪呢？

精确解时间复杂度至少我现在手里能用的是O(n^5)级别。当然从结果反推，如果有一些证明，似乎可以压到O(1)不过常数项很大的级别 这个方法有一点问题 举例来说第一问答案是6，按照这个方法似乎只能找6之后的坑？但是实际上第二问答案是5、6