AtCoder の問題を解くのにかかる時間をモデリングした
概要
AtCoder の問題に取り掛かってから AC するまでにかかる時間の対数の平均値は、レーティングの1次式で表現できると考えられます。
理論的導出
この記事の説明にあるように、AtCoderのパフォーマンスは、他の人に対する勝率が内部レーティング差のシグモイド関数で決まると仮定したときの内部レーティングの最尤推定値です。
ここから、2人がある1問の早解き競争したときの勝率も内部レーティングの差のシグモイド関数になると仮定します。この仮定を満たすような解答時間の確率分布を考えていくと、次の分布がその要件をだいたい満たすことがわかります（天下り）。
- 対数正規分布
- 期待値はレーティングの1次式
- 分散はレーティングによらない定数
早解きの勝敗は内部レーティングの差を正規分布の累積密度関数に与えたものとなります。正規分布の累積密度関数はシグモイド関数に似ているので、近似ということにします。
データで確認
分布を決定するには、内部レーティングから解答時間の対数に単回帰すればいいです。AtCoder Beginner Contest 138 の6問について、実際にやってみました。以下のグラフは、
- 縦軸を正解までの秒数
- 横軸をコンテスト開始前の内部レーティング
- 青い点が1人のAC
- 赤い線が求めた回帰式
- 黄色い線がユーザーをレーティング100ごとに区切ったときの平均値
です。なんかいい感じになっているのがわかります（適当）。Fはデータが足りなそう。
実験に使ったコード
ツイッターに書いた難易度推定の続きなので、両方ともここにあります。
その他
wacchoz さんによるレーティングを能力パラメータとしたロジスティック項目応答モデルでの難易度推定がうまく行くのは、上の理論的導出とだいたい同じ説明ができます。1問勝負で引き分けを無視してどちらか一方だけが正解する確率がレーティング差のシグモイド関数になるので、引き分けの部分は解答時間の勝敗がシグモイド関数で決まると思うと全体の勝敗もシグモイド関数になって（たぶん。ちゃんと計算してない）整合的です。
