有志の方の資料

作問用チェックリスト

やり取りしやすいように是非yukicoder Slackにご参加ください

トップページの上から参加することが出来ます。たまにでも見てもらえると助かります。

★1問題の想定解は100ms未満にしてください

コンテスト中にジャッジが詰まる原因になりやすいのでご協力お願いします。

入力の個数は多くても$N=10^5$あたりまでにしましょう

LL言語の入力が読み取れなくなる可能性があります。

自然数の用語を使うのはやめておきましょう

1以上の整数と習ったかもしれませんが、0を含める事もあり曖昧なので控えておいたほうが無難です。正整数や非負整数を使うようにしましょう。

用語は問題文中で定義する

問題文を読みなおす

頭のなかを一度空っぽにして読みなおして、問題文が理解できるかどうか確認しましょう。知ってる人だけにしか伝わらないような日本語／英語になっていませんか？
問題文には一番時間をかけた方が良いです。
数字と数の使い分けを確認しましょう。
特にグラフ問題の場合は、無向グラフ(undirected graph)・有向グラフ(directed graph)なのかをきちんと明記する。

それぞれの入力で与えられる変数の値が、整数か小数か、もしくは文字列かを記述する（非自明な場合）

小数の場合、小数点以下何桁まで入力で与えられるかも記述しましょう。

YES/NOの表記は大文字が良さそう

（要出典）

テストケースの改行チェックには、Unix系なら「file」コマンドを使いましょう

（yukicoderは末尾改行が自動で付加されるようなったのであまり必要ありません）
「ASCII text」とだけ出れば、末尾に改行がありでLFで終わってます。「with no line terminators」なら末尾に改行がありません。「with CR line terminators」ならCRで終わってます。
「file *」とするとディレクトリ内、全部のファイルを指定できます。

ディレクトリ内のCRLFをLF（yukicoderの改行コード）に変換するコード find . -type f | xargs -n 10 nkf -Lu --overwrite

例外

"yz","yx","xz","zz","zy","zy"から始まっているファイルは「MGR bitmap,・・・」と表示される。

などがある（他の例はコメントアウトされてます）

制約は、writer提出コードにassertをつける

念の為にもつけましょう。想定解とは別にassertだけのコードでもいいと思います。

余分な半角スペースが含まれていないかなどもassertでチェックすると良いかもしれませんが、面倒なのでテストケースを作るときに注意しましょう。

$i \neq j $の時に$(A_i,B_i) \neq (A_j,B_j)$などではありませんか？

問題文章上、そう読み取れるかもしれませんが、制約にちゃんと書きましょう

2次元などで$W H$があるのは $H W$の順番のほうが好まれてるらしい

（要出典）

（おなじケースがあれば）サンプルとテストケースが同じか確認する

チェックの意味でサンプルとテストケースが同じ結果になっているか確認しましょう。
また、答えだけでなく、説明に使われる値も正しいか確認しましょう。

サンプルケース内はMathJaxを使わない

コピペが正常にできなくなったり、ジャッジヘルパーの対応ができないため。

ランダムな事象な問題の場合は、「同様に確からしい」や「一様」などのランダムとわかる記述をする

条件（戦略）が記述されてないと、数学的に何の値を求めてるのかわからない(確率ではない何か)ことになるので問題として不適切になります。

（なるべく）モンテカルロ法でも通りそうな制約は避ける

想定解がモンテカルロ法を使う問題は大丈夫ですが、モンテカルロ法でも通ってしまうと想定解法を勉強するモチベーションがあまり出ないと思われるため[要出典]

想定解法のチェックをする

想定解法にバグがないことを確認するためにも愚直な解法（全探索やモンテカルロ、場合によっては山登り法など）を利用して、想定解法と一致するか、最適化問題の場合、想定解法より良い解が発見されないかをチェックすると安心です。
ランダムにテストケースを作成し、想定解法と愚直な解法の答えが一致するか試し続けるプログラムを1つ作ると安心度増し増しです。

テストケースは少なくとも20個を用意する

下の強いケースはもちろん、ランダムなども用いて20個は用意しましょう。嘘解法が通るとお互い良くないです。

テストケースを強くする

テストケースには、最小ケース、最大ケース、コーナーケースとなりうるケースは全て入れましょう（問題にもよりますが、コーナーケースは案外小さいケースが多いor発生しやすいのです）。
ある変数は最小値、ある変数は最大値、と言ったケースも入れれる限り入れると良いです。
場合分けで解ける問題の場合は、全てのケースを入れましょう。
また、最大ケースの場合、複数の変数が同じ値の場合は微妙に速くなったりするのと、最大ケースのみ埋め込みなどをされる可能性があるので、「だいたい最大ケース」みたいなのも入れましょう。
数え上げ問題などではテストケースの数は少なくても嘘解法は通りにくい傾向にありますが、最適化問題などでは嘘解法が通りやすい傾向にあるので注意しましょう。特に貪欲法でかなり良い答えが出るような問題や効率的に枝刈りできる問題は要注意。
嘘解法が通りやすい問題の場合、手軽にテストケースを強くするためには、１ファイルに複数のテストケースを入れる形式にして、テストケースの数を増やして、数の暴力で対抗するのが簡単で確実です。
また、枝刈りが効率的に出来る問題の場合は、考えうる枝刈りを行った解法を用意して、テストケースをランダムに作成し続けて、実行時間がかかるものを拾ってくるというのは結構有効な方法です。
ありうる想定誤解法を想定して、それらが落ちるテストケースを入れるのも理想ですが、コストが高いので数の暴力のほうがおすすめ。
なお、wataさんの嘘解法のススメを読み、嘘解法を絶対に通さないぞという心意気があれば完璧です。
また，yukicoderでは $N \leq 10^9$ でも $O(N)$ 解法が通ったりするので、そういう場合も複数テストケースにすると、良いかもしれません。

テストケースを強くする(discrete logarithmの場合)

安全素数を法とする場合が最悪ケース。安全素数とは$p=2q+1$ ($q$は素数) なる素数。 このとき乗法群の位数が$2q$となる。シローの定理より位数$1,2,q$の部分群が存在し、最初の二つは$\{1\},\{1,-1\}$である。 よって、離散対数問題を解く際に用いる生成元$g$が$\pm1$でない場合、位数$q$の部分群を作り、必ず大きな位数（＝離散対数問題を解くのが難しい）になる。

サンプルの確認

サンプルは間違いが発生しやすい部分です。テストケースを手で作ってミスってたり、制約変更の適用を忘れてたり、サンプルの説明が間違えてたり。必ずテスターが確認しましょう

作問用テクニック（？）

自分が書きたいライブラリ／アルゴリズムの問題を作る

ライブラリが充実／勉強が捗ってハッピーです。

なんかネタを探す（思い浮かんだ時にストックしておく）

どんなネタでも★１や★２の問題（あるいはそれ以上）は作れるものです。

きれいな性質／公式を見つける

きれいな性質を発見した時は作問チャンス。

ちょっとひねってみる

ある変数の制約を極端にきつくすると、出題形式をちょっと変えてみると、その他ちょっとした変更で別の解法が思い浮かんだりしませんか。
同じ題材でも制約次第で色々な問題ができるかもしれません。