作問用チェックリスト
Latest Author 👑
mai
/Date 2021-04-03 13:45:34 / Views 7063有志の方の資料
optさんの競プロ作問チェックリスト (初心者向け)大変まとまっておりますので参考にしてください
作問の失敗 判例集
On the problem setting by antontrygubO_o
初心者のための作問テクニックについて by E869120
作問用チェックリスト
yukicoder作問用のチェックリストです。完成度を高めるために参考にしてください。コミュニケーション
- やり取りしやすいように是非yukicoder Slackにご参加ください
- トップページの上から参加することが出来ます。たまにでも見てもらえると助かります。
制約
- ★1問題の想定解は100ms未満にしてください
- コンテスト中にジャッジが詰まる原因になりやすいのでご協力お願いします。
- ★2以下の問題の入力の個数は多くても$10^5$あたりまでにしましょう
-
Python・Ruby等のスクリプト言語の入力が読み取れなくなる可能性があります。
$10^5$を超える場合は、入力するだけのコードを書いてみて、どの程度時間が掛かっているのか、計測してみると良いです。 - それぞれの入力で与えられる変数の値が、整数か小数か、もしくは文字列かを記述する（非自明な場合）
- 小数の場合、小数点以下何桁まで入力で与えられるかも記述しましょう。
- 不必要にコーナーケースを増やすような制約になっていませんか
-
例えば、$N=1$の場合に特別な考察を必要とする場合、制約を$2\le N$としてしまうと良いです。
非自明に多倍長整数や128bit浮動小数点数を必要とする問題もできるだけ避けましょう。 - （なるべく）モンテカルロ法でも通りそうな制約は避ける
-
想定解がモンテカルロ法を使う問題は大丈夫ですが、モンテカルロ法でも通ってしまうと
想定解法を勉強するモチベーションがあまり出ないと思われるため[要出典]
問題文・解説
- 曖昧・抽象的な用語を避けましょう
-
例えば、以下のようなものがあります。
- 自然数
- 「1以上の整数」と習ったかもしれませんが、0を含める事もあり曖昧なので控えておいたほうが無難です。 「正整数」や「非負整数」を使うようにしましょう。
- グラフ
-
無向グラフ(undirected graph)・有向グラフ(directed graph)なのかをきちんと明記する。
自己ループを持ったり、多重辺を許したりする場合はそれを明記しよう。
- 用語や記号は問題文中で定義する
- たとえそれが比較的一般的な関数であっても、問題文中で定義するようにしましょう。
- ランダムな事象な問題の場合は、「同様に確からしい」や「一様」などのランダムとわかる記述をする
- 条件（戦略）が記述されてないと、数学的に何の値を求めてるのかわからない(確率ではない何か)ことになるので問題として不適切になります。
- $i \neq j $の時に$(A_i,B_i) \neq (A_j,B_j)$などではありませんか？
- 問題文章上、そう読み取れるかもしれませんが、制約にちゃんと書きましょう
- 2次元配列などで 幅=W 高さ=H があるのは $H W$の順番のほうが好まれてるらしい
- （要出典）
- サンプルケース内はMathJaxを使わない
- コピペが正常にできなくなったり、ジャッジヘルパーの対応ができないため。
テストケース
YesかYESが良さそうある変数は最小値、ある変数は最大値、と言ったケースも入れれる限り入れると良いです。
場合分けで解ける問題の場合は、全てのケースを入れましょう。
また、最大ケースの場合、複数の変数が同じ値の場合は微妙に速くなったりするのと、最大ケースのみ埋め込みなどをされる可能性があるので、「だいたい最大ケース」みたいなのも入れましょう。
数え上げ問題などではテストケースの数は少なくても嘘解法は通りにくい傾向にありますが、最適化問題などでは嘘解法が通りやすい傾向にあるので注意しましょう。特に貪欲法でかなり良い答えが出るような問題や効率的に枝刈りできる問題は要注意。
嘘解法が通りやすい問題の場合、手軽にテストケースを強くするためには、１ファイルに複数のテストケースを入れる形式にして、テストケースの数を増やして、数の暴力で対抗するのが簡単で確実です。
また、枝刈りが効率的に出来る問題の場合は、考えうる枝刈りを行った解法を用意して、テストケースをランダムに作成し続けて、実行時間がかかるものを拾ってくるというのは結構有効な方法です。
ありうる想定誤解法を想定して、それらが落ちるテストケースを入れるのも理想ですが、コストが高いので数の暴力のほうがおすすめ。
なお、wataさんの嘘解法のススメを読み、嘘解法を絶対に通さないぞという心意気があれば完璧です。
また，yukicoderでは $N \leq 10^9$ でも $O(N)$ 解法が通ったりするので、そういう場合も複数テストケースにすると、良いかもしれません。
テストケースを手で作ってミスってたり、制約変更の適用を忘れてたり、サンプルの説明が間違えてたり。
テスターは必ず確認しましょう。提出コードで assertion を行えば、これらは防げます。
「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でチェックするともっと良いです。
- 想定解法のチェックをする
-
想定解法にバグがないことを確認するためにも、想定解法より計算量が重い愚直な解法（全探索やモンテカルロ法）を利用して、
想定解法と一致するか確認しましょう。
ランダムにテストケースを作成し、想定解法と愚直な解法の答えが一致するか試し続けるプログラムを1つ作ると安心度増し増しです。
仕上げ
- 問題文を読みなおす
- 頭のなかを一度空っぽにして読みなおして、問題文が理解できるかどうか確認しましょう。知ってる人だけにしか伝わらないような日本語／英語になっていませんか？
問題文には一番時間をかけた方が良いです。
数字と数の使い分けを確認しましょう。
- writer/tester提出を全てリジャッジする
- assertコードを提出した後にテストケースを変えていると、そのテストケースはassertを通していないことになります。
作問用テクニック（？）
こっそりと書いているのです。- 自分が書きたいライブラリ／アルゴリズムの問題を作る
- ライブラリが充実／勉強が捗ってハッピーです。
- なんかネタを探す（思い浮かんだ時にストックしておく）
- どんなネタでも★１や★２の問題（あるいはそれ以上）は作れるものです。
- きれいな性質／公式を見つける
- きれいな性質を発見した時は作問チャンス。
- ちょっとひねってみる
- ある変数の制約を極端にきつくすると、出題形式をちょっと変えてみると、その他ちょっとした変更で別の解法が思い浮かんだりしませんか。
同じ題材でも制約次第で色々な問題ができるかもしれません。