AtWaker Contestのレーティング

#AtWaker Contestとは

東大生のたまり場、バーチャル東大DiscordというDiscordサーバー（通称VUTD）にはAtWakerというbotがいます。そのbotが毎朝7:30～12:00に開催している、早起きレーティングコンテストがAtWaker Contestです。

```
毎朝7:30にAtWakerが
「おはようございます！ Good morning!
20yy-mm-ddのAtWaker Contest xxx開始です。
起きた人は下の「20yy-mm-dd」の
メッセージにでリアクションしてね。
徹夜勢の参加は禁止です。
一度寝てから出直してください。」
というメッセージを送信します。
その直後にAtWakerが「20yy-mm-dd」というメッセージを送信するので、
それに12:00までにでリアクションしてください。
時刻と各参加者の過去のパフォーマンスをもとに、
AtCoder Heuristic Contestの方法を少し改造した方法で
計算されたレーティングがコンテスト後に付与されます。
2回以上リアクションをしても、採用されるのは初回のみです。
```

2021/12/~~11~~12(2021/12/08にherokuの不具合があったせいでずれました)にAtWaker Contestは300回を迎えました。300回記念として（？）AtWaker Contestのレーティングの仕組みを解説します。

#概要

毎朝7:30～12:00にAtWakerのメッセージにリアクションを付けた人には、パフォーマンスと呼ばれる点数が付きます。参加した回のパフォーマンスを集計して、レーティングが算出されます。今回はパフォーマンスの計算方法、レーティングの集計方法を解説します。

#パフォーマンス

参加者が$n$人いるとします。早い順に参加者$1,\ldots,n$とします。参加者$i\ (i=1,\ldots,n)$がリアクションを押した時点から12:01:00までの秒数を$s\_i$秒とします。参加者$i$のランク$l\_i$を以下のように定めます。便宜上$l\_0=0$とします。

$$l\_i'=\frac{\max\_{1\leq j \leq n} (s\_j)-s\_i}{16200}\times n\ (i=1,\ldots,n)\\\\
l\_i=l\_i'-\frac{3l\_1'}{2}+\max\left(l\_1',\frac{1}{16200}\right)\ (i=1,\ldots,n)$$
$\\{l\_i\\}\_{i=0,\ldots,n}$は単調増加で、すべての項が非負です。

次に各参加者の過去パフォーマンスの重み付き平均$a\_i$を計算します。参加者$i$が前日までに$m\_i$回参加しているとします。$m\_i\geq 1$のとき、参加者$i$の過去パフォーマンスを時系列の逆順（新しい順）に$p\_{i,1},\ldots,p\_{i,m\_i}$とし、

$$a\_i=\frac{\sum\_{j=1}^m0.9^jp\_{i,j}}{\sum\_{j=1}^m0.9^j}$$
とします。初参加者については、$a\_i=1200$とします。

関数$f(x)$を
$$f(x)=\sum\_{i=1}^n\frac{l\_i-l\_{i-1}}{1+6^{\frac{x-a\_i}{400}}}$$
で定めます。$f(x)$は非負単調減少で、$\lim\_{x\to\infty}f(x)=0$です。参加者$i$の暫定パフォーマンス$P\_i'$は$f(P\_i')\leq l\_i$が成立する最小の整数です。最終的なパフォーマンス$P\_i$は以下の式で求められます。$\lfloor x\rfloor$は$x$を超えない最大の整数を表します。

