■ [部活] AtCoderの昔の問題を難易度推定する 
これは Competitive Programming （その2） Advent Calender 2016 1日目の記事です。
先日、Twitterでこのような発言を見かけました。
AtCoderの過去問が今の基準だと何点になるのか知りたいhttps://twitter.com/hogeover30/status/785894012716654593
やってみました。
一応、背景を書いておきます。
以前のAtCoder Regular Contest（以下ARC）・AtCoder Beginner Contest（以下ABC）では、基本的にそれぞれの問題は100点満点でした。
2016年7月にAtCoderがリニューアルされた際、難しい問題は高い点数となるよう、難易度に応じた配点がされるように変わりました。
そこで、以前の問題が最近の基準では何点くらいになるのかを、ユーザーの回答状況を元に推定しました。
AtCoderリニューアル後のコンテストの問題に対する、各ユーザーの正解/不正解の結果と配点を教師データとして機械学習し、過去の問題に対する正解/不正解の結果をテストデータとしています。
結果はこちらにあります。
https://tomerun.github.io/atcoder_statistics/estimated_scores.html
- どうしても古いコンテストほどデータが少なくて推定しづらい様子。ABCのA問題が250点くらいといった高すぎる数値が出ている
- ABCのD問題にもけっこう難しいのが紛れている
- あまり出てないので知らなかった
- 難易度順が逆転してしまっているところはあんまりない
- これくらいの推定なら正解者数や正解率だけの分析でも出せるんではないかという気もしますが…
- 解ける人が数人しかいない最高難易度帯の問題は、そのコンテストに誰が参加していたかによって結果がかなり影響されてしまうので、信頼性低そう
実装に関しては、だいたいはscikit-learnのSVMに放り込んだだけですが、細々とした話としては次のようなことがあります。
- 全ユーザー使ってしまうとデータがすごくスパースになって精度下がってしまうので、過去のコンテストに100問以上参加しているユーザーのみを計算に使いました
- 対象ユーザーは236人でした
- 過去に一部、満点が101点という問題がありましたが、100点以上を正解として扱っています
- 「後ろのほうの問題だけ解いて他は無視」という参加をする人もいるので、コンテストの後半の問題は提出しているのに前半の問題は未提出の場合、前半の問題は不正解ではなく不参加という扱いにしています
- 逆に前半だけ提出していて後半は未提出の場合、後半の問題は手が出なかったとみなして不正解扱い
せっかく今回いろいろデータを集めてきたので、他にもなにか面白い分析をやりたいですね。アイディアがある人はぜひ教えてください。
Advent Calendar2日目は、tubo28さんの「未定」と、snuke_さんの「IOIへの出題について」です。お楽しみに！
