CodeForces & AtCoder rating 规则简述

您所在的位置：网站首页 › codeforces教育场是什么意思 › CodeForces & AtCoder rating 规则简述

CodeForces & AtCoder rating 规则简述

2024-06-15 09:13| 来源: 网络整理| 查看: 265

译者：rui_er，转载请注明出处。

（备份自 2020 年 11 月 2 日的同名博客）

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

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

1 CodeForces rating 规则 1.1 CodeForces rating 与名字颜色换算

设 \(r\) 表示 rating，则 CodeForces 的名字颜色有以下几等：（从低到高）

黑色不加粗（代码 #000000）：Unrated，没有参加过比赛。黑色（代码 #000000）：Headquarters，管理员。灰色（代码 #808080）：Newbie，\(r\lt 1200\)。绿色（代码 #008000）：Pupil，\(1200\le r\lt 1400\)。青色（代码 #03a89e）：Specialist，\(1400\le r\lt 1600\)。蓝色（代码 #0000ff）：Expert，\(1600\le r\lt 1900\)。紫色（代码 #aa00aa）：Candidate Master，\(1900\le r\lt 2100\)。橙色（代码 #ff8c00）：Master，\(2100\le r\lt 2300\)。橙色（代码 #ff8c00）：International Master，\(2300\le r\lt 2400\)。红色（代码 #ff0000）：Grandmaster，\(2400\le r\lt 2600\)。红色（代码 #ff0000）：International Grandmaster，\(2600\le r\lt 3000\)。首字母黑色+红色（代码 #ff0000(:first-letter 伪类为 #000000)）：Legendary Grandmaster，\(r\ge 3000\)。 1.2 CodeForces rating 与是否计入比赛（及比赛赛制）

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

Div.4：\(r\lt 1400\)，exICPC 赛制。 Div.3：\(r\lt 1600\)，exICPC 赛制。 Div.2 Only：\(r\lt 2100\)，CF 赛制。 Div.2：\(r\lt 1900\)，CF 赛制。 Div.1：\(r\ge 1900\)，CF 赛制。 Educational Round：\(r\lt 2100\)，exICPC 赛制。 Global Round：\(\rm{Rated\ for\ all}\)，CF 赛制。其他比赛：见赛前通知。 1.3 CodeForces rating 在 rated 比赛中的计算

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

假设每一个人原来的 rating 为 \(r_i\)，则根据以下公式计算 \(i\) 在比赛中得分高于 \(j\) 的概率：

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

因此我们可以由两人的 rating 差值算出他们其中一个比另一个得分高的期望概率。例如，如果两个人的 rating 差为 \(200\)，则 rating 高的人赢过另一方的概率被认为是 \(0.75\)；若 rating 差为 \(400\)，则这一概率约为 \(0.9\)。

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

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

例如，在 Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 1) 以前，\(\textsf{t\color{red}ourist}\) 的 rating 为 \(3503\)，因此期望排名约为 \(1.7\)；\(\textsf{P\color{red}etr}\) 的 rating 为 \(3029\)，因此期望排名约为 \(10.7\)。

一般的想法就是，如果实际排名比 \(seed_i\) 更靠前，增加 rating；反之减少。

这里计算出 \(seed_i\) 与实际排名的几何平均数：

\[m_i=\sqrt{seed_i\times rank_i} \]

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

不过我们为了让 rating 的平均变化更接近 \(0\)，还需进行以下微调：

定义一个数 \(inc\)，让所有 \(d_i\) 增加 \(inc\)。

第一次微调：

\[inc=\frac{-1-\sum{d_i}}{n} \]

保证所有人的平均变化接近 \(0\) 但在 \(0\) 以下。

第二次微调：

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

CodeForces rating 计算的源码地址：Link。

1.4 CodeForces rating 初始值

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

以前的初始值都是 \(1500\) 分，但在 2020.(5~6) 前后，CodeForces 更改了 rating 规则。

新注册的号（或未打过比赛的号）的初始 rating 是 \(0\) 而不是 \(1500\)。

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

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

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

前六场比赛都是类似的方法，每次加的数是 \(500,350,250,150,100,50\)，总和为 \(1400\)。

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

2 AtCoder 规则 2.1 AtCoder rating 与名字颜色换算

见这里。

蓝及以下记 20~1KYU，数字越小等级越高；黄及以上记 1~10DAN，数字越大等级越高，再高就是 legend 和 king 之类的，这部分不太清楚。

2.2 AtCoder 可参加比赛的 rating

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

一般地：

ABC：\(0\le r\lt 2000\)。 ARC：\(0\le r\lt 2800\)。 AGC：\(r\ge 1200\)。

2021.2.25 更新：AHC 最新的一系列比赛，还没开始，暂时不详。

更新：AHC 计算 rating (β)，不是一个体系，且与 OI 不太相关，因此不翻译。

2.3 AtCoder rating 在 rated 比赛中的计算

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

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

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

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

\[APerf=\frac{\sum_{i=1}^kPerf_i\times 0.9^i}{\sum_{i=1}^k0.9^i} \]

对于没打过比赛的萌新来讲怎么办？我们设置 \(Center\) 作为 \(APerf\)：

\[Center=\begin{cases}800,&ABC\\1000,&ARC\\1200,&AGC\end{cases} \]

令 \(n\) 为参赛人数，\(APerf_i\) 表示 \(i\) 的 \(APerf\) 值，则排名为 \(r\) 的人的 perf 记为 \(X\)，为下面方程的解：

\[\sum_{i=1}^n\frac{1}{1+6.0^{\frac{X-APerf_i}{400.0}}}=r-0.5 \]

对于并列的人，\(r\) 取他们 rank 的平均值。

对于第一场比赛，进行特判：

\[Perf=(Perf-Center)\times 1.5+Center \]

最后，真实的 perf 计算如下：

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

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

计算完了 perf，让我们一起计算一下 rating！

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

是的就是这个意思。

定义以下函数：

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

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

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

则：

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

注意到 \(g\) 是一个指数函数，大概是说当你被降智时做出 \(1\) 题和做出 \(4\) 题差异不大，但是超常发挥时做出 \(5\) 题和 \(6\) 题的差异要大得多。

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

【本文地址】

公司简介

联系我们