どうもこんにちは。明日には青コーダーになってたらいいな相馬です。今回もまず結論です。
atcoderの配点とdifficultyの関係の経時的変化を分析すると、ABC212-320(GPTが4以前つまり雑魚だった時代)から得られる回帰モデルとの残差は他の期間と比較するとABC391-410(とりわけABC391-400)で負方向に大きい → o3-mini等の無料使用可能かつ高度な推論が可能な生成AIの登場によりdifficultyにして100弱の急激なインフレが起きた可能性がある。
※幸いABC401-410ではこの残差は縮小しており(つまり元のインフレ度合いに戻りつつある)、chokudai御代の 鬼BAN 苛烈ながんばりが功を奏しているのかもしれません
今回はリサーチレターです（私自身はまだ研究者としてレターを書いたことはないので形式等が合ってるかよくわかりません。そして書いているうちに前回と同じようなボリュームになってしまいました）。以下、大規模言語モデルや推論モデルを用いた生成AIのことをAIと呼びます。また、AtCoderProblemsにおける生difficultyのことをdifficultyと呼びます(生difficultyは負の値を取りうるため、一応difficulty400以上の生difと補正後difが同じになる問題だけでも調べて、傾向に差が無いことを確認しています)。同一レートやパフォーマンスを比較した場合、過去よりも現在のほうが高い実力を示すという意味でレートの価値は上がっているためデフレでは?という向きもありますが、参加者の実力のインフレーション(膨張)という意味でインフレという表現で統一します。
[著者略歴]
精神科医、博士。市中病院で臨床やりつつ協力研究員として脳波研究の主にプログラミング部分を担当。医学部卒業半年前に休学し1年間独学でプログラミングを勉強、その後もwebアプリや研究用のスクリプトを個人的に作っては仲間内で細々と使っています。2022年春にセキスペ合格(FE,APも合格済)。AtCoderは2022年2月に始めて、ABCのdifficulty2200以下問題は全問ACし、半分以上は2,3回復習していますがまだ青にすらなれていません。職業柄もありPythonユーザー。
コンテスト中は背後からwebカメラをつけることで弱い自分を律しています。しかしいつか夜神月堕ちするのかもしれません。
前回記事「生成AIはAtCoderBeginnerContestを実際に破壊しているのか」は建設的批判も含め大変ご好評いただき、感謝しています。長期レート安定の基準をより厳格にする、レーティング変動ではなくパフォーマンスで比較するなど手法を改善したアレの修正版も出したいのですが、今回はatcoder実力インフレにAIが与えた影響を分析する記事です。
まず前提として、atcoder参加者の実力は過去から現在に至るまでひたすらインフレし続けています。つまり
- 同一レートであれば過去よりも現在の方が高い実力を示す(前述の通りレートの視点で言えばデフレでは?…)
- 使用アルゴリズムやテクニック等から同程度の難易度と判断しうる問題の正答率は上昇し続けており、解けた人間のレート分布の平均値や中央値は低下し続けている
が成り立ちます。ただこのインフレ幅には議論の余地があるようで、
ということで今回はこのインフレ幅に関する分析です。後述しますがAI以前のインフレ幅の分析は手法的に難しかったのでAIのインフレ幅に与えた影響が主な分析対象です。結論から言ってしまえばchokudai御代の感覚に合致する100以下であるとして良いでしょう。つまりAI以前であれば年50程度インフレが起きていたのが、(問題構成の変化や特定集団の急激な流入などの環境変化が無かったと仮定すれば)o3-miniやgemini 2.5pro出現で短期間に急激に100弱のインフレが起きた、ということです。そして、吉報ですがchokudai御代の苛烈ながんばり(鬼ban)によりABC401-410についてはそのインフレの影響は割と緩和されていそうです。
今回の分析のアイデアと流れを先にまとめておきます。だらだらと長い割にまとまりに欠くので読み飛ばして頂いてもいいです。
- atcoder probremsを使って過去問精進をしている限りdifficultyにして年50-100程度のインフレは以前から感じているが正確な数字は不明。それにしてもo3-mini以降のインフレはさすがにエグすぎる気がする
- AI以前のインフレ率が算出できAI以降のインフレ率と比較できれば一石二鳥
- インフレ率を算出するには、アルゴリズムやテクニックから同程度の難易度と判断される問題を集める必要があるがここがまずネック。Novistepsの判断を使わせていただく手も考慮したが、今回はシンプルに配点を難易度の目安とする。配点設定のガイドラインは不明だが、解いてる個人的感覚からは配点と解法難度が大幅に乖離することは少ない印象
- まずAI以前のインフレ率を調べるために、difficultyの説明変数となりそうな配点、日付(基準日からの経過日数)、参加者数を集めてこよう
- difficultyを被説明変数として、配点、日付、参加者数を説明変数として重回帰分析をしてみる → 配点の寄与が圧倒的で日付、参加者数はほぼ無影響 → 配点のみを説明変数とした場合の残差を被説明変数として、日付、参加者数を説明変数として回帰分析してみても無相関
- つまり配点にはインフレが織り込まれているということ?…どうしよう…
- 発想を変えて、AIの影響がほぼ無い時代の回帰モデルを用いて未来のdifficultyを予測してみて、その予測との乖離がo3-miniの出現に合わせて急激に大きくなればo3-miniによるインフレと言うことができるのではないか
- 当たり
今回もGPT-4o様が共著者です。それではお楽しみ下さい。
著者：Daiki Soma (MD), GPT-4o (AI)
データ：
AtCoder Problems API: Estimated Difficulties of the Problem
AtCoder Problems API: Detailed Problems Information
AtCoder社のコンテストごとの順位表データ（例：ABC410）
利益相反：開示すべきCOIはありません。
Introduction
AtCoder社等が提供する競技プログラミングオンラインコンテストでは、生成AI(以下AI)の性能向上により典型問題を中心に回答の速度や正確性で人間がAIに完全に負ける事案が目立つようになっており、その使用が禁止されているにも関わらずコンテスト中にAIを使用していると考えられる人間が多数観測されている。（注：禁止されているAI使用は、競技性を低下させレートの価値を毀損する行為であり、AtCoder社がコンテスト開催の協賛募集、レーティング等をもとにした人材紹介業をビジネスモデルとしている以上、損害賠償責任を問われかねない行為に該当しうる。）
AIの性能が十分に向上する以前から競技プログラミング継続参加者の実力は、学習環境の向上などもあってか上昇し続けており(以下この現象をインフレと表現する)、要求されるアルゴリズムやテクニックが同程度の問題のdifficulty(AtCoderProblemsにおける難易度推定値、詳細解説リンク)は年50程度下がることが知られている(1)。しかしAI、とりわけo3-mini, gemini 2.5 pro, deepseek R1などの無料利用可能な推論モデル出現(2)によりインフレが急激に加速した可能性があり、その寄与を推定することはAIのコンテスト及びレーティングに与える影響の大きさを定量化するとともに、AIを使用していない個人の実力把握を正確にする一助となりうる。
今回我々は、AI以前の配点、時間経過、参加人数とdifficultyの関係から得られた回帰モデルを直近までのコンテストに適用し残差を調べることで、推論モデル普及以降にこの残差が負方向に急激に大きくなる現象が見られるかを確認した。前提として推論モデル普及以降と設定したAtCoderBeginnerContest(以下ABC)391以降に配点や問題構成に大幅な変更が無くかつAI使用者以外の特定の集団の急激な流入等の環境変化が無かったと仮定している。
- chokudai “ちなみに年50-100というのは、問題が２つ与えられて、どちらの方が難しいか予想するクイズを昔有志がつくっていて、それの回答結果をもとに推定したものになります”
- AI timeline
Methods
前述のデータから、コンテスト名(ABCのみ)、問題番号(ABC410_Eなど)、difficulty、配点、経過日数(ABC212を0日とした場合のコンテスト日)、コンテスト参加者数(一度でも回答を提出した人数)を抽出し、abc212-410の計1484問分のデータを得た。difficulty2400以上の問題については現時点でもAIが安定して解けないため除外し、1275問について解析を行った(インフレを前提にすればdifficulty2400自体が一律の判定基準とならない可能性も考慮し、配点600点以上を除外基準として解析も行ったが同様のResultであることを確認している)。
GPT-4リリース前(2)をAIがABCに与える影響が十分に小さかった時期と見做し、ABC212からABC320までのコンテストについて、被説明変数としてdifficultyを、説明変数として配点、経過日数、参加者数を設定し重回帰分析を行った。当然ながら配点の影響が非常に大きかったため、配点のみで単回帰分析を行ったうえで残差を求め、その残差を被説明変数、経過日数、参加者数を説明変数とした重回帰分析も行った。
前者の回帰モデルを用いて、ABC212からABC410までのすべてのデータについて残差([実際のdifficulty] – [配点,経過日数,参加者数から予測されるdifficulty])を求めた。ABC391から410までの残差と、ABC380-390(生成AI禁止以降かつo3-mini以前)、ABC338-357(1年前同時期)、ABC287-306(2年前同時期)、ABC233-252(3年前同時期)の残差を比較しt検定を行った。多重比較にあたるためBH法を用いて補正を行った。（重回帰分析、残差分析から経過日数、参加者数は説明変数として意味をなさないと分かり配点のみの単回帰モデルでも同様の解析を行ったが、同様のResultを確認）
この選定された時期が特異でないことを確認するために、ABC321以降、10回ごとにまとめる形で残差の分布を確認した。
Results
ABC320以前の回帰分析結果
ABC212からABC320の解析については、配点、経過日数、参加者数を説明変数とした重回帰分析では以下のように配点との強い正の相関(coef=6.36,p
Table1
| 変数 |
係数（coef） |
標準誤差（std err） |
t値 |
p値 |
95%信頼区間 |
| 定数 |
-1690.74 |
72.61 |
-23.29 |
0.000 |
[-1833.31, -1548.18] |
| 配点 |
6.36 |
0.072 |
87.91 |
0.000 |
[6.22, 6.51] |
| 経過日数 |
-0.006 |
0.061 |
-0.097 |
0.923 |
[-0.126, 0.114] |
| 参加者数 |
0.010 |
0.009 |
1.182 |
0.237 |
[-0.007, 0.027] |
経過日数および参加者数との相関が薄いことは配点のみを説明変数とした単回帰モデルの残差に対し経過日数、参加者数を説明変数として重回帰分析を行った場合でも同様であった(R^2=0.003)。
Table2
| 変数 |
係数（coef） |
標準誤差（std err） |
t値 |
p値 |
95%信頼区間 |
| 定数 |
-87.85 |
67.50 |
-1.30 |
0.194 |
[-220.37, 44.67] |
| 経過日数 |
-0.006 |
0.061 |
-0.097 |
0.923 |
[-0.125, 0.114] |
| 参加者数 |
0.010 |
0.009 |
1.183 |
0.237 |
[-0.007, 0.027] |
全期間に対する残差分析、ABC391-410との比較
前者の重回帰分析から得られた回帰モデルをABC410までの全データに適応することで残差([実際のdifficulty] – [配点,経過日数,参加者数から予測されるdifficulty])を求め、各期間の残差を比較した結果、すべての期間と比較してABC391-410の残差が有意に小さいことを確認した。
Figure1 : 特定5期間におけるABC212-320回帰モデルに対する残差。プロット、平均値、95%CI
ABC391-410の残差平均は他期間と比べて有意に小さい
Table3
| vs abc391-410 |
Mean Difference |
t-value |
p-value |
p-value (after correction) |
95% CI |
Cohen’s d |
| abc233-252 |
102.8930 |
3.1505 |
0.001847* |
0.003694* |
[38.88, 166.91] |
0.388260 |
| abc287-306 |
81.4541 |
2.4063 |
0.016965* |
0.016965* |
[15.11, 147.80] |
0.301428 |
| abc338-357 |
119.8844 |
4.1284 |
0.000050* |
0.000200* |
[62.97, 176.80] |
0.514874 |
| abc380-390 |
88.7443 |
2.5903 |
0.010752* |
0.014336* |
[21.59, 155.90] |
0.393582 |
Table4
| Period |
N |
Mean |
StdErr |
95% CI |
| abc233-252 |
132 |
-23.8202 |
27.0726 |
[-77.38, 29.74] |
| abc287-306 |
126 |
-45.2591 |
28.4981 |
[-101.66, 11.14] |
| abc338-357 |
127 |
-6.8287 |
22.5737 |
[-51.50, 37.84] |
| abc380-390 |
69 |
-37.9689 |
28.9842 |
[-95.81, 19.87] |
| abc391-410 |
131 |
-126.7132 |
18.2676 |
[-162.85, -90.57] |
回帰モデルの適合と該当期間のみが特異であることの確認
選択した期間が特異でないこと、回帰モデルの精度が十分であることを確認するためABC321から10回づつのデータをまとめたプロットを作成し、ABC391-400のみが特異であることを確認した。
Figure2 : ABC321以降におけるABC212-320回帰モデルに対する残差。プロット、平均値、95%CI
ABC391-400だけが回帰モデルの予測から大きく外れる
Table5
| Group |
Count |
Mean |
Std |
Min |
25% |
50% |
75% |
Max |
| abc321-330 |
62.0 |
-41.111 |
240.910 |
-562.157 |
-225.006 |
-42.085 |
118.058 |
450.708 |
| abc331-340 |
63.0 |
-62.789 |
235.729 |
-668.624 |
-233.116 |
-104.666 |
102.927 |
470.526 |
| abc341-350 |
65.0 |
21.938 |
255.648 |
-568.807 |
-138.177 |
50.908 |
150.781 |
651.302 |
| abc351-360 |
63.0 |
-51.053 |
243.825 |
-598.994 |
-184.345 |
-90.618 |
84.653 |
692.397 |
| abc361-370 |
63.0 |
-14.077 |
233.341 |
-503.457 |
-162.029 |
7.840 |
121.480 |
696.205 |
| abc371-380 |
66.0 |
-54.746 |
241.656 |
-538.313 |
-224.699 |
-63.493 |
129.668 |
623.255 |
| abc381-390 |
62.0 |
-37.888 |
246.277 |
-429.838 |
-198.051 |
-99.964 |
118.655 |
632.751 |
| abc391-400 |
64.0 |
-171.995 |
223.982 |
-756.397 |
-325.966 |
-180.075 |
-29.037 |
424.812 |
| abc401-410 |
67.0 |
-83.459 |
185.285 |
-514.006 |
-183.869 |
-91.881 |
47.751 |
366.848 |
Discussion
今回我々はAI以前の配点、時間経過、参加人数とdifficultyの関係をもとにAI以降の各問題の配点、時間経過、参加人数からdifficultyを予測し、その残差がABC391-410において他の期間と比較し100弱低下していることを確認した。この低下は該当期間以外では観測されず、またいずれの比較対象期間とも統計学的な有意差を認めた。
この結果からAtCoderBeginnerContestにおけるdifficulty2400未満の問題について、difficultyがABC391以降急激に100弱低下したことが確認でき、この期間に配点や問題の特殊性が無くかつAI使用者以外の特定の集団の急激な流入等の環境変化が無かったと仮定するならば、AI、特に無料利用可能かつ高性能な推論モデルによる急激な実力インフレが発生したと解釈しうる。
本研究の限界として、配点を普遍的な難易度指標としているが残差分析の結果からは配点はインフレを織り込んで設定されている可能性があり普遍的な難易度指標としての妥当性が低い可能性がある。ただし回帰モデルの説明力は非常に高く、また実際に該当期間以外では残差の平均はゼロから大きく乖離することは無いため、特定期間の特異性を洗い出す手法としては妥当性に問題は無い。
Figure2から分かる通りABC401-410については391-400と比較すれば残差は再びゼロに近づいており、AIの影響はある程度除去されてきていると言える。
AIを使用していないABC参加者は推論モデル出現以降、とりわけABC391-400において本来の実力よりも低くパフォーマンスを評価された可能性が高いが、AtCoder社の対策等によりABC401以降はその幅が縮小していると考えられ、AIのレーティングに与える影響を過大に見積もり悲観的になる必要は無いと言える。
鬼BANされている割には明確に誤BANだと騒いでいる張本人というのは少なくとも僕は観測したことがなく、またAtCoder社がある程度歴史も信用もある企業であることからも、BANアルゴリズムについては感度は低いものの特異度は極限まで高いものになっていると推察されます。なので誤BANで騒ぐ必要も焦る必要も全く無いと考えます。何より今回の解析から鬼BANの威力とメリットを結構感じられたのでコンテストの健全性を極力保つためにもchokudai御代にはこの調子で苛烈に頑張っていただきたく存じます。
また、医師である私のレートに社会的価値は根本的に無く、従って実力証明のためのプレイ録画もする意味は無いと考えていたのですが、セールで買った見守りカメラの使い方が終わっていたので前々回から背後につけるようにしています。
つけてみてわかったのですが、これはとてもいいです。ABC377以降レートへのこだわりは消えていたのですが、これをつけるだけで何故か377以前の緊張感が戻ってきます。やはり自身のレートに客観的価値があると信じられる世界線のほうが楽しいに違いありません。おすすめです。
データ及びソースコード
コンテスト名、問題名、difficulty、配点、経過時間(unix time)、参加人数のデータ
解析用ソースコード
おまけ：ダン・アリエリー「ずる」から見る不正対策
「予想通りに不合理」の著書で有名な行動経済学者ダン・アリエリーの本に「ずる」というやつがあります(わたしのブクログレビュー)。
これによれば人は合理的犯罪モデルに従い不正をするわけではなく、自分を悪だと見做さないで済む範囲、具体的には10-20%下駄をはく程度の不正を大半の人間が行うということだそうです(ちなみに興味深いことにレート2000未満の各人のレートの10%にあたる数値の平均値を概算してみたら114.14でした)。
不正を増やす要素として、仲間の皆が不正をしている状況、一度不正に手を染めた、創造性が高く自分への言い訳が上手、疲れているなどがあり、逆に不正を減らす要素として監視(最強らしいです)、道徳心を思い起こさせる、正直であると事前に宣言させるなどがあるとのこと。
この著書の内容を参考にするならば、まず皆がどこかに投稿する必要は無いにしても見守りカメラや画面録画を基本的に使用するようにする、参加前に不正行為を行わないという宣言に署名させる(損害賠償責任というパワーワードも是非!)、不正の影響はBANにより縮小されてきているため皆が不正をしている状況には無いと宣伝する、などが不正対策として有効と考えられます。
あと、著書内で取り上げられていた面白い実験として、”回答が下の方に小さく刷ってありチラ見えするけど一応見ないで解きましょうという体で算数の問題を解いた群”は、”回答刷りなし群”より得点が高いにもかかわらず”回答が堂々刷ってある群”と比較して「自分の能力で解いた」と捉える傾向が強かったようです(追記:読み返したら正確には”回答が堂々刷ってある群”との比較ではなく、第二段階として2群に次回何点とれるかを予想させる方法で検証していました)。露骨GPTerは別として、隠れGPTerの中にはGPTのおかげで上がったレートを自分の能力と勘違いしてしまった哀れな方も多いのかもしれませんね。行き着く先は虚栄心を保つための利用拡大そして最後はBANです。
まあこの著書で取り上げられている研究にはデータ操作疑惑や再現性の問題など指摘され撤回された論文もあるのですが…（詳細解説）自分でも10%程度のずるをする、高度に教育的です。
おわり
