AtCoderの問題難易度を項目反応理論を用いて推定する

はじめに

AtCoder競技プログラミングのサイトです。ほぼ毎週のようにコンテストが開催され、参加者が複数の問題を解き、解いた問題数とその早さから順位がつきます。また各参加者はレーティングを持っていて、そのレーティングが順位によって変化するというシステムになっています。

コンテストの問題には100,200,300などの得点がついており、これが難易度の目安となるのですが、同じ400点の問題でもこれは簡単すぎでは?というときから絶対無理…となるときもあるので、実質の難易度は得点とは少しずれが生じていると考えられます。

特にAGC(AtCoder Grand Contest)や企業コンテストは通常のABC(Atcoder Beginner Contest)やARC(Atcoder Regular Contest)と同じ得点でも難易度が結構異なるように感じます。

今回はこのテーマに対し、項目反応理論を用いて問題の難易度推定を行いたいと思います。

関連研究

競技プログラミングの難易度推定について、探したら前例がいくつか出てきました。

下記2つの記事では今回用いる項目反応理論を用いた推定を行なっており、参考にさせていただきました。

項目反応理論について

テストによって学力を測定する場合、得点や偏差値等の数字は受験者集団や問題難易度によって変わるため、 絶対的な値を測ることができません。 項目応答理論はそれらが変わっても同じように評価ができるように考えらた理論であり、 この特性からTOEFLや日本語検定などでも使用されています。

AtCoderが問題を提供しているTOPSICというプログラミング能力を測れるサービスでも項目反応理論を使っているらしいです。

項目反応理論の式はいくつかあるのですが、今回は 2パラメータロジスティック(2PL)モデルと呼ばれる以下の式を用います。

P _ { j } ( \theta ) = \frac { 1 } { 1 + \exp \left( - 1.7 a _ { j } \left( \theta - b _ { j } \right) \right) }

この式でPは正解率、\thetaが個人の能力値、bが困難度、aが識別力を示し、 ユーザごとの正解、不正解のデータからこれら3つのパラメータを推定します。

大層な名前がついていますが、使うだけならやることはただのロジスティック回帰です。

方針

今回は項目反応理論を用いてAtCoderの問題難易度の推定をしていきます。

データはAtCoderの順位表のページから取得します。 Atcoderは順位表のページのURLに/jsonを追加するだけでjsonファイルが拾えるので非常にありがたいです。

対象コンテストは私が最近参加したAGC29、全国統一プログラミング王決定戦予選、みんなのプロコン 2019の3つにします。

項目反応理論では能力値のパラメータ\thetaは推定するものですが、 Atcoderでは参加者ごとにレーティングが付与されているため、このレーティングをそのまま使うことにします。 (使用するレーティングはコンテスト参加時のものです。)

コンテストへの参加回数が少ない場合、レーティングは実際の実力と乖離する可能性が高いため、 今回の実験ではコンテストの参加回数が20回以上のユーザを対象とします。

一度も提出をしていないユーザはコンテストに参加していないことになるため、 提出0のユーザは除外します。また提出していないものはすべて不正解とみなします。

実装

拾ってきたjsonファイルをパースして各ユーザが各問題に対して正答したかどうかのデータを作成し、 それを入力としてstanでロジスティック回帰を行います。

コードはここでは割愛します。 興味のある方は以下にコードを載せています。

github.com

stanでの項目反応理論の実装は下記のサイトを参考にさせていただきました。
- 項目反応理論をStanで実行するときのあれこれ | Sunny side up!

結果

せっかくstanで推定したので、各パラメータの事後分布を確認します。

まず識別力について事後分布を確認します。

f:id:rmizutaa:20190226074738p:plain

識別力はその問題が個人の能力を識別する程度を示すもので、 識別力が低いと問題が解けるかどうかはレーティングとはあまり関係がなく、 高いとレーティングとの関係が大きいという指標になります。

AGCや日経のF問題の分布が広くなっていますが、これらは正解者がほとんどいない影響が出ていると考えられます。 あとはそれほど顕著な値が出ているものはないかなと思います。

