AIによる難易度ソート

AI が問題文・解説・想定解を読んで、解くのに使う技法と難易度を見積もり、 見積もった難易度の順に並べた一覧です(同じ難易度の中は、技法の前提関係から「先に解くとよい問題」が先に来る順)。 見積もりは AI によるもので、誤りを含みます。技法は、問題一覧のタグと同じく、その問題を AC した方・作問者・練習モードを「ゆるふわ」にしている方に表示しています。見積もりの理由(解き方の要約)は、その問題を AC した方に表示しています。 開催中の均一スコアのコンテストの問題は、終わるまで出しません。開催中のほかのコンテストの問題の「先に解くとよい問題」は、技法と同じく AC した方などにだけ表示しています。

AI推定難易度の見積もり方

AI(Claude)が、問題文・解説・想定解(作問者の正解プログラム)を読んで見積もった値です。誤りを含みます。

コンテストの成績・AC した人数・提出の結果から計算した実測値ではありません(AtCoder Problems の difficulty のように参加者の成績から求めた値とは別物で、ずれがあります)。

  • 数値の目盛り: AtCoder のレート相当の目盛りで、大きいほど難しい見積もりです。解説で分かった本当の重さを入れますが、初めて解く人の立場で付けます(解き方を知ったあとの「易しく見える」は入れません)。
  • アルゴリズム / 考察: 総合の難易度を 2 つに分けた見積もりです。
    • アルゴリズム: 解き方を教わったとして、実装に要る知識と実装の重さ。
    • 考察: 使う技法は知っているとして、解き方に気づくまでの重さ。
    どちらも総合以下で、重い方は総合に近い値になります。
  • 目盛りのそろえ方: 問題を数十問ずつに分けて見積もり、どの組にも共通の基準問題を付けさせて、組ごとのずれを基準問題の値でそろえています。 一番易しい帯は、No.9000 Hello World! を基準(どの問題もこれより下にしない)として、解くのに要る要素の数で付けています(下の「見積もりの基準」)。
  • 400 未満の値: AtCoder が低いレートを表示するときと同じ式(r が 400 未満なら 400/e(400−r)/400)で、正の値に縮めています。並び順は変わりません。
  • AI自力: AI が解説を読む前に、問題文だけで立てた解き方で解けたかです。「解けなかった」は方針から違っていたもの、「概ねの方針は合っていたがコーナーケースなどの考慮不足」は方針は合っていたものの、コーナーケース・オーバーフロー・定数倍など、そのまま書くと誤答につながる見落としがあったものです。解けたものには何も出しません。
  • 手直し: 作問者・解いた人からのレビューを受けて、運営が確かめて値を直したものがあります。
見積もりの基準(AI への指示の要約)
  • 読むもの: 問題文(制約の追記まで全部)・解説・想定解を切り詰めずに読みます。解説の中の画像(図・手書きのメモ)も開いて見て、解説が外部へのリンクだけならリンク先も読みます。読めなかったものは、問題文と想定解だけで見積もります。
  • 技法: 決めた技法の一覧から、想定解で実際に使うものを大事な順に選びます(先頭が主な技法)。他の人の AC を根拠にするときは、関数名ではなく実際に使っているアルゴリズムを読んで確かめます。
  • 技法と難易度: 技法だけで値を決めることはしませんが、次の目安と、下の「種類ごとの基準」に合わせます。易しい側(元の値で 400 未満)の目安:
    • 入出力の形だけ(決まった文字列・読んだ値をそのまま出す): −350〜−250
    • 条件分岐 1 つ・四則演算数回: −250〜−100
    • ループ 1 つ・簡単な文字列操作・小さな全探索: −100〜100
    • 少し考えるもの(公式・場合分け 2〜3 個・素数判定・約数列挙): 100〜300
    • 易しい DP・貪欲・二分探索の入口: 300〜400
    • 特殊な入出力・オーバーフロー・誤差・コーナーケースなどの実装の罠があれば少し上げます。
    値は縮める前のもので、画面では上の「400 未満の値」の式で正の値に直して出します。このうち元の値で −200 以下になった問題は、下の「一番易しい帯」の要素の数で付け直しています。
  • 理由: 想定解の要点を 200 字以内で書きます。易しさ・難しさの格付けや、他の問題と比べる文は書きません。
  • AI自力の判定: 解説を読む前に問題文だけで立てた解き方を書き出し、あとで書き換えません。「解けた」にするのは、想定解か、総当たりとの照合と時間の実測で確かめた別解だけです。迷ったら「解けなかった」にします。
  • 解説を読んで: 解けなかった問題は、解説・想定解を読んで納得したか(納得 / 追加実験で解決 / 一部分からない / 分からない)を記録します。「追加実験で解決」は、解説で分からなかった点を、総当たり・反例探し・証明で説明できたものです。小さい範囲を総当たりしただけ(入力が有限でない)なら「一部分からない」のままにします。
  • 一番易しい帯: とても易しい問題は、見積もりの揺れで並びが崩れるので、解くのに要る要素の数で付けます。要素は、入力・算術・分岐・条件の組み合わせ・文字列や添字・ループ・型や境界の注意・小さな気づき(切り上げ、+1 や境目、木の辺は N−1 など)・専門用語です。Hello World!(No.9000)を要素 0 として、要素 1 つごとに上げ、どの値も No.9000 より下にしません。
  • レビューの扱い: 作問者・解いた人の指摘を重く見て、近い問題の今の値と比べて決めます。指摘が問題の種類についての基準になるときは、レビューの付いた問題だけでなく、同じ種類の問題を全部見直してそろえます。今までに決めた種類ごとの基準:
    • 燃やす埋める(最小カット)が主な技法の問題は 2000 以上(ただの最大流で解けるものは除く)。
    • 3 値以上の燃やす埋めるは 2400 以上。
    • 一番易しい帯では、切り上げ除算や +1・境目(何番目・何階など)の考察を「小さな気づき」として数える。

読み込んでいます…