👨‍👨‍👦‍👦

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

2021/03/29に公開

競技プログラミング

math

tech

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

はじめに

先日 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
}

以下のサイト

で実際に実行してみることができる．

この計算式はレートの差のみで勝率を計算できる．レート差が 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 - \text{ユーザーの勝率})$ で 1 対 1 での tourist の勝率が計算可能である
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);
    }
}

以下のサイト

で実際に実行してみることができる．

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

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

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

おわりに

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

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

GitHubで編集を提案