T28748: PKU游戏

math, http://cs101.openjudge.cn/practice/28748/

PKU 是一种多人参与的机会游戏。每个玩家会得到一张写有一些数字的纸，游戏主持人会随机报出这些数字。玩家需要将自己听到的数字划掉，最先划掉所有数字的玩家获胜。这个基础版本的游戏有点名声不好，因为它有点无聊。玩家唯一的任务就是不要睡着。

在这个问题中，我们将分析一种更加动态的PKU游戏的版本，它需要玩家快速反应。我们的版本叫做 “Speed PKU”（极速PKU），游戏主持人同样会随机报出纸上的数字。然而，每当一个数字被报出时，只有第一个表示自己有这个数字的玩家才被允许在自己的纸上划掉这个数字。如果某个玩家有多个相同的数字，每次只能划掉其中一个。当多个玩家的纸上都有相同的数字时，反应最快的玩家在“极速PKU”中将占有优势。但这个优势到底有多大？我们需要你来帮忙计算。

严谨的描述：有 n 位玩家，每个玩家会收到一张写有 k 个（不一定不同的）数字的纸。玩家 1 的反应速度比玩家 2 快，玩家 2 的反应速度比玩家 3 快，以此类推，玩家 n 是反应最慢的。考虑以下示例，来自第一个样例输入，三位玩家每人收到四个数字：

当数字“1”第一次被叫到时，反应更快的玩家 1 将优先把它划掉。第二次数字“1”被叫到时，玩家 2 将能够划掉它。以此类推，平均来说，玩家 1 的表现会比玩家 2 和玩家 3 更好，因为后两位玩家需要某些玩家 1 会先抢到的数字。然而，由于玩家 2 和玩家 3 没有相同的数字，他们的表现彼此独立，尽管玩家 2 比玩家 3 反应更快。

所有n x k个数字（包括重复的数字）被制作成抽签放入暗箱中，主持人每次从中不放回地抽出一个签作为本次叫出的数字，直到所有数字都被抽出。那么每个玩家最后一个完成的概率是多少呢？

输入

输入描述的是一局 Speed PKU 的游戏。第一行包含两个整数 n 和 k，分别表示玩家的数量和每个玩家纸上的数字数量（1 ≤ n ≤ 100，1 ≤ k ≤ 1000)。接下来的n行，每行包含k个整数，第i行表示第i位玩家纸上的数字。这些数字都在 1 到 10^9之间（含 1 和 10^9）。

输出

输出包含n行，每行对应一个玩家。第i行应包含玩家i最后完成游戏的概率。所有的值的绝对误差必须不超过10^-6，保留九位小数。

样例输入

sample1 input:
3 4
1 2 3 4
1 2 5 6
3 4 7 8

sample1 output:
0.000000000
0.500000000
0.500000000

样例输出

sample2 input:
4 2
1 2
3 4
10 5
7 8

sample2 output:
0.250000000
0.250000000
0.250000000
0.250000000

提示

tags: greedy, difficult: 900

来源

2024 TA-Xjk

这是一个概率计算问题，我们可以将其转化为一个组合计数问题。

问题分析

游戏机制与结束条件：
- 游戏中有 $n$ 名玩家，每人手中有 $k$ 个数字。
- 暗箱中总共有 $N = n \times k$ 个数字（对应所有玩家纸上数字的多重集并集）。
- 数字被逐一取出（不放回）。
- 游戏一直进行直到所有数字都被取出。
- 我们要计算的是每个玩家“最后完成”的概率。
谁是最后完成的玩家？
- 既然游戏直到所有数字都被取出才停止，那么最后一个被取出的数字（第 $N$ 个数字）决定了游戏的终结。
- 拥有第 $N$ 个数字（即最后一个被叫到的数字）的玩家，一定是在这一刻才划掉他的这一个数字。
- 这意味着，该玩家不可能在第 $N$ 个时刻之前完成游戏（因为他当时还有一个数字没划掉）。
- 同时，所有其他玩家的数字都在前 $N - 1$ 个时刻被叫到了（因为第 $N$ 个数字属于特定的某一位玩家，而其他所有 $N - 1$ 个数字都属于其他人或该玩家的其他数字），所以其他玩家一定都在第 $N$ 个时刻之前或恰好在第 $N$ 个时刻完成了任务。
- 关键结论：在一个特定的抽签序列中，拥有最后一个被抽出的数字的那位玩家，就是最后完成游戏的玩家。
数字的所有权分配（优先级规则）：
- 题目规定了优先级：玩家 1 > 玩家 2 > ... > 玩家 $n$ 。
- 当一个数字（例如 "5"）被叫到时，拥有该数字且优先级最高的玩家划掉它。
- 这意味着：
  - 如果池子中有 $C$ 个 "5"，
  - 玩家 1 如果需要 $k_{1}$ 个 "5"，他会拿走前 $k_{1}$ 次出现的 "5"。
  - 玩家 2 如果需要 $k_{2}$ 个 "5"，他会拿走接下来的 $k_{2}$ 次出现的 "5"。
  - 以此类推。
