【競プロ】プログラマーは何人集まれば王者 tourist に勝てるのか

8 min read読了の目安(約7600字

結果だけ知りたい方はこちら

はじめに

先日 AtCoder 上で UTPC 2020(東京大学プログラミングコンテスト)[1]という競技プログラミングのコンテストが開催された.本コンテストではチーム参加が可能であり,チーム参加規定は以下のものとなっていた.

3/14(日) ARC 後直後(3/26/19:27変更)の highest レーティングを R とし、 \max(0,R-1600) を個人のコストとする。チームメイトのコストの和が 2629 以下であれば、チームを組むことができる。
(同ページ[1:1]より引用)

これにより, Twitter などで「 Raring 1600 以下の人を大量に集めるチーム」などが見受けられた[2]
そこで本記事では,他のコンテストでも水色コーダーが大量に集まってチームが組めた場合,何人で tourist[3] に勝てるのか検証する.

おことわり

様々な制約をここで記載する.読み飛ばして構わない.

  • AtCoder のレーティングシステムに関しては公式PDF[4]に記載されている.非公式のQiita記事[5]ではこれを噛み砕いてわかりやすく記載されている.
  • tourist とは Google Code Jam[6] 7 連覇[7]の男性のことであり, AtCoder ではもっともレートが高い[3:1]
  • 今回用いる tourist のレートは彼の最高レート(2020/3/29 執筆時)である 4229 を用いる.また本記事では計算の簡略化のため,これを内部レートとして扱う.よって厳密には多少計算結果に誤差が生じる.
  • AtCoder で水コーダーとは,レート 1200 から 1599 のユーザーのことを指すが,本記事では計算の簡略化のためレート 1400 のユーザーのことを指すものとする.同じよう灰コーダーは 200, 茶コーダーは 600, 緑コーダーは 1000, 青コーダーは1800, 黄コーダーは 2200, 橙コーダーは 2600 として計算する.
  • 著者は前述のQiita記事[5:1]を参考にしているので,こちらの記事が間違っている場合は本記事も間違っている.本記事はあくまで参考程度のものである.

AtCoder の内部レートにおけるユーザー間の勝率算出式

詳しくは前述のQiita記事[5:2]の「内部パフォーマンス算出式の意味」節[8]を閲覧していただきたい.ここには内部パフォーマンスを算出するために内部レートを計算する必要があるが,初参加のユーザーの内部レートを計算するために特定のユーザー間の勝率を計算する必要がある.これはロジスティック分布で近似しているようだ.ここで, P はユーザー B に対するユーザー A の勝率を示す.

\begin{aligned} s &= \frac{400}{\log{e} 6}\\ P &= \frac{1}{1 + e^\frac{A \text{と} B \text{の内部レートの差}}{s}} \end{aligned}

これをプログラムに書き落とすとこのようになる.

C++
#include <iostream>
#include <cmath>
int main() {
    int userRateA = 1400; // ユーザー A のレート(例)
    int userRateB = 1600; // ユーザー B のレート(例)
    double rateDiff = userRateB - userRateA;  // ユーザー間のレート差

    double s = 400 / log(6);
    double winProbA = 1 / (1 + exp(rateDiff / s)); // ユーザー A の勝率
    double winProbB = 1 - winProbA; // ユーザー B の勝率
    std::cout << winProbA << std::endl; // 出力は 0.289898
    std::cout << winProbB << std::endl; // 出力は 0.710102
}

以下のサイト

https://paiza.io/projects/em82eEv-UhOTT6BQhe3u-w
で実際に実行してみることができる.

この計算式はレートの差のみで勝率を計算できる.レート差が 200 の場合,レートが高いユーザーの勝率は約 71 %である.

tourist VS 各色の競技プログラマーの 1 対 1 での勝率

上記のプログラムで各色のユーザーと tourist が 1 対 1 で勝負した場合,どれくらいの勝率で勝てるのか計算してみる.結果は以下の通り.

一般人のレート 一般人の勝率 touristの勝率
\textcolor{gray}{灰(200)} 0.0000015% 99.9999985%
\textcolor{brown}{茶(600)} 0.0000087% 99.9999913%
\textcolor{green}{緑(1000)} 0.0000523% 99.9999477%
\textcolor{cyan}{水(1400)} 0.0003137% 99.9996863%
\textcolor{blue}{青(1800)} 0.0018822% 99.9981178%
\textcolor{yellow}{黄(2200)} 0.0112922% 99.9887078%
\textcolor{orange}{橙(2600)} 0.0677150% 99.9322850%
\textcolor{red}{赤(3000)} 0.4049190% 99.5950810%
\textcolor{red}{赤(3400)} 2.3813024% 97.6186976%
\textcolor{red}{赤(3800)} 12.7676343% 87.2323657%

tourist の恐ろしさがよくわかる結果となった.

tourist VS 各色の競技プログラマーの 1 対 多 での勝率計算

本記事では tourist に勝てる人数 N を以下のような式で定義する.

\begin{aligned} f(P, X) &= \text{勝率}P\text{のユーザー}X\text{人と}\mathrm{tourist}\text{が}\\ &\text{同時にコンテストに参加し,}\mathrm{tourist}\text{が優勝する確率}\\ N &= f(P, X)\text{が}50\%\text{下回る最小の}X \end{aligned}

とします.ここで,ユーザーの勝率 P を固定した時に f(P, X) は広義単調減少となるので,二分探索が可能である.
また, f(P, X) に関しては以下のようにして計算可能である.

  1. (1 - \text{ユーザーの勝率}) で 1 対 1 での tourist の勝率が計算可能である
  2. tourist が同じレートの相手に 2 連勝する確率は P_t = (1 - \text{ユーザーの勝率}) とした時, P_t^2 である.一般的に同じレートの相手に N 連勝する確率は P_t^N であり,またレート R_1, R_2, R_3, \dots, R_N のユーザー全員に勝つ確率は P_t^{\prime} = \prod_{i=1}^N (1 - R_i) で計算できる

これにより,勝率 P のユーザー X 人が tourist に勝つ確率は1 - f(P, X)と計算できる.

計算結果

ユーザーの
レーティング
ユーザー個人の
勝率
touristに勝つために
必要な人数
AtCoderの
ユーザー数
(2020/3/29 執筆時)
\textcolor{gray}{灰(200)} 0.0000015% 47725879人 61401人
\textcolor{brown}{茶(600)} 0.0000087% 7954314人 12573人
\textcolor{green}{緑(1000)} 0.0000523% 1325720人 8701人
\textcolor{cyan}{水(1400)} 0.0003137% 220954人 4741人
\textcolor{blue}{青(1800)} 0.0018822% 36826人 2380人
\textcolor{yellow}{黄(2200)} 0.0112922% 6138人 1142人
\textcolor{orange}{橙(2600)} 0.0677150% 1024人 333人
\textcolor{red}{赤(3000)} 0.4049190% 171人 154人
\textcolor{red}{赤(3400)} 2.3813024% 29人 27人
\textcolor{red}{赤(3800)} 12.7676343% 6人 9人
計算に用いたプログラム
C++
#include <iostream>
#include <cmath>
typedef long long int ll;
// xのn乗を計算
double fast_pow(double x, ll n) {
    double res = 1.0;
    while (n > 0) {
        if (n & 1) res = res * x;
        x = x * x;
        n >>= 1;
    }
    return res;
}

// 一般ユーザーの人数とtouristの勝率から,touristが50%以上の確率で勝てるか判定する
bool isTouristWin(double touristWinProb, ll userNum) {
    return fast_pow(touristWinProb, userNum) >= 0.5;
}

int main() {
    for (int rating = 200; rating < 4000; rating += 400) {
        int userRate = rating;   // ユーザー A のレート
        int touristRate = 4229;  // tourist のレート
        double rateDiff = touristRate - userRate;  // ユーザー間のレート差

        double s = 400 / log(6);
        double userWinProb = 1 / (1 + exp(rateDiff / s));  // ユーザー A の勝率
        double touristWinProb = 1 - userWinProb;           // tourist の勝率
        printf("ユーザーのレーティング: %d\n", rating);
        printf("勝率: %.7f%% %.7f%%\n", userWinProb * 100,
               touristWinProb * 100);

        // touristに勝つために必要な人数を二分探索する
        ll ok = 1LL << 60;  // ユーザーが絶対勝てる人数=INF
        ll ng = 1;          // ユーザーが絶対勝てない人数
        while (abs(ok - ng) > 1) {
            ll mid = (ok + ng) / 2;
            if (isTouristWin(touristWinProb, mid)) {
                ng = mid;
            } else {
                ok = mid;
            }
        }
        printf("必要な人数: %lld人\n", ok);
        printf("ユーザーの勝率: %.7f%%\n\n",
               (1 - fast_pow(touristWinProb, ok)) * 100);
    }
}

以下のサイト

https://paiza.io/projects/E59JD8xf4oz-g0FEqxxJqw
で実際に実行してみることができる.

例えば水コーダーだと 22 万人も集結しないと tourist に 50% の確率で勝てないようだ.
忘れてしまいそうだが,水コーダーは

半数以上のIT企業において、アルゴリズム能力についてはカンストと言えるでしょう。特にアルゴリズム的な能力を必要としない会社であれば、ここから上はレートを上げても実務に役立つ部分はほとんどありません。
(chokudai社長のブログ[9]より)

の能力を持つ競技プログラマである.また,赤コーダー(3000)でも 171 人,「三人いれば文殊の知恵」って言葉とは......

おわりに

本記事でおこなった計算は各所で概算がされている.例えば実レートと内部レートが同じものとして計算を行ったり,水コーダーは全員レート 1400 としたりしている.よって必ずしも正確ではないことを十分承知いただきたい.

(ちなみになんですが, tourist 倒すのに必要な灰コーダーの人数が日本の人口の約半分ってやばくない??戦国時代の戦に例えてみて,武将 tourist が日本の半分の人間を斬ってる姿を想像するとかなりシュールでした.)

脚注
  1. https://atcoder.jp/contests/utpc2020 ↩︎ ↩︎

  2. https://twitter.com/evima0/status/1373654460589690881 ↩︎

  3. https://atcoder.jp/users/tourist ↩︎ ↩︎

  4. https://www.dropbox.com/sh/zpgcogxmmu84rr8/AADcw6o7M9tJFDgtpqEQQ46Ua?dl=0&preview=rating.pdf ↩︎

  5. https://qiita.com/anqooqie/items/92005e337a0d2569bdbd#fnref1 ↩︎ ↩︎ ↩︎

  6. https://codingcompetitions.withgoogle.com/codejam ↩︎

  7. https://en.wikipedia.org/wiki/Google_Code_Jam ↩︎

  8. https://qiita.com/anqooqie/items/92005e337a0d2569bdbd#fnref1 ↩︎

  9. http://chokudai.hatenablog.com/entry/2019/02/11/155904 ↩︎