引言
在某款人称赛车界原神的赛车游戏中有组队竞速赛。共有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}
答案就是
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 <= 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()
参考资料
- https://www.cnblogs.com/xiao-apple36/p/9151883.html
[复制链接]
发表于 2024-6-16 17:35
|
发表于 2024-6-17 20:51
