Codeforces Rating System 算法实现

2018-02-26 7,701 次浏览 数据结构与算法

简介

Codeforces Rating System 是著名算法竞赛网站 Codeforces 的评分计算系统。

Codeforces 使用 rating(评分)来衡量选手水平。每个人都有一定的初始 rating。改变 rating 的主要方式为标准 Codeforces 比赛,一场比赛结束后,Codeforces Rating System 会根据所有参赛选手的现有 rating 和比赛排名来计算每位选手 rating 变化值,以体现出比赛中选手的发挥水平。

在这篇文章里,我们将介绍一下 Codeforces Rating System 的算法步骤,并给出示例代码和测试用例。如果你对 Codeforces 这类多人竞技比赛的评分机制感兴趣,本文可以成为一个参考。

算法步骤

首先,我们需要整场比赛所有参赛者的赛前 rating 和比赛排名作为输入数据。

Codeforces Rating System 的算法扩展了 Elo Rating System。我们令 $r_{i}$ 表示第 $i$ 位参赛者的赛前 rating,然后采用 Elo Rating System 的计分公式来计算出第 $i$ 位参赛者比第 $j$ 位参赛者成绩好的概率:

$$P_{i,j}=\dfrac {1}{1+10^{\dfrac {r_{j}-r_{i}}{400}}}$$

接下来我们计算每位参赛者的期望排名 $seed_{i}$,它等于除了第 $i$ 位参赛者之外的所有其他参赛者的成绩都比自己好的概率:

$$seed_{i}=\sum _{1\leq j\leq n,j\neq i}p_{j,i}+1$$

由于我们的排名是从 $1$ 开始的,因此上述公式最后需要 $+1$。

计算出所有人的期望排名后,一个容易想到的方案是如果参赛者的比赛实际排名比期望排名高,那么就增加他的 rating,反之亦然。

于是我们计算出每位参赛者的实际排名与期望排名 $seed_{i}$ 的几何平均数 $m_{i}$,然后我们用二分查找法找到一个 rating 值 $R_{i}$,表示如果期望排名为 $m_{i}$ 时应有的 rating。有了 $R_{i}$,我们便用 $d_{i}=\left( R_{i}-r_{i}\right) /2$ 作为第 $i$ 位参赛者的 rating 变化值。

到这里 rating 计算就基本完成了,只是还需要对算法做一些优化。Codeforces 提出了一个避免 rating 过度膨胀(例如强者越来越强)的修正方法。需要注意的是,Codeforces Round #327 之后和较之往前的比赛中 rating 计算使用了不同的方法,因此这里我们只考虑较新的方法。

我们需要进行两次抗膨胀操作。

第一次我们令所有参赛者的 $d_{i}=d_{i}+inc$,其中 $inc=-sum\left( d_{i}\right) /n-1$。

第二次我们先找到一部分赛前 rating 最高的参赛者,这部分参赛者的数量我们设为一个启发值 $s=\min \left( n,4\sqrt {n}\right)$,并算出他们的 $d_{i}$ 之和 $sum_{s}$。然后令所有参赛者的 $d_{i}=d_{i}+inc$,其中 $inc=\min \left( \max \left( -sum_{s}/s,-10\right) ,0\right)$(限制 rating 变化量不超过 $0$ 并将变化程度限制到最多降低 $10$)。

经过以上步骤计算后,我们最终得出的 $d_{i}$ 就是赛后每位参赛者的 rating 变化值了。

示例代码和测试用例

Codeforces-Rating-System-third-party-implementation

参考资料

  1. Elo rating system
  2. Open Codeforces Rating System [updated on October 2015]
  3. Codeforces: Rating Is Fixed (bug, go away!)

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2018/02/26/codeforces_rating_system_algorithm.dream

还不快抢沙发

添加新评论