CodeForce-Gym 101736 G题：最小化期望得分的概率求解

问题描述 #

给定由n个隔间组成的环形转轮，每个隔间设有出口。小球初始时被均匀随机放入任意隔间，移动规则如下：

• 处于隔间i（1≤i<n）时，以概率pᵢ退出转轮，以1-pᵢ概率移动至隔间i+1；
• 处于隔间n时，以概率pₙ退出转轮，以1-pₙ概率移动至隔间1。

玩家初始得分为0，每次访问隔间i获得aᵢ分，从隔间j退出额外获得bⱼ分。需在0.01≤pᵢ≤0.99的约束下分配所有pᵢ，最小化玩家的期望得分。

输入：n及每个隔间的aᵢ、bᵢ；输出：最小期望得分，允许1e-6的绝对或相对误差。

解题思路 #

1. 期望得分建模 #

设Eᵢ为从隔间i出发的期望得分，根据规则可列出递推式：

• 对于i < n：$E_i = a_i + p_i b_i + (1-p_i) E_{i+1}$
• 对于i = n：$E_n = a_n + p_n b_n + (1-p_n) E_1$

目标是最小化总期望得分 $\frac{1}{n}\sum_{i=1}^n E_i$，同时满足每个pᵢ∈[0.01, 0.99]。

2. 无约束最优解推导 #

忽略pᵢ的上下限约束，通过拉格朗日乘数法分析最优条件：
对总期望关于每个pᵢ求偏导并令其为0，可推导出最优解满足 $E_{i+1} - b_i = \lambda$（λ为常数，i < n），且 $E_1 - b_n = \lambda$。

将此关系代入递推式，可得无约束下的pᵢ表达式：
$$p_i = \frac{a_i + b_i - b_{i-1}}{\lambda}$$
其中$b_0 = b_n$。

3. 约束处理 #

若无约束下的pᵢ落在[0.01, 0.99]区间内，即为最优解；若存在pᵢ超出边界，则将其固定为边界值（0.01或0.99），并将对应隔间与相邻隔间合并，重新构建问题求解剩余变量。

可通过二分法寻找合适的λ，使得所有pᵢ满足约束：

• 根据pᵢ的约束条件确定λ的初始范围；
• 迭代二分λ，检查对应的pᵢ是否全部在约束范围内；
• 找到符合条件的λ后，代入递推式求解所有Eᵢ，计算平均值得最小期望得分。

4. 特殊情况处理 #

当n=1时，递推式简化为 $E_1 = \frac{a_1}{p_1} + b_1$：

• 若a₁>0，取p₁=0.99以最小化E₁；
• 若a₁<0，取p₁=0.01以最小化E₁；
• 若a₁=0，E₁=b₁，与p₁无关。

代码实现 #

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx +=1
    a = []
    b = []
    for _ in range(n):
        ai = float(input[idx])
        bi = float(input[idx+1])
        a.append(ai)
        b.append(bi)
        idx +=2
    
    if n == 1:
        if a[0] > 1e-12:
            res = a[0]/0.99 + b[0]
        elif a[0] < -1e-12:
            res = a[0]/0.01 + b[0]
        else:
            res = b[0]
        print("{0:.10f}".format(res))
        return
    
    # 二分法寻找合适的lambda
    left = 1e-12
    right = 1e12
    
    # 初始化lambda的边界
    for i in range(n):
        prev_b = b[(i-1)%n]
        numerator = a[i] + b[i] - prev_b
        if abs(numerator) < 1e-12:
            continue
        if numerator > 0:
            left = max(left, numerator / 0.99)
            right = min(right, numerator / 0.01)
        else:
            left = max(left, numerator / 0.99)
            right = min(right, numerator / 0.01)
    
    # 迭代二分
    for _ in range(100):
        lam = (left + right) / 2
        valid = True
        p = []
        for i in range(n):
            prev_b = b[(i-1)%n]
            numerator = a[i] + b[i] - prev_b
            pi = numerator / lam
            if pi < 0.01 - 1e-12 or pi > 0.99 + 1e-12:
                valid = False
                break
            p.append(pi)
        if not valid:
            # 调整lambda范围
            for i in range(n):
                prev_b = b[(i-1)%n]
                numerator = a[i] + b[i] - prev_b
                pi = numerator / lam
                if pi < 0.01:
                    if numerator > 0:
                        left = lam
                    else:
                        right = lam
                    break
                elif pi > 0.99:
                    if numerator > 0:
                        right = lam
                    else:
                        left = lam
                    break
            continue
        
        # 计算E_i
        coeff = 1.0
        const = 0.0
        for i in range(n-1, -1, -1):
            if i == n-1:
                coeff = (1 - p[i])
                const = a[i] + p[i] * b[i]
            else:
                new_coeff = (1 - p[i]) * coeff
                new_const = a[i] + p[i]*b[i] + (1 - p[i])*const
                coeff, const = new_coeff, new_const
        
        x = const / (1 - coeff)
        total = x
        current = x
        for i in range(n-1):
            current = a[i] + p[i]*b[i] + (1-p[i])*current
            total += current
        
        avg = total / n
        print("{0:.10f}".format(avg))
        return
    
    # 处理需要固定边界的情况（此处简化实现）
    pass

if __name__ == "__main__":
    main()

注意事项 #

• 浮点数精度：计算中需使用足够小的epsilon（如1e-12）避免除以零或误判边界。
• 边界合并：当存在pᵢ超出约束范围时，需将对应隔间与相邻隔间合并，重新建模递推关系，这部分逻辑需根据实际情况补充完善。
• 迭代次数：二分法迭代100次足够满足1e-6的精度要求。

内容的提问来源于stack exchange，提问作者adomakor412