娱乐 每 日 算 法 挑 战 【第4期】

[Mr.K 018]

第4期来啦！

前排提示：本题涉及一点概率论，不难，也就高中水平

第4期 芜湖，起飞

 

本期的题目是在飞行棋的棋盘上展开的。棋盘可以想象成一列n个格子，从1到n编号。棋子从第1格开始，每一轮需要掷一枚均匀的6面骰子，取骰子的出目作为前进的格数。当棋子经过第n格（也就是最后一格时），不论是否刚好在这一格停下，就认为是胜利，游戏结束。特别地，棋盘上有若干“飞行通道”，双向连接两个不同编号的格子。若棋子停在了飞行通道的一端，就可以在这一步里直接移动到另一端，也可以选择不移动，直接结束本轮。

已知棋盘的格数n和飞行通道的情况，问从游戏开始到游戏结束，游戏轮数的期望是多少？

输入

有多组测试用例，请读取到文件尾。

每个用例的第一行是两个数n1≤n≤10⁵和k (1≤k≤10³)，分别表示格数和“飞行通道”的数量；
接下来有k行，每行有两个数a­_i和b_i，分别表示第i个飞行通道两个端点在第几格，满足1≤a­_i<b­_i≤n.

输出

对每个测试用例，输出一个小数占一行，表示游戏轮数的期望值，精确到小数点后4位。

 

后排召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui

四月 13, 2020，由Mr.K 018修改

[sgszx]

通道是双向的吗？还是固定从a->b？

[Mr.K 018]

刚刚, sgszx 说道:

通道是双向的吗？还是固定从a->b？

双向

[Muriya Tensei]

我太菜了，等大佬一波解答

四月 13, 2020，由Muriya Tensei修改

[随性而为]

问：在双向通道中来回横跳怎么办

然而不管你怎么改，我都不会做

 

四月 13, 2020，由随性而为修改

[yhz012]

艹这就突然变成我老本行了（x

我拿particle filter做可以不，暴力模拟的（

等我刷完牙开始写好了，已经有想法了

 

为了方便我就把格子从0开始编号了，所以会和题目中的编号差1，不过不影响大局。

首先需要一个概率论非常重要的性质，即期望的线性性 —— 定理1

可以表述为E( sum_i (k_i X_i) ) = sum_i ( k_i E(X_i))，其中的k为常数X为随机变量

 

我们考虑最简单的情况，终点在1

有期望 = 1 * 1 = 1，即1的概率走至少1格，花费1步

 

终点在2时，我们有

1/6的概率走到1，花费1步，然后变成剩下1格的情况，即期望1。以及5/6的情况花费一步直接到位。即期望 1/6 * (1 + 1) + 5/6 = 7/6

 

终点在3时，我们有

1/6走到1，花费1，变成剩下2格。1/6走到2，花费1，变成剩下1格，4/6的情况一步到位。即期望1/6 * (1 + 7/6) + 1/6 * (1 + 1) + 4/6 * 1 = 49/36

 

终点4同理，有

1/6 * (1 + 49/36) + 1/6 * (1 + 7/6) + 1/6 * (1 + 1) + 3/6 * 1 = 343/216

 

终点5同理，有

1/6 * (1 + 343/216) + ... = 2401/1296

 

终点6同理有

16807/7776

 

ok，现在初始表格填完了，接下来考虑递推，因为显然终点在至少是7的时候不存在1步到位的情况了，所以是通项公式

终点在k的时候我们有花1步把问题变为

1/6概率终点在k-1

1/6概率终点在k-2

1/6概率终点在k-3

1/6概率终点在k-4

1/6概率终点在k-5

1/6概率终点在k-6

利用定理1，得到K = 1 + 1/6 (K-1 + K-2 + K-3 + K-4 + K-5 + K-6)，其中大写K为终点在K时的期望步数，K-x同理。

至此，如果无传送门，得解。（注：这里可以用类似斐波那契数列的矩阵求法类似的方式直接得到通项公式） —— 公式1

 

为了解决传送门问题，首先我们需要准确知道到各传送门的概率。

类似的方法，初始化-5~-1号格子为0， 0号格子为1，对格子k有

K = 1/6 (K-1 + K-2 + K-3 + K-4 + K-5 + K-6)，其中大写K为走到格子K的概率，K-x同理。 —— 公式2

 

需要注意的是，对于传送门实际上我需要精确的刚好走到这一格的期望，因为错过了就凉了，所以需要求的期望和上面的终点期望稍微有一些不同

举例来说1是(1 * 1/6) / 1/6 = 1，2是(2 * 1/36 + 1 * 1/6) / (1/36 + 1/6)，3是(3 * 1/6^3 + 2 * 1/6^2 * 2 + 1 * 1/6) / (1/6^3 + 1/6^2 * 2 + 1/6)……

不过同样的对于7及以上可以得到和公式1一样的递推公式 —— 公式3

实际上这里我们已经得到了精确地走到每个格子的期望，为了转化成最终结果，只需要对最后6个格子的递推公式改一下，把置零的部分变成置一就可以了

 

然后传送门可以理解为将a端的期望直接复制给b端即可（ab可互换）（当然是选择留小的就是了这句有很大问题

 

想了下基本上已经可以做了

公式3依然可以暴力做成矩阵的通项公式的形式，然后对于传送门两侧update一下之后继续用递推公式暴力打表就好了，最后用最后6个格子的期望稍微处理一下就完了

四月 13, 2020，由yhz012修改

[yhz012]

22 分钟前, Muriya Tensei 说道:

那么对于飞行通道描述中的，可以选择飞也可以不飞，如何理解

首要的目的是快速通关还是 完全随机（那不就是1/2飞了么），如果为了快速通关，也不必要双向啊

有必要的，举例来说我现在一共100格子，有通道1-51，48-52，49-100

[Muriya Tensei]

1 分钟前, yhz012 说道:

有必要的，举例来说我现在一共100格子，有通道1-51，48-52，49-100

默认会选择最优的走法吗（比如你举的这个例子，如果51到了52，是否飞回48,），计算期望选择还是emmm

[yhz012]

1 分钟前, Muriya Tensei 说道:

默认会选择最优的走法吗（比如你举的这个例子，如果51到了52，是否飞回48,），计算期望选择还是emmm

这部分以我的理解是玩家自己选择的，所以肯定对于玩家来说是主动选择最优解法

[Mr.K 018]

1 小时前, Muriya Tensei 说道:

那么对于飞行通道描述中的，可以选择飞也可以不飞，如何理解

首要的目的是快速通关还是 完全随机（那不就是1/2飞了么），如果为了快速通关，也不必要双向啊

玩家会选择尽可能快地通关。

四月 13, 2020，由Mr.K 018修改

[Xchara]

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

 

前排提示：本题涉及一点概率论，不难，也就高中水平

那我一定上的是个假高中咯

[Muriya Tensei]

（对于传送门的算法依然想不清楚）等个大佬分析……

依然想不到一个好的算法可以正确识别一个传送门应该正飞还是反飞（举例，100~100000, 90~101, 91~102, 92~103, 93~104, 94~105, 95~106）

对于概率和均轮数的算法都很简单（没有门的情况下），都是简单的递推算法。。

四月 13, 2020，由Muriya Tensei修改

[ppzt]

蒙特卡罗的话大概就是根据当前所在位置计算期望最短路径然后走

然后模拟足够多次拟合期望

不暴力模拟直接算我没想到什么好的方法