読む人向け: 思考内容を雑にメモったものです。内容の正確性はありません。批判などはご自由に。発展させてくれるとなお良い。
memo:
AtCoderのABCにおける、出題前のDifficulty推定について、どうやれば精度が上がるかを考える。
Difficulty = どれだけコンテスト中に参加者が解ける割合があるのか、ということを考える必要がある。ざっと以下の点を考慮には入れたほうが良さそう。
- 考察強度・知識強度・実装強度
- ”難度" ではないのは、 個人の感覚による判断によってしまうことを避けた
- 推定正解率・推定AC時間・推定ペナ率
- 問題配置
以下詳細
考察強度: どう考えればよいか、どの程度深い考察が必要になるかによるもの。adhoc系はここが高くなる?、dp系の問題もこっちに寄ってくるかもしれない。
知識強度: 知識がないと解けないようなもの、典型があると大幅に解きやすくなるものがここ?(典型により解きやすくなる、は指標分けたほうがよい?)、例えば「最小値の最大値は二分探索」など。検索しやすさや類題の有無・既出とかも影響する?
実装強度: 実装する際に、実装量が多くなったりバグが生まれやすいかどうか(コーナーケースが多いは「考察強度」にはいる?)。ややこしい全探索とか、グラフ探索系とかが当てはまるかも?
推定正解率: 「問題単体でコンテストに出たら、こんぐらいの人が正解するかもね~~~」という感覚値、推定Difficultyを見積もるぞって言われて考えられてるの多分ここだけ
推定AC時間: ACするまでにかかる時間、考察強度と実装強度によりそう。(知識強度が足りない場合はそもそも解けないか膨大に時間がかかることになると思われる)
推定ペナ率: コーナーケースの引っかかりやすさ(考察強度)、バグりやすさ(実装強度)が影響しそう。
問題配置: 以上を見積もったうえで、問題配置による影響度を考慮するための項。考察・実装強度が高いDより、知識強度がやや高く考察・実装強度が低いEのほうが解かれるやつを考慮したい。
主張としては「考察・知識・実装軸で問題考えてみない?」という話と、「問題配置の影響を考えてみない?」という話がある。
多分もうちょい細分化するとかしてうまいこと「解くとはどういう要素が影響するのか」を詰めれたら。