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

文章目录

- 引言
- 所有人都能完成
- 可能有人未完成
- 扩展问题
- 参考资料

引言

在某款~~人称赛车界原神的~~赛车游戏中有组队竞速赛。共有n个人，n为偶数，分为人数相等的红队和蓝队进行比赛。结果按排名得分的数组为pts，单调递减且均为正整数。比如pts = [10, 8, 6, 5, 4, 3, 2, 1]表示第1~8名分别为所在队伍获得10、8、6、…、1分。总分高的队获胜，如果总分一样，则获得第一名的队获胜。对以下情况，分别求红队获胜的情况数。

所有人都能完成。
可能有人未完成（显然第一名完成了），未完成的都获得0分。

作者：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。

在下面的代码中，我还输出了所有方案，方便后文进行探究。思路：状压枚举，S为1的位表示红队队员的名次。
为了在终端输出彩色文字，我用到一个叫colorama的包，用法非常简单：参考链接1。

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[i] = 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[i]
            if red_rk == n + 1:
                red_rk = i + 1
        else:
            blue += pts[i]
            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 << n):
        if bc[S] != n >> 1:
            continue
        red, red_rk, blue, blue_rk = calc_teams_pt(S, n)
        if red > blue or (red == blue and red_rk < blue_rk):
            tot += 1
            colorful_pt_info = [f'{Fore.RED if S >> i & 1 else Fore.BLUE}{pts[i]}' 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()

输出示意：

在这里插入图片描述

可能有人未完成

这个问题似乎有点难，我们不妨先输出方案。

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 << m):
            if bc[S] > 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 < blue_rk):
                tot += 1
                colorful_pt_info = [f'{get_color(S, i, m)}{pts[i] if i < m else 0}' for i in range(n)]
                print(red, red_rk, blue, blue_rk, ', '.join(colorful_pt_info))
    return tot

代码思路很简单，先枚举完成人数m，再进行m位，而非n位的状压枚举即可。输出：

在这里插入图片描述

n = 4时答案为3 + 3 + 2 + 1 = 9，再结合上图展示的颜色信息，似乎跟组合数息息相关。我们还是和上一章一样从对称性入手，即一种红队赢的情况反转后总是一种蓝队赢的情况。所以从直觉上看，答案应该是一些组合数的和除以2。

假设共有m人完成，1 <= m <= n，红队有0 <= i <= min(m, n / 2)人完成，那么蓝队完成人数满足0 <= m - i <= n / 2，得max(0, m - n / 2) <= i <= min(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}

答案就是
$\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 <= i <= n/2+1)。接着我们考虑看着上文展示出的数塔，结合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[i] = 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[i]
            if red_rk == n + 1:
                red_rk = i + 1
        else:
            blue += pts[i]
            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 << n):
        if bc[S] != n >> 1:
            continue
        red, red_rk, blue, blue_rk = calc_teams_pt(S, n)
        if red > blue or (red == blue and red_rk < blue_rk):
            tot += 1
            colorful_pt_info = [f'{Fore.RED if S >> i & 1 else Fore.BLUE}{pts[i]}' 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) <= i <= min(m, n / 2)
def calc_method_num_hard(n: 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):
        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 << m):
            if bc[S] > 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 < blue_rk):
                tot += 1
                colorful_pt_info = [f'{get_color(S, i, m)}{pts[i] if i < m else 0}' 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
    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[i] = 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[i]
            if red_rk == n + 1:
                red_rk = i + 1
        else:
            blue += pts[i]
            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 << m):
            if bc[S] > 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 < blue_rk):
                tot += 1
    return tot


def calc_method_num_hard(n: 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):
        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 << (i - j) for j in range(i)]
        tot12 = solve(i, pts2)
        print(f'tot11 = {tot11}, tot12 = {tot12}')
        tot2 = calc_method_num_hard(i)
        tot3 = calc_method_num_ez(i)
        assert ans[(i >> 1) - 1] == tot11 and tot11 == tot12 and tot11 == tot2 and tot11 == tot3


if __name__ == '__main__':
    main()