CodeForces & AtCoder rating 规则简述

**译者：rui\_er，转载请注明出处。** （备份于[博客园](https://www.cnblogs.com/ruierqwq/p/17973570/cf-at-rating)） 本博客为了方便自己查阅，同时也方便大家了解，但因为我英语很菜，所以难免有翻译错的地方，还请评论区纠正。 未注明资料来源的均为常识积累。 # 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\]](https://codeforces.com/blog/entry/20762)。 假设每一个人原来的 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)](https://codeforces.com/contest/573) 以前，$\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](https://codeforces.com/contest/1/submission/13861109)。 ## 1.4 CodeForces rating 初始值 此部分资料来源：[Codeforces: Soon We Will Change the Rating Calculation for New Accounts](https://codeforces.com/blog/entry/77890)。 以前的初始值都是 $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 与名字颜色换算 见 [这里](https://record.ak-ioi.cf/show.html)。 蓝及以下记 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](https://www.dropbox.com/sh/zpgcogxmmu84rr8/AADcw6o7M9tJFDgtpqEQQ46Ua?dl=0&preview=rating.pdf)。 在每场比赛后，你都有一个 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$ 题的差异要大得多。 ~~换句话说就是超常发挥是让你高兴很久，发挥失常时只用伤心一会（？？？~~