1. はじめに
こんにちは、高校 2 年生のE869120です。
私は、プログラミングの中でも競技プログラミング (競プロ) が好きで、AtCoder・CodeForces・国際情報オリンピック・パソコン甲子園などの各種大会・コンテストに出場しています。
さて、競プロをやっている人の中では、
作問をしたいけど、初心者なので作問が本当にできるのか不安だ。。。
といった考えや、
問題は思いついたけど、作問の方法やテクニックが分からないから作問できず困っています。。。
といった考えが近年多く見受けられます。1 それについて、「誰でも気軽に競プロ作問ができるようにしたい！」と思い、私は本記事を書くことにしました。
今回は、競技プログラミングの世界で、作問と出題準備をする方法について解説します。初心者でもわかるように解説しますので、是非お読みください！
対象とする読者層
この記事は、競技プログラミングを経験したことがある方すべてに読んでいただきたいです。当然、灰コーダーから赤コーダーまで全部含めます。競技プログラミングをまだやったことが無いという方は、以下の 2 記事を読んで、競技プログラミングを今日から始めましょう。
本記事を終えた次は？
本記事を読み終わったら、以下のコンテストサイトで作問をすることをお勧めします。
yukicoder は、作問のプラットフォームがしっかり整備されているため、灰コーダー・茶コーダーなどの初心者でも出題ができます。実際に、作問者の約20%が緑コーダー以下です。余力があれば、CafeCoderなどで作問することもお勧めです。（設立から数か月なのでまだサーバーは安定していませんが）
目次
| 章 | タイトル | 備考 |
|---|---|---|
| 1. | はじめに | |
| 2. | 作問の役割分担と作業工程 | 作問の全体の流れについて説明します！ |
| 3. | 問題文作成 | ここをしっかりフォローします！ |
| 4. | テストケース作成 | ここもしっかりフォローします！ |
| 5. | その他、作業で確認しておくべき 6 つのポイント | 失敗の原因となる、あまり気づかないポイントを 6 個紹介します！ |
| 6. | おわりに |
2. 作問の役割分担と作業工程
さて、競技プログラミングの問題を作り、出題するためには、どのような工程を踏まなければならないのでしょうか。その全体的な流れを理解していただくために、この章では以下の 2 点について説明します。
2-1. 役割分担
競プロの作問には、以下の 2 つの役割の人が携わります。
| 役割 | 何をするか |
|---|---|
| writer | 問題の原案担当者。問題文・テストデータなどの作成を行う。 |
| tester | writer の問題を解き、AC する。そして問題文やデータが本当に正しいか確認を行う。 |
writer は、基本的に 1 つの問題につき 1 名です。（共同作問の場合は例外ですが、滅多に無いです）
tester は、1 名のことが多いですが、AtCoder のコンテスト等では 2 名以上付く場合もあります。例えば、GigaCode 2019 のテスターの数は 4 名でした。
2-2. 作業の流れ
競プロ作問の作業工程（ステップ）は、以下のようになります。
本記事では、主に writer 側が関わる作業について説明します。
- 3 章では、問題文作成 (writer)
- 4 章では、テストデータ作成 (writer)
- 5 章では、最終確認とその他のテクニック (writer/tester)
で解説します。方法とテクニック等を含め、すべて解説します。
3. 問題文作成
競プロのコンテストに出題するためには、まず問題文を書く必要があります。問題文は、
- 「自分が理解できるもの」ではなく、「ほとんど (95%以上) の参加者に理解できるもの」
である必要があります。そのため、問題文は分かりやすくなければなりません。でも作問未経験の人は、どのような問題文を書けばよいのかわからないと思います。そこで、以下の 6 点に分けて説明したいと思います。
- 問題文に入れるべき項目 ： 問題文
- 問題文に入れるべき項目 ： 制約
- 問題文に入れるべき項目 ： 入力
- 問題文に入れるべき項目 ： 出力
- 問題文に入れるべき項目 ： 入力例・出力例
- 問題文作成で特に気を付けるべき 7 つのポイント
3-1. 問題文に入れるべき項目 ～「問題文」編～
問題文は基本的に、文章が短い方が「参加者が理解に苦しむ」確率を減らすことができます。目安としては、200 文字以内です。実際に、直近 10 回の AtCoder Beginner Contest で出題された問題の 75% 以上が「200 文字以内の問題文」でできています。そのように、数式などを用いて、削ることも重要です。長くなってしまう場合は、もし箇条書きなどを用いてより分かりやすくすることが可能です。良い例としては、
- AtCoder Beginner Contest 146 D - Coloring Edges on Tree → 文章が必要最小限にまとめられている
- AtCoder Beginner Contest 143 D - Triangles → 箇条書きが効果的に使われている
- 第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution → 数式が効果的に使われている
問題にストーリー等を付けたい場合は、「問題文」という項目には入れず、「ストーリー」という別の項目に入れましょう。
ただし、「実生活に即した問題文にしたい」「小学生にも理解できるような問題文を書きたい」などといった理由で、どうしても長くなってしまう場合があります。例えば、
その場合は無理に削る必要がありません。そのような長い問題文は、「箇条書きにする」「①・②・③・… というように場合分けして書く」「問題文や入力例に図を入れる」などという手法を使うと、格段に分かりやすくなります。
3-2. 問題文に入れるべき項目 ～「制約」編～
全ての入力データが制約条件を満たすように、しっかり制約を付けましょう。特に以下の 3 点に気を付けましょう。
- 「$N$ が偶数である」などという特殊な制約を入れ忘れない
- $0 \leq N$、$1 \leq N$、$2 \leq N$ のどれであるかを間違えない
- 入力が全部整数の場合、「入力はすべて整数である」を書き忘れない（そうでない場合も、「$a, b, c$ は全部整数である」などを書く）
3-3. 問題文に入れるべき項目 ～「入力」編～
以下の形式に合わせると簡単です。詳しくは、過去の AtCoder 公式コンテストなどの問題を見ることでわかると思います。
入力は以下の形式で標準入力から与えられる。
(pre タグを使い、入力形式を書く) ※HTMLで問題文を書く場合
3-4. 問題文に入れるべき項目 ～「出力」編～
AtCoder 以外では、出力が 1 行の場合に「最後の改行を忘れないこと」を書くのを忘れないようにしましょう。例えば、以下の文章は定型文です。
出力が 1 行の場合
1 行に、〇〇〇〇〇〇を出力してください。
最後に改行してください。
出力が 2 行以上の場合
$N$ (あるいはその他の数式) 行に渡って出力してください。
$i$ 行目に、〇〇〇〇〇〇を出力してください。
なお、AtCoder では基本的に、空白区切り・改行区切りの違いや、無駄な空白改行をしても正解と判定されます。そのため、「最後の改行を忘れないこと」が問題文中に明記されていない場合が多いです。
3-5. 問題文に入れるべき項目 ～「入出力例」編～
入出力例の目的のうち一つは、「競技者が問題を理解する助けになる」ことです。そのため、入出力例は
- 基本的に 3 つ以上用意すべき
- うち 1 つは入出力例に対する説明を書くべき
だと思います。実際に、直近 10 回の AtCoder Beginner Contest の C～F 問題のうち、入力例が 3 つ以上ある割合は 約98% です。その一方で、入力例の数が多いと、解法を推測されてしまいやすい問題もあります。例えば、
この問題は、答えが $\frac{N(N-1)}{2}$ です。非常に単純であるため、多くの入力例があると、解法を入力例から推測できる人が多く出てしまいます。そのような場合は入力例の数を少なくするのも手です。
3-6. 特に気を付けるべき 7 つのポイント
最後に、問題文作成作業において「writer / tester でも気づかないけど不備の原因になりやすい！」というところを上位 7 項目、紹介したいと思います。問題文を確認する時に、以下の 7 つの項目（特に上位 4 項目）を見ると、大幅に分かりやすい問題文ができると思います。
| 順位 | 内容 |
|---|---|
| 1位 | 制約のところに「入力はすべて整数」を明記する。 |
| 2位 | 問題文・制約・入出力例中の変数が間違ってないか確認する。例えば、$N$ が $Q$ になってないかとか、$A_i$ が $a_i$ になってないかとかを全部確認する。 |
| 3位 | 制約が本当に合っているかどうか確認する。$0 \leq N$ か $1 \leq N$ かはもちろん、コンテスト直前に突然制約が変更された場合は特に注意。 |
| 4位 | ですます調／である調が統一されているか確認する。 |
| 5位 | 入力例に十分な説明がついているか確認する。 |
| 6位 | 句読点が問題文中で統一されているか確認する。例えば、「、。」「，．」「,.」の 3 通りが混在している場合がある。 |
| 7位 | 長い問題文には、十分な図が付いているか確認する。 |
4. テストケース作成
競プロのコンテストに出題するためには、テストケースを作る必要があります。テストケースは、大きく分けて「入力データ」「出力データ」の 2 種類があり、それぞれ作る必要があります。今回は、初心者でも簡単にテストケースが作れるように、以下の 5 点に分けて説明したいと思います。
4-1. 入力データの作り方
基本的に、乱数などを用いてテストケースを作ることが推奨されます。
例えばランダムなテストケースを作りたいとき、C++ の場合 rand 関数 を以下のコードように使うことができます。（なお、rand 関数は Visual Studio の場合 $0$ ～ $32767$ までの値しか出てこないので注意。）
// #include <ctime> をする
srand((unsigned)time(NULL)); // 実行ごとに同じ乱数が出ないようにするおまじない
int x = rand();
また、生成された入力データをいちいちコピーして txt 形式に貼り付けるのは面倒だと思うので、C++ の場合、ファイル入出力というものをお勧めします。（以下のようにできます）
FILE *in = freopen("in1.txt", "w", stdout);
上のようなコードを main 関数内の先頭に書くと、cout で出力されたものが全部 in1.txt に書き込まれます。これを、テストケース数と同じ回数実行すれば、全部の入力データが作れます。（for 文を回して一気に数十ケース生成する方法もありですが、初期化とかの関係で初心者にはあまり安全ではないです）詳しくは、生成コード例をご覧ください。
4-2. 出力データの作り方
ステップ 1
まず、想定解ソースコードを作りましょう。
ステップ 2
次に、想定解ソースコードと同じ階層に、in というフォルダと out というフォルダを作り、in に全入力データをコピーしましょう。（例えば下の図だと、main.cpp と同じ階層に in フォルダと out フォルダがあり、in フォルダに全入力データが入っています）
ステップ 3
in1.txt に対する出力を生成したい場合は、想定解ソースコードの main 関数の先頭に、以下のコードを書きましょう。
FILE *in = freopen("in\\in1.txt", "r", stdin);
FILE *out = freopen("out\\in1.txt", "w", stdout);
それを実行すると、out フォルダに in1.txt というファイルが生成され、入力データに対する答えが書き込まれます。実は freopen を使うと、すべての cin に対してファイル読み込みができ、すべての cout に対してファイル書き込みができるので、とても便利です。
ここでは in1.txt での出力生成方法を説明しましたが、これをすべての入力データに対して行えば、全テストケースに対する出力データを生成することができます。20 ケース以上ある場合少し手間がかかるかもしれませんが、この方法が最も安全です。詳しくは、生成コード例をご覧ください。
4-3. どのようなテストケースを作ればよいのか？
テストケースが弱いと、本当に簡単な嘘解法が通ってしまう可能性があります。ですが、以下の 6 項目を含むと、嘘解法を通す可能性が大幅に減ります。
[1] 最小ケース
$N = 1$ などの、制約条件を満たす中で最小のケースは必ず用意すべきです。
「$N = 1$ の場合分けを忘れてて WA する」といったケースは決して珍しくありません。
[2] 最小ケースに準ずるもの
$N = 2, 3, 4$ などのケースも入れるべきです。
実際に、「$N = 2$ の特定のケースのみで誤解答となる」というケースも珍しくないです。通り数が少ない場合は、$N$ が一定より小さいテストケースを全通り（あるいは全パターン）入れるのも手です。
[3] 最大ケース
$N \leq 10^{5}$ に対して $80000$ とかではなく、本当に最大のケースです。大きい入力データは、実行時間制限超過（TLE）の原因となるので、必ず入れるべきです。なお、最大ケースには、以下の 3 種類を入れることがオススメです。
- ランダムケース（ランダムで計算時間が最も長くなるのは珍しくない）
- $A_i, B_i$ など各種値も最大となっているケース
- 実行時間が最大となるようなコーナーケース（思い付けば）
[4] 最大に近いランダムケース
$N \leq 10^{5}$ とかに対して $99999$ とか $98230$ とかの、最大に近いランダムケースも入れるべきです。特に以下の 2 つのパターンの場合は必須です。
- 1 つの値しか入力しない問題の場合（埋め込みで通される可能性があります）
- $N$ の値などの偶奇で、実装の方針が変わる場合
[5] <一応> 中くらいのケース
もし作れれば、あった方が良いです。無くても影響は少ないです。
[6] <一応> コーナーケース
作るのは難しいですが、コーナーケースを入れると、嘘解法が落としやすいです。無くても影響が少ないことが多いですが、あった方が良いです。コーナーケースの例として、以下の 4 種類が考えられます。
- $A_i$ など、各種値が全部 $1$ のテストケース
- $A_i$ など、各種値が全部 $0$ のテストケース
- $A_i$ などの値が全部異なるテストケース（稀に TLE の原因となることもあります）
- その他、tester が想定した嘘解法を落とすテストケース
4-4. テストケース作成で困りがちな 5 つのポイント
ポイント 1 ～テストケースの個数～
テストケースの個数は、基本的に 20～30 個程度が推奨されます。稀に 200 個以上作る人もいますが、そうするとジャッジにすごく時間がかかってしまい、yukicoder などの場合ジャッジキューが詰まる可能性があります。コーナーケース等が多くても、50～70個程度を限度としましょう。2
ポイント 2 ～入出力データのファイル名～
基本的に、入力データと出力データのファイル名は一致していなければならないことが多いです。例えば、入力ファイル in1.txt に対応する出力ファイルの名前は in1.txt である必要があります。AtCoder・yukicoder 両方そうです。
一方で、HackerRank で問題を作る際のみ例外です。HackerRank の場合は、入力テストケースが順に input00、input01、input02、… 出力テストケースが順に output00、output01、output02、… となっている必要があるので、注意してください。
ポイント 3 ～ファイル入出力を Visual Studio でやるとき～
いざ、ファイル入出力を Visual Studio でやろう！ と思ったとき、以下のようなエラーが出ることがあります。
エラー C4996 'freopen': This function or variable may be unsafe. Consider using freopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
このエラーを解決するためには、main 関数の前（include をいろいろやっているところ）に、以下の一文を追加しましょう。そうすると、正常にプログラムが実行され、テストケースが作成されます。
#pragma warning (disable: 4996)
ポイント 4 ～Visual Studio における乱数について～
C++ の標準の環境 (GCC) を用いると、rand() 関数は $0$ 以上 $2^{31}-1$ 以下の値を返します。一方で、Visual Studio の場合、rand() 関数は $0$ 以上 $32767$ 以下の値しか返さないのです。両方の環境で正常に $2^{31}-1$ 程度以下の乱数を生成するためには、以下のようなコードを使いましょう。（以下のコードでは $0$ 以上 $2^{30}-1$ 以下の乱数を生成します）
int Rand() {
return (rand() % 32768) * 32768 + (rand() % 32768);
}
ポイント 5 ～入力データの生成方法を残すべき～
突然、制約が tester の意見により変わる、などということは作問準備においてよく起こることです。そのため、制約が変更されてもすぐ対応できるように、予め入力データを生成する関数を作っておくべきです。詳しくは、生成コード例を参照すると分かりやすいと思います。
4-5. 入力データ・出力データ 生成コード例
5. その他、確認しておくべき 6 つのポイント
最後に、コンテストを開催したときに、問題の不備が起こる可能性を減らすために、確認しておくべきポイントを 6 個、紹介します。全部やると相当な負担になるので、全部やる必要はありませんが、多くやればやるほど成功確率が上がります。
5-1. 解法をきちんと証明すること
解法はしっかり証明してから出しましょう。
証明に不安があるのならば、強い tester（目安は青色以上）に厳密な証明を頼るのも大事です。
5-2. writer も制約チェックをすること
writer が生成したケース、実は制約に違反しているかもしれません。というか、最初に生成した入力データの制約違反はかなり多く、競プロの作問を 3 年やってきた私でも 20% 程度の確率でケース生成を間違えます。また、AtCoder Beginner Contest 150 でも、D 問題の一部のテストケースが制約を満たしていなかったため、unrated となりました。
そのため、writer/tester 両方が「全テストケースが制約の条件を満たしているか」をチェックすることが推奨されます。方法はとても簡単です。
ステップ1
全テストケースをコンテストサイトに upload する。
ステップ2
制約違反が 1 箇所でもあればランタイムエラー（RE）となるように、想定解に以下のようなソースコード（assert 関数）をすべての制約について追加する。
// 例 1. N > 400 の場合ランタイムエラーを起こす
assert(N <= 400)
// 例 2. A[i] が [1, 100] の範囲に入っていない場合ランタイムエラーを起こす
for (int i = 1; i <= N; i++) assert(1 <= A[i] && A[i] <= 100);
ステップ3
ステップ2で追加されたソースコードを提出し、ACが出たらテストケースの制約違反に問題なし、REが出たらテストケースの制約違反に問題あり。
5-3. ストレステストをすること（中級者以上向け）
- writer の想定解ソースコードがバグってしまい、tester も同じバグを踏んだ
- writer の想定解ソースコードがバグってしまい、tester の確認がコンテストに間に合わなかった
- 実は解法の証明が間違っていた
などといったケースが多く見受けられます。初心者には難しいかもしれませんが、全探索や $O(N^2)$ 解法など、計算時間が遅く実装が軽いアルゴリズムを書き、$N=2～20$ 程度の小さいランダムケース（数万ケース）で比較し全部一致するか調べる、といった手法を使うと、確実性が上がります。これをストレステストといいます。
なお、$N = 20$ とかいう特定の $N$ について調べるのだけでは駄目です。「$N = 2$ の特定のケースだけ誤解答となる」などはザラにあります。そのため、$N = 1, 2, 3, 4, 6, 8, 10, 12, 15, 20, ...$ といった複数の $N$ に対してストレステストをかけることが推奨されます。
5-4. 嘘解法を落とすこと（中級者以上向け）
基本的に、AtCoder 以外の日本国内コンテストサイトで出題する場合は、嘘解法が AC することは比較的気にされない場合が多いです。
一方で、「多くの人が嘘解法で AC する」確率を減らすには、
- 適当な貪欲などを tester と協力して思いつく。
- 思いついた嘘解法を、ストレステストと同等な手法を用いて探索し、それぞれ落とすケースを 1 個以上入れる。
というのが手です。（なお、実は嘘解法だと思っていた解法が、どんな入力データに対しても正しい回答を返すことがあるので、注意しましょう）
5-5. 入力データに無駄な空白改行が無いのを確かめること（できれば）
- 実は入力データの最後の行に改行がなかった
- 入力データの一部に、無駄な空白があった
などといった場合、C++ などの競技プログラミングにおけるメジャーな言語では問題なく解くことができますが、多くのマイナーな言語では、空白改行のミスのせいで入力が正しく読み取れず、WA などになってしまうことがあります。実際に 技術室奥プログラミングコンテスト #4 Day1 では、その影響で 3 問に不備が発生しました。
AtCoder では testlib.h などという便利なツールを利用していますが、初心者中級者には（環境構築から）やや難しいと思うので、手動で「入力例」と「その他数ケースの中の一部分」をチェックするだけでもいいです。それだけで、ミスが起こる確率は大幅に減ります。（AtCoder の writer をするときは testlib.h を使いましょう）3
5-6. 強い tester に頼ること
既に AtCoder や yukicoder などで作問を経験している人は、やはりそのような作問準備にも慣れています。そのため、writer の作業に不安があれば、経験者や強い人に相談することをお勧めします。相談すると、問題に不備が起こる確率を減らせるだけでなく、writer 作業をどう進めていくかなどのアドバイスをいただける場合も多いです。
6. おわりに
作問は、競プロ初心者でもすることができます。
皆さんの中にもし興味があれば、yukicoderなどのコンテストサイトで作問をすることをお勧めします。今日からでもできます。問題を思いついたらすぐ準備して出題するのがオススメです。
最後に、本記事が少しでも「競プロ作問をしたい！」という方の役に立ち、作問者を一人でも増やすことができたならば、そして将来的には AtCoder の writer を増やすことができたならば、とても嬉しい気持ちです。高校生が書く記事ですので分かりにくい部分が多かったかと思われますが、最後までお読みいただきありがとうございました。
-
本記事は、このような意見を持つ人から要望を受けたため、作成されました。例えば @aoharu514 さんの ツイート など。 ↩
-
稀に、AtCoder ではテストケースが 100 個以上ある問題があります。ただ、このような問題の多くは、難易度が高く、実行時間が 1 ～ 2 秒と短いです。また、例外的に、日本情報オリンピックの問題はテストケース数が非常に多く、Mountain Rescue Team などテストケース 232 個といった問題もあります。 ↩
-
実際に、AtCoder 公式コンテストでは testlib.h を用いて制約チェックすることが義務化されていますが、今回の記事は初心者対象なのでそこまでは求めないことにしています。 ↩