CodeForces & AtCoder rating 规则简述

作者:rui_er,转载请注明出处。

0 由于 latex 炸了,建议前往洛谷博客查看 Link

本博客为了方便自己查阅,同时也方便大家了解,但因为我嘤语很菜,所以难免有翻译错的地方,还请评论区纠正。

未注明资料来源的均为常识积累。

1 CodeForces rating 规则

1.1 CodeForces rating 与名字颜色换算

rr 表示 rating,则 CodeForces 的名字颜色有以下几等:(从低到高)

  • 黑色不加粗(代码 #000000):Unrated,没有参加过比赛。
  • 黑色(代码 #000000):Headquarters,管理员。
  • 灰色(代码 #808080):Newbie,r<1200r\lt 1200
  • 绿色(代码 #008000):Pupil,1200r<14001200\le r\lt 1400
  • 青色(代码 #03a89e):Specialist,1400<r16001400\lt r\le 1600
  • 蓝色(代码 #0000ff):Expert,1600<r19001600\lt r\le 1900
  • 紫色(代码 #aa00aa):Candidate Master,1900r<21001900\le r\lt 2100
  • 橙色(代码 #ff8c00):Master,2100r<23002100\le r\lt 2300
  • 橙色(代码 #ff8c00):International Master,2300r<24002300\le r\lt 2400
  • 红色(代码 #ff0000):Grandmaster,2400r<26002400\le r\lt 2600
  • 红色(代码 #ff0000):International Grandmaster,2600r<30002600\le r\lt 3000
  • 首字母黑色+红色(代码 #ff0000(:first-letter 伪类为 #000000)):Legendary Grandmaster,r3000r\ge 3000

1.2 CodeForces rating 与是否计入比赛(及比赛赛制)

除非赛时因为 CodeForces 爆炸等原因 Unrated,否则比赛 rated 的范围如下:

  • Div.4:r<1400r\lt 1400,exICPC 赛制。
  • Div.3:r<1600r\lt 1600,exICPC 赛制。
  • Div.2 Only:r<2100r\lt 2100,CF 赛制。
  • Div.2:r<1900r\lt 1900,CF 赛制。
  • Div.1:r1900r\ge 1900,CF 赛制。
  • Educational Round:r<2100r\lt 2100,exICPC 赛制。
  • Global Round:Rated for all\rm{Rated\ for\ all},CF 赛制。
  • 其他比赛:见赛前通知。

1.3 CodeForces rating 在 rated 比赛中的计算

此部分资料来源:翻译自 Open Codeforces Rating System [updated on October 2015]

假设每一个人原来的 rating 为 rir_i,则根据以下公式计算 ii 在比赛中得分高于 jj 的概率:

Pi,j=11+10rjri400P_{i,j}=\frac{1}{1+10^{\frac{r_j-r_i}{400}}}

因此我们可以由两人的 rating 差值算出他们其中一个比另一个得分高的期望概率。例如,如果两个人的 rating 差为 200200,则 rating 高的人赢过另一方的概率被认为是 0.750.75;若 rating 差为 400400,则这一概率约为 0.90.9

根据这一概率,我们可以得到每个选手赛后的期望排名:

seedi=j=1jinPj,i+1seed_i=\sum_{{j=1}\atop{j\neq i}}^n{P_{j,i}+1}

例如,在 Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 1) 以前,tourist\textsf{t\color{red}ourist} 的 rating 为 35033503,因此期望排名约为 1.71.7Petr\textsf{P\color{red}etr} 的 rating 为 30293029,因此期望排名约为 10.710.7

一般的想法就是,如果实际排名比 seediseed_i 更靠前,增加 rating;反之减少。

这里计算出 seediseed_i 与实际排名的几何平均数:

mi=seedi×rankim_i=\sqrt{seed_i\times rank_i}

则我们二分查找出一个 RiR_i 使得该用户计算出的 seedi=miseed_i=m_i。显然 rir_i 应该像更靠近 RiR_i 的方向变化。我们取 di=Riri2d_i=\frac{R_i-r_i}{2} 作为该用户的 rating 变化值。

不过我们为了让 rating 的平均变化更接近 00,还需进行以下微调:

定义一个数 incinc,让所有 did_i 增加 incinc

第一次微调:

inc=1dininc=\frac{-1-\sum{d_i}}{n}

保证所有人的平均变化接近 00 但在 00 以下。

第二次微调:

取前 s=min(n,4n)s=\min(n,4\sqrt{n}) 高的人,取一个合理地 incinc 使得前 ss 人的平均变化为 00。但是 incinc 也不能太大,因此去 inc=min(max(inc,10),0)inc=\min(\max(inc, -10), 0),用这个值进行第二次微调。

CodeForces rating 计算的源码地址:Link

1.4 CodeForces rating 初始值

此部分资料来源:Codeforces: Soon We Will Change the Rating Calculation for New Accounts

以前的初始值都是 15001500 分,但在 2020.6 前后,CodeForces 更改了 rating 规则。

新注册的号(或未打过比赛的号)的初始 rating 是 00 而不是 15001500

对于比较新的号 rating 也会有不同的计算方式:

在第一场比赛中,将 rating 看作 14001400 来计算变化,然后计算后的 rating 会变成 500+d1500+d_1

在第二场比赛中,将 rating 看作 1400+d11400+d_1 来计算变化,然后计算后的 rating 会变成 500+d1+350+d2500+d_1+350+d_2

前六场比赛都是类似的方法,每次加的数是 500,350,250,150,100,50500,350,250,150,100,50,总和为 14001400

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

2 AtCoder 规则

2.1 AtCoder rating 与名字颜色换算

鉴于自己只打过 33 场 AtCoder,此部分待补充

2.2 AtCoder 可参加比赛的 rating

ABC、ARC、AGC 比赛界面可以查看。

一般地:

  • ABC:0r<20000\le r\lt 2000
  • ARC:0r<28000\le r\lt 2800
  • AGC:Rated for all\rm{Rated\ for\ all}

2.3 AtCoder rating 在 rated 比赛中的计算

此部分资料来源:翻译自 AtCoder Rating System ver. 1.00

在每场比赛后,你都有一个 performance 值 XX。如果算出的这个值稳定在 XX,则你的 rating 会从 X1200X-1200 逐渐上升为 XX。不用担心在第一场比赛中得到很低的 rating,你的真实水平可以在大于 1010 场比赛后大致看出。

你可以在 https://atcoder.jp/users/{username}/history 查看你每场比赛的 performance 被四舍五入后的值,下面是计算方法:

对于每个参赛者,我们求出平均 perf:(这里 Perf1PerfkPerf_1\sim Perf_k 表示各场比赛获得的 perf,不四舍五入,时间从后向前)

APerf=i=1kPerfi×0.9ii=1k0.9iAPerf=\frac{\sum_{i=1}^kPerf_i\times 0.9^i}{\sum_{i=1}^k0.9^i}

对于没打过比赛的萌新来讲怎么办?我们设置 CenterCenter 作为 APerfAPerf

Center={800,ABC1000,ARC1200,AGCCenter=\begin{cases}800,&ABC\\1000,&ARC\\1200,&AGC\end{cases}

nn 为参赛人数,APerfiAPerf_i 表示 iiAPerfAPerf 值,则排名为 rr 的人的 perf 记为 XX,为下面方程的解:

i=1n11+6.0XAPerfi400.0=r0.5\sum_{i=1}^n\frac{1}{1+6.0^{\frac{X-APerf_i}{400.0}}}=r-0.5

对于并列的人,rr 取他们 rank 的平均值。

对于第一场比赛,进行特判:

Perf=(PerfCenter)×1.5+CenterPerf=(Perf-Center)\times 1.5+Center

最后,真实的 perf 计算如下:

RPerf=min(Perf,RATEDBOUND+400)RPerf=\min(Perf, \rm{RATEDBOUND}+400)

其中 RATEDBOUND\rm{RATEDBOUND} 表示 rated 的最大范围,见上一条。

计算完了 perf,让我们一起计算一下 rating!

什么你跟我说前面算了这么多乱七八糟的都没算 rating?

是的就是这个意思。

定义以下函数:

F(n)=i=1n0.81ii=1n0.9iF(n)=\frac{\sqrt{\sum_{i=1}^n0.81^i}}{\sum_{i=1}^n0.9^i}

f(n)=F(n)F()F(1)F()×1200f(n)=\frac{F(n)-F(\infty)}{F(1)-F(\infty)}\times 1200

g(x)=2x800g(x)=2^{\frac{x}{800}}

则:

Rating=g1(i=1kg(RPerfif(i))×0.9ii=1k0.9i)Rating=g^{-1}\left(\frac{\sum_{i=1}^kg(RPerf_i-f(i))\times 0.9^i}{\sum_{i=1}^k0.9^i}\right)

注意到 gg 是一个指数函数,大概是说当你被降智时做出 11 题和做出 44 题差异不大,但是超常发挥时做出 55 题和 66 题的差异要大得多。

换句话说就是超常发挥是让你高兴很久,发挥失常时只用伤心一会(???