【算法】某赛车游戏中的组合计数问题及其扩展。推导思路:层层合并

查看 49|回复 3
作者:hans7   
引言
在某款人称赛车界原神的赛车游戏中有组队竞速赛。共有n个人,n为偶数,分为人数相等的红队和蓝队进行比赛。结果按排名得分的数组为pts,单调递减且均为正整数。比如pts = [10, 8, 6, 5, 4, 3, 2, 1]表示第1~8名分别为所在队伍获得10、8、6、…、1分。总分高的队获胜,如果总分一样,则获得第一名的队获胜。对以下情况,分别求红队获胜的情况数。
[ol]
  • 所有人都能完成。
  • 可能有人未完成(显然第一名完成了),未完成的都获得0分。
    [/ol]
    作者:hans774882968以及hans774882968以及hans774882968
    本文52pojie:https://www.52pojie.cn/thread-1935160-1-1.html
    本文juejin:https://juejin.cn/post/7380579040824737830
    本文CSDN:https://blog.csdn.net/hans774882968/article/details/139723445
    所有人都能完成
    显然要么红队赢要么蓝队赢,又因为红队和蓝队地位相同,所以答案为C(n, n / 2) / 2。
    [ol]
  • 在下面的代码中,我还输出了所有方案,方便后文进行探究。思路:状压枚举,S为1的位表示红队队员的名次。
  • 为了在终端输出彩色文字,我用到一个叫colorama的包,用法非常简单:参考链接1。
    [/ol]
    from colorama import Fore, init
    from math import comb
    pts = [10, 8, 6, 5, 4, 3, 2, 1]
    bc = [0] * 256
    def init_bc():
        for i in range(1, len(bc)):
            bc = bc[i >> 1] + (i & 1)
    def calc_teams_pt(S: int, n: int):
        red, red_rk, blue, blue_rk = 0, n + 1, 0, n + 1
        for i in range(n):
            if S >> i & 1:
                red += pts
                if red_rk == n + 1:
                    red_rk = i + 1
            else:
                blue += pts
                if blue_rk == n + 1:
                    blue_rk = i + 1
        return red, red_rk, blue, blue_rk
    def solve_all_complete(n: int):
        if n & 1:
            raise ValueError(f'n should be even, but got {n}')
        tot = 0
        for S in range(1, 1 > 1:
                continue
            red, red_rk, blue, blue_rk = calc_teams_pt(S, n)
            if red > blue or (red == blue and red_rk > i & 1 else Fore.BLUE}{pts}' for i in range(n)]
                print(red, red_rk, blue, blue_rk, ', '.join(colorful_pt_info))
        return tot
    def main():
        init(autoreset=True)
        init_bc()
        for i in range(2, 9, 2):
            tot = solve_all_complete(i)
            print(f'tot = {tot}')
            assert tot == comb(i, i >> 1) >> 1
    if __name__ == '__main__':
        main()
    输出示意:


    paopao-1.jpg (74.35 KB, 下载次数: 0)
    下载附件
    2024-6-16 17:34 上传

    可能有人未完成
    这个问题似乎有点难,我们不妨先输出方案。
    def solve_at_most_8(n: int):
        if n & 1:
            raise ValueError(f'n should be even, but got {n}')
        def get_color(S: int, i: int, m: int):
            if i >= m:
                return Fore.WHITE
            return Fore.RED if S >> i & 1 else Fore.BLUE
        member_num = n >> 1
        tot = 0
        for m in range(n, 0, -1):
            for S in range(1, 1  member_num or m - bc[S] > member_num:
                    continue
                red, red_rk, blue, blue_rk = calc_teams_pt(S, m)
                if red > blue or (red == blue and red_rk
    代码思路很简单,先枚举完成人数m,再进行m位,而非n位的状压枚举即可。输出:


    paopao-2.jpg (107.46 KB, 下载次数: 0)
    下载附件
    2024-6-16 17:34 上传

    n = 4时答案为3 + 3 + 2  + 1 = 9,再结合上图展示的颜色信息,似乎跟组合数息息相关。我们还是和上一章一样从对称性入手,即一种红队赢的情况反转后总是一种蓝队赢的情况。所以从直觉上看,答案应该是一些组合数的和除以2。
    假设共有m人完成,1 ,红队有0 人完成,那么蓝队完成人数满足0 ,得max(0, m - n / 2) 。i的所有取值构成一座简单的数塔,以n = 2, 4, 6, 8为例:
    2 2 {1}
    2 1 {0, 1}
    4 4 {2}
    4 3 {1, 2}
    4 2 {0, 1, 2}
    4 1 {0, 1}
    6 6 {3}
    6 5 {2, 3}
    6 4 {1, 2, 3}
    6 3 {0, 1, 2, 3}
    6 2 {0, 1, 2}
    6 1 {0, 1}
    8 8 {4}
    8 7 {3, 4}
    8 6 {2, 3, 4}
    8 5 {1, 2, 3, 4}
    8 4 {0, 1, 2, 3, 4}
    8 3 {0, 1, 2, 3}
    8 2 {0, 1, 2}
    8 1 {0, 1}
    答案就是
    ans = \frac{\sum_{m=1}^{n} \sum_{i=max(0, m - n / 2)}^{min(m, n / 2)} C_m^i}{2}
    去OEIS上搜这个数列,可以得到一个更简洁的公式:C(n + 1, n >> 1) - 1。接下来我们看看推导过程。首先注意到m = 1~n/2取到的i集合都是满的,于是有2^1 + ... + 2^(n/2) = 2^(n/2+1) - 2。而2^(n/2+1) = sum(C(n/2+1, i), 0 。接着我们考虑看着上文展示出的数塔,结合C(i, j) = C(i - 1, j) + C(i - 1, j - 1)进行层层合并:C(n/2+1, 0~n/2+1)和已有的C(n/2+1, 1~n/2)可以凑出C(n/2+2, 1~n/2+1),C(n/2+2, 1~n/2+1)和已有的C(n/2+2, 2~n/2)可以凑出C(n/2+3, 2~n/2+1),C(n/2+3, 2~n/2+1)和已有的C(n/2+3, 3~n/2)可以凑出C(n/2+4, 3~n/2+1)……直到最后只剩C(n / 2 + n / 2 + 1, n/2~n/2+1),而C(n + 1, n / 2) = C(n + 1, n / 2 + 1),于是2 * ans = 2 * C(n + 1, n / 2) - 2。
    完整代码:
    from colorama import Fore, init
    from math import comb
    pts = [10, 8, 6, 5, 4, 3, 2, 1]
    bc = [0] * 256
    def init_bc():
        for i in range(1, len(bc)):
            bc = bc[i >> 1] + (i & 1)
    def calc_teams_pt(S: int, n: int):
        red, red_rk, blue, blue_rk = 0, n + 1, 0, n + 1
        for i in range(n):
            if S >> i & 1:
                red += pts
                if red_rk == n + 1:
                    red_rk = i + 1
            else:
                blue += pts
                if blue_rk == n + 1:
                    blue_rk = i + 1
        return red, red_rk, blue, blue_rk
    def solve_all_complete(n: int):
        if n & 1:
            raise ValueError(f'n should be even, but got {n}')
        tot = 0
        for S in range(1, 1 > 1:
                continue
            red, red_rk, blue, blue_rk = calc_teams_pt(S, n)
            if red > blue or (red == blue and red_rk > i & 1 else Fore.BLUE}{pts}' for i in range(n)]
                print(red, red_rk, blue, blue_rk, ', '.join(colorful_pt_info))
        return tot
    # equivalent to max(0, m - n / 2) > 1
        tot = 0
        for m in range(n, 0, -1):
            st = set()
            for i in range(max(1, m - member_num), min(m, member_num) + 1):
                st.add(i)
                st.add(m - i)
            for v in st:
                tot += comb(m, v)
        return tot >> 1
    # C(2n+1, n) - 1 = 2, 9, 34, 125
    def calc_method_num_ez(n: int):
        if n & 1:
            raise ValueError(f'n should be even, but got {n}')
        return comb(n + 1, n >> 1) - 1
    def solve_at_most_8(n: int):
        if n & 1:
            raise ValueError(f'n should be even, but got {n}')
        def get_color(S: int, i: int, m: int):
            if i >= m:
                return Fore.WHITE
            return Fore.RED if S >> i & 1 else Fore.BLUE
        member_num = n >> 1
        tot = 0
        for m in range(n, 0, -1):
            for S in range(1, 1  member_num or m - bc[S] > member_num:
                    continue
                red, red_rk, blue, blue_rk = calc_teams_pt(S, m)
                if red > blue or (red == blue and red_rk > 1) >> 1
        for i in range(2, 9, 2):
            tot1 = solve_at_most_8(i)
            print(f'tot1 = {tot1}')
            tot2 = calc_method_num_hard(i)
            tot3 = calc_method_num_ez(i)
            assert tot1 == tot2 and tot2 == tot3
    if __name__ == '__main__':
        main()
    扩展问题
    现在考虑pts为任意单调递减数组,n为任意偶数,方案数还是C(n + 1, n >> 1) - 1吗?代码运行结果表明,答案是肯定的。
    from typing import List
    from math import comb
    import random
    bc = [0] * 1048576
    def init_bc():
        for i in range(1, len(bc)):
            bc = bc[i >> 1] + (i & 1)
    def calc_teams_pt(S: int, n: int, pts: List[int]):
        red, red_rk, blue, blue_rk = 0, n + 1, 0, n + 1
        for i in range(n):
            if S >> i & 1:
                red += pts
                if red_rk == n + 1:
                    red_rk = i + 1
            else:
                blue += pts
                if blue_rk == n + 1:
                    blue_rk = i + 1
        return red, red_rk, blue, blue_rk
    def solve(n: int, pts: List[int]):
        if n & 1:
            raise ValueError(f'n should be even, but got {n}')
        member_num = n >> 1
        tot = 0
        for m in range(n, 0, -1):
            for S in range(1, 1  member_num or m - bc[S] > member_num:
                    continue
                red, red_rk, blue, blue_rk = calc_teams_pt(S, m, pts)
                if red > blue or (red == blue and red_rk > 1
        tot = 0
        for m in range(n, 0, -1):
            st = set()
            for i in range(max(1, m - member_num), min(m, member_num) + 1):
                st.add(i)
                st.add(m - i)
            for v in st:
                tot += comb(m, v)
        return tot >> 1
    # C(2n+1, n) - 1 = 2, 9, 34, 125, 461, 1715, 6434, 24309, 92377, 352715
    def calc_method_num_ez(n: int):
        if n & 1:
            raise ValueError(f'n should be even, but got {n}')
        return comb(n + 1, n >> 1) - 1
    def gen_decr_arr(n: int):
        a = [1]
        for _ in range(n - 1):
            a.append(a[-1] + random.randint(1, 10))
        a = a[::-1]
        return a
    def main():
        init_bc()
        ans = [2, 9, 34, 125, 461, 1715, 6434, 24309, 92377, 352715]
        for i in range(2, 21, 2):
            pts1 = gen_decr_arr(i)
            print(f'pts1 = {pts1}')
            tot11 = solve(i, pts1)
            pts2 = [1 > 1) - 1] == tot11 and tot11 == tot12 and tot11 == tot2 and tot11 == tot3
    if __name__ == '__main__':
        main()
    参考资料
    [ol]
  • https://www.cnblogs.com/xiao-apple36/p/9151883.html
    [/ol]

    都能, 答案

  • vethenc   

    感谢大佬分享
    一弍彡亖乄   

    感谢分享,楼主辛苦了~~~~~!
    爱学习的小妖精   

    感谢大佬分享学到了
    您需要登录后才可以回帖 登录 | 立即注册