AtCoderの問題の難易度推定（簡易版）

この記事はAtCoder ProblemsにDifficultyがつく前に考えていたことを形にしたものです。難易度推定の方法としてはかなり単純なものとなります。

【2020/11/17更新】
安定性が高く確実に推定できることから、AtCoder Problemsでも似た方法に切り替わったようです。

• 難易度推定に用いるアルゴリズムを公式のレーティングと同じものにする
• Implemented binary search-based difficulty estimation.

AtCoder ProblemsのDifficulty

AtCoder ProblemsにはDifficultyが表示されています。難易度推定には2PL IRTモデルを使用しています¹いました²。以下のページで詳細に解説されています。

• AtCoder Problems の難易度推定について (amylaseさん)

本記事の目的

本記事では、Ratedな正答者数だけを用いて難易度を簡易的に推定する方法を提案します。

手法

Ratedな参加者だけを考慮することにします。問題にも参加者と同様のレートがあると考え、問題の難易度が$D$、参加者の内部レートが$R$ならば正答率は$\frac{1}{1+6^{(D-R)/400}}$になると仮定します³。このとき、AtCoderのレート計算式（Qiita上の解説記事）の内部パフォーマンス計算式$\sum\frac{1}{1+6^{(X-APerf_i)/400}}=r-0.5$⁴の右辺を正答者数に置き換えた時の$X$が難易度の最尤推定値になります。つまり、正答者数を$K$とすると、$K+0.5$位の内部パフォーマンスが推定難易度になります。ただし$K+0.5$位の内部パフォーマンスを得ることができなかったため、代わりに$K$位の内部パフォーマンスを用いることにします。調査対象は2019年1月から2020年4月までのRatedコンテストとAtCoder Beginners Selectionの問題とします。

結果

• 推定難易度一覧 (Googleスプレッドシート)
  • infはRatedな正答者なし
  • WTFのA, B, C, D, E, FはそれぞれA, B, C1, C2, D, E
  • Tenka1-2019-beginnerとTenka1-2019は同時開催

旧Difficultyとの比較

推定値の違い

AtCoder Problemsの旧Difficultyと比較すると、Difficulty400以下の易しい問題の難易度が高めに見積もられ、Difficulty2800以上の難しい問題の難易度が低めに見積もられる傾向があります。Difficulty1200程度の問題は概ね50以内の差に収まっています。

速報性

ac-predictorを使えばコンテスト中やコンテスト直後にパフォーマンスを知ることができます。遅くともレート更新までには難易度が分かるため、本記事で説明する方法は速報性に優れています。

安定性

【2020/11/17追加】
旧Difficultyでは推定に失敗するケースがありました。この方式ではコンテスト中にAC者と未AC者が1人ずついれば必ず推定できます。

まとめ

AtCoderの問題の難易度を簡単に推定する方法を説明しました。コンテスト直後に大まかな難易度を知るために使えるでしょう。ただし低難度や高難度の問題では推定値が旧Difficultyから大きくずれることが多いため、十分注意して使用してください。

1. AGC-A問題を除く ↩

2. AtCoder Problemsも1PL IRTモデルに切り替わったようです。 ↩

3. 1PL IRT仮定。この仮定を置くと正答率50%と90%のレート差は約490となり、実測値と大体同じになります。 ↩

4. $X$は補正前内部パフォーマンス、$APerf_i$は参加者$i$の内部レート、$r$は参加者の順位 ↩