次に、問題の難易度となる困難度について事後分布を確認します。

f:id:rmizutaa:20190226074800p:plain

EやF問題で広がっているもののは先ほどと同じ理由ですね。 困難度についてはかなり分布が限定されるようです。

では推定したこれらのパラメータの平均値を用いて項目特性曲線を引いていきます。

  • AGC29

f:id:rmizutaa:20190226074826p:plain

縦軸が正答率で、横軸が参加者のレートを1/1000にしたものになります。 この図だと、例えばレーティングが1000の人がいたとすると、A問題はまず正答できるが、 B問題を解くのは厳しそう、というのが見てわかります。 AGCではA→Bで難易度の断絶を感じていましたが、どうやらD→Eくらいでも難易度のジャンプがあるみたいですね。

  • 全国統一プログラミング王決定戦予選

f:id:rmizutaa:20190226074854p:plain

ABはほぼ同難易度で、C以降は比較的均等な感覚で難易度が推移しています。 C問題は他の問題に比べて傾斜が緩やかになっていますが、これは識別力が低く、 レートが低い人でも回答できたり高い人でも不正解する人の割合が他の問題よりも多かったことを示します。

  • みんなのプロコン 2019

f:id:rmizutaa:20190226074936p:plain

C問題とD問題の難易度の差が非常に大きいです。 レート500-2000くらいの人で解ける問題数が同じになってしまうので、 こういう問題構成のときは早解きが順位に与える影響が大きくなりますね。 (自分は失敗してこのとき水→緑に落ちた)

問題に対する推奨レートみたいなものを作りたかったので、 各問題で正解率が50%となる点をまとめました。

コンテスト名 A B C D E F
AGC29 500 1620 2170 2080 3260 3370
全国統一プログラミング王決定戦予選 270 290 1180 1520 2290 3670
みんなのプロコン 2019 270 320 640 2060 2530 2190

問題の得点と見比べます。

コンテスト名 A B C D E F
AGC29 300 600 700 800 1200 2200
全国統一プログラミング王決定戦予選 100 200 400 500 800 1200
みんなのプロコン 2019 100 200 400 600 800 900

逆転しているのはAGCのCとD、みんなのプロコンのEとFだけですね。 全国統一プログラミング王決定戦予選とみんなのプロコン 2019の400点は、 得点は同じでも50%正答となるレーティングが640と1180で倍近い差があるのは興味深いですね。 体感的には妥当な推定ができている気がします。

私はレーティング1200前後を推移しているのですが、 それくらいの人がどれくらいの確率で問題に正答できるのかを出してみました。

コンテスト名 A B C D E F
AGC29 97.5 19.3 1.4 3.9 0.0 0.0
全国統一プログラミング王決定戦予選 99.3 99.5 51.5 13.3 0.2 0.0
みんなのプロコン 2019 99.9 99.8 96.1 2.8 0.0 0.6

私が正答できたのはAGC:A、全国統一プログラミング王決定戦予選:ABC、みんなのプロコン 2019:ABC、なのでほぼ確率通りです。ここからさらに1問正答するのはもう少し力をつけないと厳しいみたいです。

レートが400上がったらどう景色が変わるのか見たかったので、 レート1600の人が正解する確率も出してみました。

コンテスト名 A B C D E F
AGC29 99.6 48.5 7.7 15.0 0.1 0.0
全国統一プログラミング王決定戦予選 99.9 99.9 79.3 61.8 2.4 0.0
みんなのプロコン 2019 99.9 99.8 99.5 14.6 0.2 4.7

各コンテストで+1問とけるかとけないかくらいになれればレート1600になれるようです。

まとめ

項目反応理論を用いてAtCoderの問題難易度の推定を行いました。 参加者のレーティングを考慮して問題難易度の推定が行えるので、 比較的それらしい結果が推定できたと思います。 もしレコメンド等をしようとするとこういうものが使えるかもしれません。 (強くなる人はどのみち全問解くんですが。。。)