Hatena::Grouptopcoder

ir5は引退した

 | 

2014-12-11

問題を難易度表で管理することについて

01:32

この記事は Competitive Programming Advent Calendar 2014 の11日目の記事です.主に ICPC・JAG難易度表(a.k.a. AOJ-ICPC) の話を書きます.難易度表の話は今まで断片的には色んなところに書き記していたのですが,ちゃんとまとめて書いたことがなかった気がするので,この機会にまとめてみようと思います.

難易度表について

ICPC・JAG難易度表ICPC日本地区公式のセットとOB/OG会のセットの一部の問題をまとめ,いくつかの難易度で区切って表示することを目的に作ったページです.現在は Google spreadsheet 上で管理しています.難易度は,不特定多数のユーザーからの投票を受け付け,管理者がそれに基づいていい感じに決めるといったことをしています.

AOJ-ICPC ではICPC・JAG難易度表の問題と AOJ での解答状況を集計して公開しています.各ユーザーの解答状況を見れる他,他人との正解した問題の差分を見る機能(diff)も実装されています.

ここで唐突ですが,去年の会津大会のときに撮影した AOJ の美しいサーバーの様子を御覧ください.

履歴

この難易度表をつくろうと思った理由と,その経緯について記します.ちょっと懐古録みたいになってる気がしないでもないですがご了承下さい.

かなり昔からこのような難易度表を作るモチベはありました.

以下のツイートは2012/9のものですがこれよりも前に似たようなことをつぶやいていた気がします.うろ覚え.

作るモチベの源泉となっているのは音楽ゲーム(特に弐寺,BMS((弐寺の二次創作版みたいものです.)))のコミュニティです.音楽ゲームでは曲が大量にあり,弐寺公式では同じレベル帯にあっても分け方が粗いために上位と下位で難易度に大きな幅があり,曲選びの際に悩みの種になったりします.そんなときに非公式の難易度表を使うと,公式よりも細かい指標で難易度がわかり,曲選びがスムーズに行えたりします.また,BMSでは作者の付けた難易度が作者によってばらばらでよくわからないのでそれらを統一して扱うためであったり,そもそもBMSでは曲が多すぎてどれをダウンロードすればわからないのでそれをまとめる役割を果たしているようです.また,攻略情報などを wiki や掲示板で共有するためのコミュニティとしての役割を果たすというのも重要な要素です.

現時点では様々なサイトがありますが,例えば以下のようなサイトは有名どころでしょう.

…ちょっと話が脱線したので競プロに戻りますが,難易度表が存在するメリットはおおまかに以下のようなものであると考えていました.

  • オンラインジャッジを始めたばかりの初心者にとってはどれを解けばいいか一目で分かりやすい.解いた人数以外の信頼できる指標として使える.
  • 中級者~上級者にとってはひたすら埋めることで修行用に使える.
  • 投票や解法の交換でコンテスタントの地力を上げる.コミュニティを活性化させる.

あと,当時は ICPC や JAG で問題がたくさん生まれていくもののあまり解いている人が居らず,問題を作るばかりではなくて問題を振り返る機会をもう少し大切にしたいなぁという考えもありました.☆の投票があるのは,数多く存在する問題の中でもできるだけ良い問題を残して行きたいといった意図があったりなかったりします.

ただこういう難易度表のためのサイトを作るには多くの場合専用のシステムが必要になり,作るための時間を確保できていませんでした.また,長い時間をかけて作ったとしてもそれを実際に使ってくれる人がどれくらいいるのかもよく分からなかったため,当時の僕は興味がちょっとあったものの手が出せていませんでした.そうした中で @japlj さんが Google Spreadsheet を使ってJOI非公式難易度表を作っていました.いつごろからあったのか忘れましたが少なくとも2012/9の時点では既に存在していたようです.たしかに Spreadsheet を公開設定にして書き込めるようにしておけば投票もできるし編集も柔軟に行えるので,これはなかなか上手い方法だなと思いました.

そういうわけで,比較的暇な時間ができた正月に3日間実家に篭って難易度表のたたき台を作り,Spreadsheet 上で公開しました.

難易度の数字は TopCoder を意識しています.突然新しい指標を作りだしても,難易度の合意が取りづらいのではないかと思ったためです.とはいえ当時はとりあえずたたき台の段階だったので難易度はだいぶ適当だった記憶があります.いかんせん300問近い問題をひよこのオスメス判定のように高速に分けていくのでだんだん自分でも何が難しくて何が簡単なのかわけがわからなくなっていきます.あと難易度もこのときはかなり細かく分けていたのですが,後になってこんなに細かい必要は無いと判断して高難易度の難易度分けはマージされています.

で,驚いたのがこの翌日なのですが,@ichyo さんがこの難易度表と AOJ の解答状況を集計するページを作ります.スピード感があります.

以降は投票とかを地道に反映させたり,なんとなく放置したり,また更新再開させたりしていて,今に至ります.現在は難易度表の管理は @ichyo さんと僕でやっています.

現状

投票でだいぶ票が集まって結構安定してきたように思います.とはいえまだ改善点はありそうです.例えば以下のようなものです.

  • 基準の変更とか,時代の流れで簡単とみなされるようになった問題がまだ上位難易度に残っているのをどうすべきか
  • 難易度の整合性,個人差の扱いどうするか (幾何と数論とか比較しようがないし…)
    • あまり細かいところにこだわっても疲れるだけである
  • 非推薦の問題をもうちょっと賢く決めたい(今は管理者が半分独断で決めているがもう少し合理的にやるべき)

また,最近は diff 埋めといって,ライバルで実力が近い人が解いている問題を順番に埋めていくといった使い方が流行っていて,これもまた面白い使い方だなぁと思います.僕がオンラインジャッジを埋めていた頃はひたすら孤独な修行という印象だったのですが,随分とソーシャルになったものです.

今後の展望とか

現在は @ichyo さんに混ぜてもらって AOJ-ICPC をちょっとずつ変えていっています.今は github のプライベートリポジトリで管理しています.変更分は多分そのうち公開すると思います.

できたら楽しいだろうなぁと思っているのは以下のことです.

  • 投票機能を spreadsheet から移植する
  • 難易度や☆だけではなく,解法の話とかもできるようにする
  • 個人差を可視化する (投票の数値の分散を表示するとか)
  • ICPC・JAG以外の表を作る.例えばJOI版の表を作る.高校生ウケ狙い.
  • これ

…とはいえ僕はもうあまり時間が割けない(しあと立場的にもずっとこれに携わるのはある程度のところでやめたいと思っている)のでどなたかやってくれる人は常時募集しています.とりあえず投票機能の移植くらいまでは実装してしまいたいところです.

まとめ

ちょっと単に僕が昔を思い出すだけっぽい記事になりましたが,まぁみんなゲーム感覚で問題を埋めたり問題について考察とか感想を共有していけば,日本の競プロのレベルも上がるし,楽しいし,なんとなく盛り上がってる感じがするし,細かいことはよく分からないけど,いいんじゃないかと思います.面白い,知的好奇心を刺激する,これは大切なことだと思っています.

アドベントカレンダーの次の担当は @na_o_ys さんの「競プロと出会った一年を振り返る」です.一体どんな一年があったのか気になります.

 |