- 因此，对于任何一个特定的数值 $v$ ，它在游戏过程中最后一次出现（第 $C$ 次出现）时，一定归属于需要该数字的玩家中，优先级最低（编号最大）的那一位。
概率计算：
- 暗箱中的 $N$ 个数字进行随机排列（全排列）。
- 由于排列是完全随机的，暗箱中的每一个物理签（card）都有均等的机会 $\frac{1}{N}$ 出现在序列的最后一位。
- 因此，玩家 $i$ 最后完成的概率等于：(归属于玩家 $i$ 的签在最后一位出现的次数) / (总排列数)。
- 结合上述分析，这等价于：(归属于玩家 $i$ 的签的数量) / $N$ 。
- 哪些签归属于玩家 $i$ 且可能出现在最后一位呢？
- 这里有一个逻辑转换：并不是看哪个物理签，而是看数值。
- 对于任何数值 $v$ ，虽然它在池子里可能有多个副本，但在随机打乱的序列中，最后出现的那个 $v$ 一定归属于该数值的所有者中编号最大的那个玩家（设为 $P_{m a x} (v)$ ）。
- 所以，如果序列的最后一个数字是 $v$ ，那么最后完成的玩家就是 $P_{m a x} (v)$ 。
- 最后一位是数值 $v$ 的概率是多少？既然池子里有 $C o u n t (v)$ 个 $v$ ，总共有 $N$ 个数字，那么最后一位是 $v$ 的概率是 $\frac{C o u n t (v)}{N}$ 。
- 因此，玩家 $i$ 最后完成的概率 = $\sum_{v ∣ P_{m a x} (v) = i} \frac{C o u n t (v)}{N}$ 。

算法步骤

读取输入，统计池子中每个数值 $v$ 的总出现次数 $C o u n t (v)$ 。
同时，对于每个数值 $v$ ，记录拥有该数字的玩家中的最大编号 $P_{m a x} (v)$ 。由于输入是按玩家顺序给出的（玩家1到玩家n），我们只需要遍历所有玩家的数字，不断更新该数值对应的拥有者即可，最后留下的自然是编号最大的。
初始化每个玩家的“权重”为 0。
遍历所有出现过的数值 $v$ ：
- 找到该数值的 $P_{m a x} (v)$ 。
- 将该数值的总计数 $C o u n t (v)$ 加到玩家 $P_{m a x} (v)$ 的权重上。
最终，玩家 $i$ 的概率 = (玩家 $i$ 的权重) / (所有数字的总数 $n \times k$ )。

Python 代码实现

python

import sys

def solve():
    # 读取所有输入数据
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return

    iterator = iter(input_data)
    
    try:
        n = int(next(iterator))
        k = int(next(iterator))
    except StopIteration:
        return

    # number_counts: 记录每个数字在整个游戏中出现的总次数
    number_counts = {}
    # number_last_owner: 记录拥有该数字的玩家中编号最大的那个（优先级最低）
    number_last_owner = {}

    # 依次处理每个玩家的数字
    # 玩家编号从 1 到 n
    for player_idx in range(1, n + 1):
        for _ in range(k):
            val = int(next(iterator))
            
            # 更新该数字的总计数
            if val in number_counts:
                number_counts[val] += 1
            else:
                number_counts[val] = 1
                
            # 更新该数字的最后拥有者
            # 因为我们是按玩家编号从小到大遍历，所以这里直接覆盖即可
            number_last_owner[val] = player_idx

    # 计算每个玩家最后完成的“权重”
    # 权重 = 如果最后一个被抽出的数字是 v，且 v 的最后拥有者是该玩家，
    #        则该数值 v 贡献 Count(v) 份可能性给该玩家。
    player_wins = [0] * (n + 1)
    
    for val, count in number_counts.items():
        owner = number_last_owner[val]
        player_wins[owner] += count
        
    total_cards = n * k
    
    # 输出结果，保留9位小数
    for i in range(1, n + 1):
        prob = player_wins[i] / total_cards
        print(f"{prob:.9f}")

if __name__ == "__main__":
    solve()

T28748: PKU游戏 ​

T28748: PKU游戏