競プロ作問のTips

競プロ作問に関する Tipsです。

他にも、作問に関する記事は これ などたくさんありますが、一回まとめておきたいと思いました。

上の記事は多少参考にしました。

急いで書いたので雑でも許してください

Writer のやること

原案作成

原案作成はそんなに気を付けることはないですが、一応。

つまらない問題を避ける

あからさまにつまらない問題はつまらないので、やめましょう。

プラットフォームの雰囲気にもよりますが、不必要な実装を増やしたりすると、つまらないです。

解法の正当性を証明する

これは大事です。

解法の正当性を証明できないまま出題して Writer 解が間違っていることがコンテスト中に発覚すれば、大変なことになります。

問題文作成

原案ができたら（原案や解法のプロットなどは誰に見せるものでもないので、なぐり書きでも全然よいです）、問題文作成にとりかかります。

問題文作成で注意すべき点を以下にまとめます。

問題文の流れを意識する

「問題文の流れ」というのは、問題を読む人が理解しやすい情報の出し方、順番のことです。

たとえば、一通り問題設定を述べた後にただし書きを多くすると読む人が右往左往することになります。

「整数 が〜、<中略> を求めてください。ただし、 です。」みたいなのは良くないです。

「 でない整数 があります。」と始めればこれは避けられます。

このように、問題文の流れを意識して、読みやすい順番に文章を並べると良いです。

かっこ書きを使わない

基本的に問題文を書く過程でかっこ書きが必要になることはほぼありません。

かっこ書きをするくらいなら、一段下げてちゃんと文章として書きましょう。

「〜を とします。（つまり、〜が になります。）」より、「〜を とします。<改行> つまり、〜が になります。」のほうが良いです。

ちなみに、これは英語問題文などでもかなり重要です。

全角文字と半角文字の間には半角スペースを空ける

これは見やすさに関わります。

「互いに素な3数がある。」

よりも、

「互いに素な 3 数 がある。」

のほうが読みやすいです。

AtCoder などの問題文もこれに準拠して書かれています。

また、漢数字のほうが見やすいと判断すれば漢数字を使ってもいいと思います。

箇条書きをうまく使う

並列の情報がたくさんあるときは、箇条書きを使うと効果的です。

普通に書くのと変わらない、と思うかもしれませんが、「並列に条件や挙動の説明が複数個ある」という事実を読む人に暗に伝えられるのは大きいです。

主語と述語を対応させる

これは競プロに限りませんが、主語と述語が対応していない文章が世の中には多く見受けられます。

「<抽象的な名詞> としては、<具体的な名詞> が挙げられます。」と書くべきところを「<抽象的な名詞> としては、<具体的な名詞> です。」と書く、というのが最もよくある例です。

このような文章は、一部の人は不快に思うおそれがあるので、書かないように気をつけた方が良いです。

敬体と常体を混ぜない

これも競プロに限りませんが、敬体（です、ます調の文）と常体（だ、である）調の文は、混ぜないでください。

もちろん、

• 会話文を挿入する場合
• 箇条書きなどで、条件を簡潔に記述したい場合

などに混在することはありえますが、他の部分との区切りをはっきりさせないと、とても読みにくい文章になります。

読点を入れる

これはもはや特に言うことないですが、読点を適切に入れましょう。

制約をしっかり書く

これは E869120 さんの記事に詳しいですが、Writer に慣れていないと必要な制約を書き忘れることがあります。

入力が整数であることや、入力の下限など、間違えやすいところが非常にたくさんあります。

慣れているというわけではないですが、自分でも、気を抜いて書くと 3 回に 1 回くらいは間違えてしまいます。

これに関しては本当に何度もしっかり見直しをしたほうがよいです。

ill-defined な定義を避ける

新しい用語を定義する時以外にも、説明をする時は well-defined になるようにしましょう。

サンプルの説明に気を付ける

サンプルケースの説明に誤りが含まれる場合は思ったより多いです。

ここの文章も、読みやすく正しいものを書くようにしましょう。

ここに挙げたこと以外でも、常識的な文章を書くよう心がけましょう。

テストケース作成

テストケース作成は、作問で最もミスが起こりやすいところです。

作成の詳細な方法は E869120 さんの記事をみてください。ここでは、起こりやすいミスを中心に話します。

制約違反に気を付ける

これが一番問題で、かつ重大なミスです。

作る時から気をつけていれば制約違反が起こることはほぼないので、気をつけましょう。

これは、とにかく生成のときに気を付けるしかないですが、のちに述べる validation の作業で発見できるミスでもあります。

テストケースを作った後に制約の変更をして違反する場合が多いです。

強いケースを作る

テストケースが弱いせいで愚直解法などが通ってしまうと、問題の質が下がってしまいます（悲しい…）

E869120 さんの記事にもあるように、

• 最小ケース
• 最大ケース
• 最大に近いケース
• ランダムケース

の4つは必ず入れた方がいいでしょう。

木なら、直線グラフやウニグラフ、場合によっては完全二分木や深めの木など、特殊なケースをたくさん入れておくと良いです。

また、コーナーケースがあるなら当然そのコーナーも入れましょう。

サンプルケースを入れる

当たり前です。

Tester のやること

Tester の仕事も重要です。

Writer が変な日本語を書いたり、変なケースを作ってしまったりするのは、人間なので仕方ないですが、それに Tester が気づかないのはもっとやばいです。

問題文校正

Writer の書いた問題文を、相談しながら誰でも読めるように校正します。

ここで注意することは、上に書いた問題文作成でやることに準ずるので省きます。

Validation

これめちゃくちゃ大事です。

テストケースの制約違反・形式違反をチェックします。

testlib.h を使うといいでしょう。

自分は、標準入力からファイル名を受け取って validation する validator を書いて、

ls tests | ./validator

みたいにして実行しています。

これで改行や空白に関するミスも見抜けます。

その他

Time Limit や制約の調整

想定解だけを通してその他の解法を落とすために、相談して制約や Time Limit を適切に設定しましょう。

ただ、Python などの遅い言語にも対応する必要がある場合なら、あまりきつい Time Limit は良くないです。

まとめ

Writer/Tester のどちらかは慣れた人がやりましょう