noshi91
客観的なデータをもとに難易度色をつける
ある程度項目数が落ち着いてきたらでいいんですが、競技プログラマーに以下の項目でアンケートを取って難易度色を裏付けるデータを取りたい気持ちがあります。
- 現在のレーティング
- 辞典の各項目について知っているかどうか
- 名前を聞いたことがない / ある / どのような問題を解けるか知っている / 資料を見ながら実装できる・した / 人に説明できる
これで知っている度合いが一定以上（資料を見ながら実装できるを今のところ考えています）の人の割合が50%になるレーティングを難易度色とするという案を考えています。
客観的な色を表示できるとうれしいというのはまったくその通りです。 私はさすがにそこまで手は回らないので調査は任せたいですが、やってもらえればその結果はぜひ取り込みたいです。
クイズにしてtwitterに放流すると流行って回収率が上がりそうですね。あと正確さも当然上がると思います。
「知っている」ことの定義を考えてみたんですが、「コンテストで知識そのものズバリを聞く問題が出たら解ける」というのがいいのではないかと考えています。そうすると、この定義の知名度を測るには知識問題が大量に並んだコンテストをするのが一番いいことになりますが、準備があまりにも大変そうなので（これはこれでやったら面白そうではありますが）、もっと簡潔なクイズでこの定義での知識を測るようにする方針にしようと思っています。
今のところ、クイズの冒頭に100個くらいアルゴリズムの名前が並んでいて、各問題が以下のような形式になっているものを想定しています。
問題
整数係数の n 次多項式が 2 つ与えられます。これらの積を求めてください
制約
時間計算量: O(n logn) 空間計算量: 制限なし
出力
この問題を解くのに使うアルゴリズムまたはその設計手法を冒頭の選択肢から選び、記号で答えてください。
実現の手法のひとつとして「AtCoder の問題に使用するアルゴリズムでタグ付け (手動で、あるいは解説記事や提出結果を解析して自動で) し、そして問題のタグと問題の難易度推定の結果からタグの難易度を推定する」という方法もある気がしてきました。実現可能性が怪しいですが、機械学習に詳しい人がやるならこういう方向も面白いと思います。面白そうな思い付きを言ってみただけであり、実際にどの手法でやるかは任せます。