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

关键逻辑：由于每个物理签在序列最后位置的概率均等，某玩家获胜（最后完成）的概率等于：他拥有的“在该数值所有拥有者中优先级最低”的签的总数，除以总签数。

python

import sys

def solve():
    data = sys.stdin.read().split()
    if not data: return
    it = iter(data)
    n, k = int(next(it)), int(next(it))
    
    counts = {}
    last_owner = {}
    for p_idx in range(n):
        for _ in range(k):
            val = int(next(it))
            counts[val] = counts.get(val, 0) + 1
            last_owner[val] = p_idx # 覆盖更新，由于 p_idx 递增，最后存的是最大编号

    prob_weights = [0] * n
    for val, c in counts.items():
        prob_weights[last_owner[val]] += c
        
    total = n * k
    for w in prob_weights:
        print(f"{w/total:.9f}")

solve()

逻辑分析
令牌分配：假设总共有 $N = n \times k$ 个数字。由于每个数字 $v$ 可能出现多次，我们可以把它们看作不同的“令牌”。例如，如果数字 1 出现了 3 次，我们可以称它们为 $1^{(1)}, 1^{(2)}, 1^{(3)}$ 。根据规则，反应最快的玩家优先划掉数字。这意味着如果玩家 $A$ 比玩家 $B$ 快，且两人都有数字 $v$ ，那么在随机抽出的序列中，第一个出现的 $v$ 一定是被 $A$ 划掉，第二个出现的 $v$ 才会轮到 $B$ 。
结论：对于任何数字 $v$ ，如果它在所有玩家的纸上总共出现了 $m_{v}$ 次，那么这 $m_{v}$ 个 $v$ 在随机序列中出现的顺序决定了归属。该数字最后一次（第 $m_{v}$ 次）出现时，必然是被拥有该数字且反应最慢（即编号最大）的玩家划掉的。
最后完成的条件：一个玩家完成游戏的时刻，就是他分配到的最后一个令牌被抽出的时刻。在所有 $N$ 个令牌随机排列的序列中，整个游戏的“最后完成者”就是排在序列最后一位（第 $N$ 位）的令牌所属的玩家。
计算概率：
在总共 $N$ 个令牌的随机排列中，任何一个令牌出现在最后位置的概率都是 $\frac{1}{N}$ 。
对于数字 $v$ ，其出现的总次数为 $m_{v}$ 。只有该数字最后一次出现的那个令牌（即第 $m_{v}$ 个 $v$ ）可能出现在序列的最后位置。
由于序列中任意一个位置放哪个数字的概率取决于该数字的总数，因此序列最后一位是数字 $v$ 的概率为 $\frac{m_{v}}{N}$ 。
如果最后一位是数字 $v$ ，那么“最后完成”的玩家就是拥有数字 $v$ 的所有玩家中编号最大（反应最慢）的那一位。

T28748: PKU游戏 ​

T28748: PKU游戏