AOJ-ICPC

概要

AOJ-ICPC では Aizu Online Judge に収録されている ICPC 日本リージョン の国内予選,アジア地区予選,及び OB・OG会(通称JAG) のプログラミングコンテストで出題された問題の難易度を有志らで勝手に評価して並べています. 通常のオンラインジャッジでは問題の難易度や良し悪しを見極めるのが難しく,それをまとめるのが主な目的です. 自分の実力にあった問題を探すのにお使いください.

難易度は 100 から 1200 までの数値で評価しています. 100 から 600 までは 50 刻みで,それ以降は 100 刻みで付けています. これらは元々 topcoder の div1 の点数表記と合わせる意図で付けていましたが,ICPC と topcoder では出題される問題のバリエーションが大きく違うこと,また時代の移り変わりとともに topcoder 自身の難易度が大きく変動していることがあり,現在は topcoder の難易度表記とは一致していません. そのため,AOJ-ICPC の難易度は独自の基準で付けられています. 細かい基準については下記の「難易度基準」の項目をご覧ください.

難易度表のページで自分の AOJ のアカウント ID を入力すると,今の自分の回答状況を照らし合わせることができます. 他人の ID を入力して比較することもできます. AOJ-ICPC での回答状況の更新は数分おきの間隔で行っています.

投票によって良問であると判断された問題には ☆ マークが問題名の後についています. 良問が何であるかの明確な取り決めは今のところ存在しませんが,「他人にその問題を解くことを勧めたいか」が基準の1つになっているように見えます.

投票

AOJ-ICPC では投票を常時受け付けています.投票では認証のために Twitter を使っています.

投票をする場合,まずはページの右上の "Sign in with Twitter" を押して,自身のアカウントを AOJ-ICPC のアプリケーションに認証させてください. Twitter のアカウントを持っていない人は適当に作ってください. Twitter API の仕様上,AOJ-ICPC のアプリケーションに read 権限を付与することになります.そのため,protected アカウントを認証させる場合は注意してください. 難易度表の ☀ マークをクリックすると,対応する問題の投票ページに移動し,投票を行えます.

投票ページには投票欄とコメント欄があります. 投票欄では難易度の点数,☆,投票理由を投稿できます. コメント欄では問題の解法や感想,その他雑談などを投稿できます.

投票理由欄とコメント欄では MathJax を使用できます. 数式にしたい部分をドル記号($)で囲むとその部分が数式環境で表示されます.また,\[ ... \] で囲むと,その部分だけ改行された状態で表示されます.

投票の更新は不定期に行っています. 難易度をいくらに設定するかは,投票の平均値などを見て運営が手動で更新しています.

除外問題

問題の中にはなんらかの不備があったり,似たような問題が他に多く存在するなどの理由で,解いても得られるものが少ないものが存在します. このような理由で AOJ-ICPC の運営が解かなくても良いと判断したは除外問題というカテゴリに分類しています. 除外問題は普通の難易度表には表示していません. また,通常の難易度も付けず,単に △ という記号を付けるに留めています. 最終的に問題を除外するかどうかは運営が独自の判断で行っていますが,おおまかに以下のような基準で判断しています.

  1. 問題文に致命的な不備がある.
  2. 難しすぎて解いても得られるものが少ない.
  3. データセットが致命的に弱かったり Time Limit の設定が長すぎたりして,想定ではない愚直な解法が通ってしまう.
  4. 問題そのものよりも問題文の解読の方が難しい.
  5. 他にも同じような問題が難易度表に幾つかあり,他の問題を解いていればそれをわざわざ解く意味があまりない.

除外したい問題がある場合は,該当する問題の投票欄やコメント欄にその理由を書いてください.

問題の難易度を Spreadsheet で管理していた頃はまだ問題数がそこまで多くなく,また JAG などの有志団体が作っている問題についてはボランティアで作っていることもあり質がそこまで高くなくてもやむを得ないだろうと判断して,多少の不備があっても目を瞑っていることがありました.しかし最近は問題数が増えてきており,また AOJ-ICPC を競技プログラミングの練習に使っている人がそれなりに多く見受けられることから,ある程度質の高い問題を残したいと考えています.つまり問題に多少不備がある程度でも除外する可能性があります.

連絡板

全体向けのコメント欄です.特定の問題ではなく,AOJ-ICPC 全体で何か意見や要望がある場合は連絡板に書いて下さい.

難易度基準

難易度は基本的に「実装の大変さ」と「数学的・アルゴリズム的な考察の大変さ」の2つを軸に決めています. 難易度を決めるにあたってはかなり個人差があるため言語化するのは難しいのですが,各レベル帯はおおまかに以下のような基準で決めているつもりです.

100 プログラミングの入門を終えたばかりの人でも辛うじて解けるレベルの問題が並ぶ. 必要となる知識は基本的な制御構文(if, for)と配列くらいで,アルゴリズム的な考察はほとんど要求されない. 基本的には問題文をそのまま実装するだけで良い.実装量も(変なことをしなければ)1KB前後で収まることが多い.
150 プログラミングを始めてからプログラミングコンテストの問題にある程度慣れたレベルの人たちが解けるレベル,あるいは,コンテスト以外のプログラミングに慣れている人がいきなりスタートしても(標準入出力の扱いなどを除けば)難なくこなせるレベルの問題が並ぶ. 問題としては,簡潔なシミュレーションや探索の問題から構成される. このレベルで必要となるアルゴリズムは初歩的なものに留まる.具体的には,素因数分解,スタック/キュー,簡単な全探索など. 実装量は多くとも1KB~2KB程度で済むことが多いはず.
200
250 実装だけではなく,数学的・アルゴリズム的な考察をある程度要するレベルの問題が並ぶ. このあたりからアルゴリズムの知識がある程度必要になってくる.具体的には以下のような感じである.実際には,以下を基点として問題それぞれの実装量や考察量を加味して難易度を考えることになる.
・250- : 幅優先探索,ダイクストラ法などの最短路アルゴルズム
・250- : 動的計画法
・350- : 最大流問題,最小費用流問題
・350- : ライブラリが必要となるレベルの幾何
・350- : データ構造 (セグメント木,BIT, UnionFindなど)
実装量はさまざまであるが,多くとも2~3KB以内に収まるはずである.
300
350
400
450 やや重い実装や,数学的・アルゴリズム的な考察を要するレベルの問題が並ぶ. いわゆる「典型」と呼ばれるタイプの問題(有名な手法を使えば比較的苦労せずに解けるもの)も多く含まれており,ここまでを一通り解けば何が典型であるのかは一通り分かる構成になっている(ような気がする).
500
550
600 重い実装や,やや難しい数学的・アルゴリズム的な考察を要するレベルの問題が並ぶ. この辺りから,その問題固有の「あまり典型ではない考え方」をする必要が出てくることがある. あるいは,考え方自体は自明だが実装方針を決めるのが容易ではない問題も含まれる.
700
800
900 上位陣の選手でも苦労するような難しい問題が並ぶ.(良い説明募集)
1000
1100 トップレベルの選手でも苦労するような難しい問題が並ぶ. 実装が大変なだけではなく,あまり典型的ではない高度なアルゴリズムや数学の思考が要求される.複雑な考察に加えて,難解な実装をしなければならないことも少なくない.
1200

運営

運営は @ichyo(社会人), @ir5(社会人), @asi1024(大学院生) あたりが暇な時にやっています. 砂場はこちらにあります.