Codeforces Rating System

来翻译一下官方文档,但是建议看英文原文,本文可能会出现一些错误,虽然不是为了方便自己查阅用的。


首先,对于人 (i),定义 (r_i) 是他的 rating,对于人 (i,j),定义 (P_{i,j}) 为在一场比赛中 (i)(j) 强的概率。

Codeforces 想尽力让这个柿子成立:

[P_{i,j}=frac{1}{1+10^{frac{r_j-r_i}{400}}} ]

一场比赛开始前,定义 (seed_i) 为第 (i) 个人的期望排名。明显有 (seed_i=1+sumlimits_{j e i}P_{j,i})

比赛结束后(如果此时还是 rated 的话),取 (m_i)(seed_i) 和实际排名 (rank_i) 的几何平均数((m_i=sqrt{seed_irank_i}))。把 (m_i) 当作排名计算出这个人在这场比赛中的表现 rating (R_i),然后这个人的 rating 变化是 (d_i=frac{R_i-r_i}{2})

不过这还没完。为了让 rating 平均变化更接近 0,还要进行微调。

再定义一个数 (inc),让所有 (d_i+=inc)

计算方法,先进行第一次微调,这次让 (inc=frac{-1-sum d_i}{n})(n) 是参赛人数)。这保证了所有人的平均变化靠近 0 又在 0 以下。

然后进行第二次微调,取比赛前 rating 前 (s=min(n,4sqrt{n})) 高的人,合理设置 (inc) 使得前 (s) 个人的平均变化为 0。但是这个 (inc) 也不能太大,所以 (inc=min(max(inc,-10),0))。用这个 (inc) 进行第二次微调。这同时让所有人的平均变化在 0 的更下面。(smg 啊……)


upd 2020.5.26:

看到 rating 系统有点小变化,来更新了。

首先注意到新注册的号初始 rating 是 0 而不是 1500。但是对于比较新的号 rating 也会有不同的计算方式。

在第一场比赛中,把他的 rating 看作 (1400) 来计算变化 (d_1)。然后他的 rating 会变成 (500+d_1)

在第二场比赛中,把他的 rating 看作 (1400+d_1) 来计算变化 (d_2)。然后他的 rating 会变成 (500+d_1+350+d_2)

在第三场比赛中,把他的 rating 看作 (1400+d_1+d_2) 来计算变化 (d_3)。然后他的 rating 会变成 (500+d_1+350+d_2+250+d_3)

前六场都这么做,每次后面加的数是 (500,350,250,150,100,50)。注意到这些数的和恰好是 (1400)

以后的场按正常方式计算。

这样的好处:

  • 实质上把每个账号的初始 rating 变成了 1400 左右而不是 1500,可缓解通货膨胀。
  • 目前大多数用户一开始都会不停掉,现在这样也能有鼓励作用了。

现在这个与 AtCoder 有一定相像之处。

原文地址:https://www.cnblogs.com/1000Suns/p/11701028.html