作問用チェックリスト

Latest Author yuki2006 /Date 2016-07-23 01:51:18 / Views 1311
2 (Favした一覧ページは作成中です。)

作問用チェックリスト

yukicoder作問用のチェックリストです。強制ではありませんが完成度を高めるために参考にしてください。
問題文を読みなおす
頭のなかを一度空っぽにして読みなおして、問題文が理解できるかどうか確認しましょう。知ってる人だけにしか伝わらないような日本語/英語になっていませんか?
問題文には一番時間をかけた方が良いです。
数字と数の使い分けを確認しましょう。
特にグラフ問題の場合は、無向グラフ(undirected graph)・有向グラフ(directed graph)なのかをきちんと明記する。
それぞれの入力で与えられる変数の値が、整数か小数か、もしくは文字列かを記述する
小数の場合、小数点以下何桁まで入力で与えられるかも記述しましょう。
テストケースの改行チェックには、Unix系なら「file」コマンドを使いましょう
「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発生しやすいのです)。
ある変数は最小値、ある変数は最大値、と言ったケースも入れれる限り入れると良いです。
場合分けで解ける問題の場合は、全てのケースを入れましょう。
また、最大ケースの場合、複数の変数が同じ値の場合は微妙に速くなったりするのと、最大ケースのみ埋め込みなどをされる可能性があるので、「だいたい最大ケース」みたいなのも入れましょう。
数え上げ問題などではテストケースの数は少なくても嘘解法は通りにくい傾向にありますが、最適化問題などでは嘘解法が通りやすい傾向にあるので注意しましょう。特に貪欲法でかなり良い答えが出るような問題や効率的に枝刈りできる問題は要注意。
嘘解法が通りやすい問題の場合、手軽にテストケースを強くするためには、1ファイルに複数のテストケースを入れる形式にして、テストケースの数を増やして、数の暴力で対向するのが簡単で確実です。
また、枝刈りが効率的に出来る問題の場合は、考えうる枝刈りを行った解法を用意して、テストケースをランダムに作成し続けて、実行時間がかかるものを拾ってくるというのは結構有効な方法です。
ありうる想定誤解法を想定して、それらが落ちるテストケースを入れるのも理想ですが、コストが高いので数の暴力のほうがおすすめ。
なお、wataさんの嘘解法のススメを読み、嘘解法を絶対に通さないぞという心意気があれば完璧です。
また,yukicoderでは $N \leq 10^9$ でも $O(N)$ 解法が通ったりするので、そういう場合も複数テストケースにすると、良いかもしれません。

作問用テクニック(?)

こっそりと書いているのです。
自分が書きたいライブラリ/アルゴリズムの問題を作る
ライブラリが充実/勉強が捗ってハッピーです。
なんかネタを探す(思い浮かんだ時にストックしておく)
どんなネタでも★1や★2の問題(あるいはそれ以上)は作れるものです。
きれいな性質/公式を見つける
きれいな性質を発見した時は作問チャンス。
ちょっとひねってみる
ある変数の制約を極端にきつくすると、出題形式をちょっと変えてみると、その他ちょっとした変更で別の解法が思い浮かんだりしませんか。
同じ題材でも制約次第で色々な問題ができるかもしれません。