$$M'=\frac{1}{n}\sum\_{i=1}^nP\_i',\ D'=\sqrt{\frac{1}{n}\sum\_{i=1}^n(P\_i'-M')^2}\\\\
M=1200+300\ln(n),\ D=800\ln(6)\\\\
P\_i''=\frac{D}{D'}(P\_i'-M')+M\\\\
P\_i=\left\\{\begin{array}{ll}
\lfloor P\_i''\rfloor&(P\_i''>400)\\\\
\left\lfloor 400\times e^{\frac{P\_i''-400}{400}}\right\rfloor&(P\_i''\leq 400)
\end{array}\right.$$

#レーティング

定数$W,S$を次のように定めます。この定数については後で解説します。

$$W=0.827197336426137,\ S=724.47443003358$$

参加者$i$の今回のパフォーマンスを$p\_{i,0}(=P\_i)$、過去パフォーマンスを時系列の逆順（新しい順）に$p\_{i,1},\ldots,p\_{i,m\_i}$とします。さらに、参加者が時系列の逆順（新しい順）に$d\_{i,0},d\_{i,1},\ldots,d\_{i,m\_i}$日前に参加していたとします。つまり、$0=d\_{i,0}<d\_{i,1}<\cdots<d\_{i,m\_i}$で、参加者は$d\_{i,j}$日前のAtWaker Contestでパフォーマンス$p\_{i,j}$を獲得し、$d\_{i,1}$日前、…、$d\_{i,m\_i}$日前以外の日は参加していないとします。修正パフォーマンス$p\_{i,j}'\ (i=1,\ldots,n,\ j=1,\ldots,m\_i)$を$p\_{i,j}'=0.99^{d\_{i,j}}p\_{i,j}$として定めます。これによって、不参加（あるいは開催中止）により1日当たりレーティングが約1%減少するようになっています。参加者$i$に対し、数列$\\{q\_{i,k}\\}\_{k=1,\ldots,100(m\_i+1)}$を以下のように定めます。

$$q\_{i,100j+l}=p\_{i,j}-S\ln(l)\ (j=0,\ldots,m\_i,\ l=1,\ldots,100)$$

$\\{q\_{i,k}\\}\_{k=1,\ldots,100(m\_i+1)}$を降順にソートしたものを$\\{q\_{i,k}'\\}\_{k=1,\ldots,100(m\_i+1)}$とします。暫定レーティング$R\_i'$は$\\{q\_{i,k}'\\}\_{k=1,\ldots,100(m\_i+1)}$の先頭100項の重み付き平均として計算されます。

$$R\_i'=\frac{\sum\_{k=1}^{100}W^kq\_{i,k}}{\sum\_{k=1}^{100}W^k}$$

最終的なレーティング$R_i$は以下のように計算されます。

$$R\_i=\left\\{\begin{array}{ll}
\lfloor R\_i'+0.5\rfloor&(R\_i'>400)\\\\
\left\lfloor 400\times e^{\frac{R\_i'-400}{400}}+0.5\right\rfloor&(R\_i'\leq 400)
\end{array}\right.$$

非参加者についても同様に計算します。（ただし、今回参加していないので、$p_{i,0},d_{i,0}$などは除いて計算します。）

###定数について

定数$W,S$は初参加者のパフォーマンスが$1600$以上のときにレーティングがパフォーマンスから$1000$を引いた値になり、なおかつ後述の$q\_{i,1}',\ldots,q\_{i,10}'$のレーティングへの寄与がちょうど全体の85%になるように調整したものです。具体的には、

$$\sum\_{k=1}^{10}W^k=0.85\sum\_{k=1}^{100}W^k\\\\
S=\frac{1000\sum\_{k=1}^{100}W^k}{\sum\_{k=1}^{100}W^k\ln(k)}$$

を満たすような$W,S$です。$W\neq 0,1$に注意して、一つ目の$W$の式を変形すると、

$$17W^{100}-20W^{10}+3=0$$

となります。$X＝W^{10}$とおくと、

$$17X^{10}-20X+3=0$$

となります。これは10次方程式であり、代数的には解けないので、[Halley's method](https://en.wikipedia.org/wiki/Halley%27s_method)で近似値を求めます。

$$F(X)=17X^{10}-20X+3$$

とすると、

$$F'(X)=170X^9-20,\ F''(X)=1530X^8$$

となります。

$$G(X)=X-\frac{2F(X)F'(X)}{2(F'(X))^2-F(X)F''(X)}\\
=\frac{26010X^{19}+24480X^{10}-5610X^9+120}{31790X^{18}+17000X^9-4590X^8+800}$$

初期値$X_0=0$として、$X_{i+1}=G(X_i)$を計算すると、

$$X_1=\frac{3}{20}=0.15\\\\
X_2=\frac{62914520938853327042075667}{419430125886693432194690620} \approx 0.15000000490153$$

となります。

$$f(X_2)\approx 4.10454\times 10^{-28}$$

なので、これで十分でしょう。

$$W\approx\left(\frac{62914520938853327042075667}{419430125886693432194690620}\right)^{\frac{1}{10}}\approx 0.827197336426137\\\\
S=\frac{1000\sum\_{k=1}^{100}W^k}{\sum\_{k=1}^{100}W^k\ln(k)}\approx 724.47443003358$$

となります。

#最後に

実装は[こちら](https://github.com/v-ut-d/atwaker)。ただし、チャンネルがVUTDのatwaker-駒場東大前チャンネルに固定されているため、適宜変更を加えないと他サーバーでは使えません。

みんなAtWaker Contestに参加してね！