【日本語翻訳】Atcoderレーティングの計算



この記事はAtcoder公式の[AtCoder Rating System ver. 1.00](https://www.dropbox.com/sh/zpgcogxmmu84rr8/AADcw6o7M9tJFDgtpqEQQ46Ua?dl=0&preview=rating.pdf)を、ChatGPTを使って翻訳した文です。原文がPDFなので、筆者がマークダウン記法での書式に整えて翻訳しました（[これ](https://drive.google.com/file/d/1Bjtse4G5mFLU9uF10ywQ4VqrzHVJqYC9/view?usp=sharing)）。

また、原文には書かれていませんが、最終的なレーティングの計算式も追加しました。
というのも、原文を参考にPythonで計算のシミュレーションをしたのですが、結果が一致しませでした。説明が不十分と感じ、[AtCoderのレート計算式](https://qiita.com/anqooqie/items/92005e337a0d2569bdbd#%E5%86%85%E9%83%A8%E3%83%91%E3%83%95%E3%82%A9%E3%83%BC%E3%83%9E%E3%83%B3%E3%82%B9%E7%AE%97%E5%87%BA%E5%BC%8F%E3%81%AE%E6%84%8F%E5%91%B3)の考察を参考にして再度計算してみたところ、無事結果が一致しました。数式の意味や細かい数学的な考察なども、[AtCoderのレート計算式](https://qiita.com/anqooqie/items/92005e337a0d2569bdbd#%E5%86%85%E9%83%A8%E3%83%91%E3%83%95%E3%82%A9%E3%83%BC%E3%83%9E%E3%83%B3%E3%82%B9%E7%AE%97%E5%87%BA%E5%BC%8F%E3%81%AE%E6%84%8F%E5%91%B3)にとても詳しく書かれていますので、ぜひ参考に。

以下本文です。

# Atcoderレーティングシステム ver. 1.00

## レーティングシステムの概要

このレーティングシステムは、Elo RatingのようにLogistic Distribution（またはSigmoid Function）に依存していますが、多くの修正が加えられています。各コンテストで「パフォーマンス」という値が得られます。この値は、コンテストでどれだけ良いパフォーマンスをしたかを表しています。過去のコンテストのパフォーマンスは`https://atcoder.jp/users/USERNAME/histor`で確認できます。

大まかに言うと、あなたのレーティングは、パフォーマンスの加重平均（最近のコンテストにはより多くの重みがあります）から、$f(レート対象のコンテストへの参加回数)$を引いたものとして計算されます。ここで、$f(1) = 1200$であり、$f$は徐々に減少してゼロに収束します。これは、$X$のパフォーマンスを維持し続けると、あなたのレーティングは$X - 1200$から始まり、$X$に収束するということを意味します。最初のコンテストで非常に低いレーティングを取っても心配しないでください。より多くのコンテストに参加すると、レーティングは非常に速く上がる可能性が高いです。10回以上のコンテストに参加した後は、あなたのレーティングが実力に近いものであると考えてよいでしょう。

## パフォーマンスの計算

内部的には、パフォーマンスには2種類あります：$Perf$と$RPerf$（Rounded Performance）。`https://atcoder.jp/user/USERNAME/history`に表示されている数字は実際には$RPerf$です。まず、各参加者について、$APerf$（Average Performance）を計算します。特定のユーザーの$Perf$（$RPerf$ではない）の履歴を$Perf_1, \cdots , Perf_k$としましょう。$Perf_1$は最新で、$Perf_k$は最も古いものです。この参加者の$APerf$は、以下のように定義されます。

$$
APerf=\frac{\sum_{i=1}^k Perf_i \times 0.9^i}{\sum_{i=1}^k 0.9^i} \tag{1}
$$

新参者の$APerf$は$Center$に設定されます。AGCでは$Center = 1200$、ARCでは$Center = 1000$、ABCでは$Center = 800$です。

参加者数を$n$とし、$i$位の参加者の$APerf$を$APerf_i$とします。このコンテストで$r$位のユーザーの$Perf$は、以下の条件を満たす唯一の$X$として定義されます。

$$
\sum \frac{1}{ 1+6.0^{ (X-A Perf_i )/ 400.0 } }=r-0.5 \tag{2}
$$

この$X$は二分探索を使用して計算できます。
順位は、同じ順位になった場合の平均となります。例えば、3位から6位まで4人が同じ場合、これらの人々の順位は4.5です。例外として、最初のコンテストでのパフォーマンスのばらつきが小さすぎるのを避けるため、最初のコンテストのパフォーマンスは以下のように誇張されます。

$$
 Perf=(Perf- Center) \times 1.5+Center \tag{3}
$$

最後に、各ユーザーの$RPerf$は以下のように計算されます。

$$
 RPerf=\min \( Perf, RATEDBOUND+400 \) \tag{4}
$$

ここで、$RATEDBOUND$はARCで2800、ABCで2000、AGCで∞です。
これは、ARCのいくつかのトップの人々のパフォーマンスがすべて3200であることを意味します。

## レーティングの計算

レーティングはパフォーマンスの平均です。
以下の関数を$f$としましょう：

$$
F(n)=\frac{\sqrt{\sum_{i=1}^n 0.81^i}}{\sum_{i=1}^n 0.9^i} \tag{5}
$$

$$
f(n)=\frac{F(n)-F(\infty)}{F(1)-F(\infty)} \times 1200 \tag{6}
$$

次に、以下の関数を$g$とします：

$$
g(X)=2.0^{\frac{X}{800}} \tag{7}
$$

この関数は、より良いパフォーマンスにより多くの重みを割り当てるために使用されます。したがって、非常に良いパフォーマンスとそこそこのパフォーマンスとの間には大きな差がありますが、大失敗と中程度の失敗との間の差はそれほど大きくありません。
特定のユーザーの$RPerf$の履歴を$RPerf_1 , . . . , RPerf_k$としましょう。このユーザーのレーティングは、以下のように定義されます。

$$
Rating=g^{-1}\left(\frac{\sum_{i=1}^k g\left(RPer f_i\right) \times 0.9^i}{\sum_{i=1}^k 0.9^i}\right)  \tag{8}
$$

この式により、各ユーザーのレーティングが計算されます。

## 補足

*※ここは原文にない補足部分です。この補足がないと、実際のレーティングの算出ができません。ただし、公式の情報からでなく、推測であることの断りを入れておきます。*

原文通りに計算すると、レーティング結果がどうしてもマイナスになってしまいます。そこで、400以下のレートを以下のようにマッピングすることで解決させます。

$$
mapRating(r) = 
\begin{cases}
    \frac{400}{\exp(\frac{400 - r}{400})} & ( r \leq 400 ) \\\\
    r & ( r \gt 400 )
\end{cases} \tag{9}
$$

最後に、コンテストの出場回数$n$に応じてレーティングの信頼度を調整する$f(n)$の項[（数式(6)）](#レーティングの計算)を追加して、真のレーティングを計算します。

$$
TrueRating = mapRating(Rating - f(n)) \tag{10}
$$

--- 補足おわり ---

---

## 色

執筆中。

## **段と級**

執筆中。現時点では、これが達成した最高のレーティングに依存するとだけ言っておきます。

## **このドキュメントの履歴**

- 2016年8月13日 Ver. 1.00：初版。