趣旨

筆者（$p$進大好きbot）のyukicoderコンテストに参加しようか検討している人向けに、筆者がyukicoderで作問する際にどのような基準で★の数を設定しているかについてご説明いたします。

作問そのものに興味がある人は

• 競技プログラミング作問時に心掛けていること
• 競技プログラミング作問のノウハウ

もお楽しみください。

前置き

競技プログラミングで作問をする時、難易度の評価をする必要があります。特にyukicoderで作問をする場合、★の数で難易度を表す必要があるのですが、その表し方はwriterさんによって千差万別です。例えば

1. yukicoderの過去問と比較して、同程度の難易度の問題と同じ★の数をつける。
2. yukicoderのヘルプを参考にして、想定解のアルゴリズムに対応する★の数をつける。
3. ★の数とAtCoderのdifficultyの間に対応を決め、difficultyを推定してそれに対応する★の数をつける。

などが一般的な方法かなと思います。「この方法でないといけない」などと持論を述べるつもりはなく、あくまで筆者のコンテストに参加しようとしてくださっている人向けに筆者がどうしているかを述べるだけであることにご留意ください。

大雑把な基準

まず結論から言うと、先程挙げた方法の1・2を折衷して★の数を決めています。つまりyukicoderの過去問とヘルプの療法を参考にして★の数を合わせているということです。

過去問を参照している理由は、

• 過去問に合わせた方が普段からyukicoderで練習なさっている参加者の方々にストレスを与える難易度設定を避けやすいから。
• 過去問に合わせた方が、★1埋めのような特定の難易度埋めで練習している人の妨害をせずに済むから。

が主です。つまり普段からyukicoderを利用していらっしゃる方々にとってのメリットを優先しています。

ヘルプを参照している理由は、

• 運営さんが「難易度は、ヘルプのものに合わせようプロジェクト」を始動した以上、なるべくヘルプに則した難易度設定にすることが運営さんへの礼儀だと思っているから。
• ヘルプが今後も変わらないという前提のもとで、ヘルプに則した方が普遍的な（既存のdifficultyと違ってコンテスト参加者の偏りや実力のインフレに影響を受けない）難易度設定にできるから。
• ヘルプを重視するwriterさんが増えれば増えるほど、ヘルプに合わせた方が他のwriterさんと整合的な難易度設定になり、普段からyukicoderで練習なさっている参加者の方々にストレスを与える難易度設定を避けやすいから。

が主です。つまり運営さんへの感謝と、難易度インフレへの忌避ですね。

細かい基準

では具体的にどう難易度を決めるかですが、第一の指針として過小（普段からyukicoderで練習なさっている参加者の方々にとって★の数が少なくついているように感じさせてしまう難易度設定）を絶対に避けたいと考えています。

そのための対策として

• 過去1年以内に★3で要求されていない手法は極力★3で出題しない。★3未満をつける際も同様で、例えば過去1年以内に★2.5で要求されていない手法は極力★2.5で出題しない。
• 過去3年以内に★3で出題された問題のほぼ上位互換となる問題を★2.5で出題しない。★3未満をつける際も同様で、例えば過去3年以内に★2.5で出題された問題のほぼ上位互換となる問題を★2で出題しない。
• ★3.5以上はupsolveしていないため同様の措置が取れないが、なるべく過小を避けるためにtesterさんがついている場合はtesterさんの難易度評価との$\max$を取る。

という方策を取っています。

ただしここ最近は★3以下のインフレが激しく、それこそ過去1年以内に★3で要求されていない手法がそこそこの頻度で★3で出題されているので、upsolveをし続けるのがとても難しく感じています。従ってこの方法での作問がいつまで続けられるかは分かりません。

またあくまで過小を避ける目的なので、過去問を基準に評価した★の数の下界とヘルプを基準に評価した★の数の下界の$\max$を取って★の数を設定しています。

ただしいくつか例外があります。例えばヘルプで★4に挙げられている行列冪乗はそれより少ない★の数でも出題しています。その理由は、★4典型としての行列冪乗は行列を冪乗するアルゴリズム自体が難しいのではなく、非自明な考察でそれらに帰着させることが難しいからです。

つまり★3相当の考察で自然に行列冪乗に帰着できるのであれば★3に設定することもあり得るということです。アルゴリズムとしての難易度自体は他の★3典型とさほど変わりませんので。

同様にヘルプで★3.5に挙げられている桁DPと★4.5に挙げられているFFTもそれより少ない★の数でも出題しています。

自分用覚え書き

github pagesで数式を使う際は、閉じ括弧と半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。（波括弧でもたまにバグる）

数式環境をくくる大括弧と数式環境内の中括弧や半角空白や濃度のシャープは半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。

inline数式内の縦棒はlvertなどを使わないとmarkdownの表と認識される。

大括弧の数式環境はアンパサンドで縦位置を揃えられない。

arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。arrayなしだとアンパサンドは使えない。