Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2016-12-01

[] AtCoderの昔の問題を難易度推定する 00:09 はてなブックマーク -  AtCoderの昔の問題を難易度推定する - TopCoderの学習のお時間


これは 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への出題について」です。お楽しみに!

 |