競技プログラミングの作問進行法 (Competitive Programming Advent Calendar Div2014 Day 2)

Intro

初めての作問。作問の作業ってどう進めればいいのかわからない。
そんな人のために、今年は作問についての記事を書くことにしました。
特に、ACM-ICPC OB/OGの会 (通称JAG)の作問の仕方を例に書きます。そのため、作業者が複数いて、ネット上で全てを進めるような作問形態の例となります。その形態と違う方は、自分の環境に合わせてやり方を変えてみましょう。

目次

実際の進行方法と同じように書きます。

  1. コンテスト概要を決めよう
  2. 原案を出そう
  3. 問題選定をしよう
  4. 作業担当者を決めよう
  5. rime&testlibでコード作成
  6. Google docsを使って校正
  7. 最終段階
  8. JAGに入ろう！(番外編)
  9. おわりに

コンテスト概要を決めよう

まずは、「どのようなコンテストを開くのか」決めましょう。これが決まっていなければ、どのような問題を作っていいのかわかりません。決めるのは、次のようなことです。

コンテストの目的

「目的」がなければ、どんなコンテストを開いていいかわかりません。
「ただ、たまった問題を放出したい」という簡単な目的でも、「ICPC国内予選の対策としてコンテストを開きたい」というJAGのような目的でも、何でも大丈夫なので決定しましょう。これが決まっていると、コンテストの概要を決めるヒントになります。

出場者のレベル

「選手のレベル」が決まっていると、自然と問題のレベルも決まってきます。
例えば、TopCoder Div2程度の出場者を対象と決めているなら、Div1 Hardレベルの問題を作る必要はない、とかそういうことです(というか、作れないけど...)。

コンテスト時間・問題数・難易度・ジャンル

目的や出場者のレベルが決まっていると、自然に「コンテストの時間」「問題数」「問題のレベル」「問題の難易度」「問題のジャンル」が決まってきます。
ICPC国内予選対策を目的としてコンテストを開くならば、出場者のレベルは初心者から上級者まで幅広い出場者のレベルが考えられます。ICPCの過去のコンテストの傾向も合わせると、以下のようなコンテスト概要ができあがります。

  • コンテスト時間：3時間
  • 問題数：6~7問
  • レベル
    • プログラミングを始めたばかりの人でも解けるようなレベルの問題を入れる
    • 競技プログラミングの「プロ」が、時間内に解けるか怪しいレベルの問題も用意する(さすがに0perasanレベルは対象外)
  • ジャンル
    • やるだけ 2~3問
    • 探索・DP 2~3問
    • 幾何 1~2問
    • 文字列操作・構文解析 0~1問

原案を出そう

概要が決まりました。さあ、作問作業の始まりです。
まずは、コンテストの概要に合うような問題「原案」をたくさん考えましょう。実際にコンテストに出題するような、しっかりした問題文でなくても大丈夫です。適当な問題案でも、思いついたら片っ端からメモしましょう。

JAGでは「pukiwiki」を使用して、以下の図のように原案を1問1問まとめています(以下の図は、テンプレートです)。

f:id:Respect2D:20141202015231p:plain

図の説明

  • タイトルと問題の概要
    • 問題の作成者や、問題のジャンル、難易度等を書きましょう。コンテストに採用すべき問題かどうかが、一目でわかるので便利です。
  • Problem Statement
    • 図中に書いてある通りです。適当でもいいですが、他人が見て理解できる程度の問題文を書きましょう。
  • Input, Output
    • 入出力のフォーマットについての説明を書きましょう。Outputに「Special Judge」と赤太字で書いてあります。これは、出力が一意に定まらないような問題のときに、必ずメモしておきましょう(例えば、この問題)。Special Judgeの場合、問題準備に一手間かかるので、この情報は大切です。
  • 解法
    • 原案が思い浮かんだ時点で解法がわかっている場合は、詳しく書きましょう。書いておくと、誰かが間違いを発見してくれたり、もっと良い解法を考えてくれる場合があります。
  • 推薦
    • コンテストに出題するかどうかを、JAGではこのように推薦という形で決めています。「この問題を次の模擬国内予選のA問題に推薦します」みたいな感じで記入したりします。
  • 議論
    • 解法の相談や、問題についての意見は、この欄に記入し議論します。

問題選定をしよう

原案をたくさん出しました。
次は「問題選定」を行います。原案の中から、コンテストの概要に合うような問題を適切に決定しましょう。

選定の作業を行った結果、実は原案が足りていないと発覚することがあります(例えば、ICPC国内予選のような問題セットを作りたいと思っていたのに、原案がA~D相当の問題しかなくて、E~Gに置ける問題がない、みたいなことが)。その場合は、今足りていないジャンル、難易度を明確にして、原案を作る作業を再度行いましょう。

このように、選定で結構手間取ってしまうことが多いので、「原案出しと問題選定作業はなるべく早めに」行うようにしましょう。

作業担当者を決めよう

問題がでそろったので、各問題に担当者をつけましょう。JAGでは、以下の図のように「1問につき最低3人体制」の形で作業を進めています。

f:id:Respect2D:20141202030710p:plain

各担当者の意味

  • データセット・解答作成
    • データセットというのは、入力データのことです。間違った解答をなるべく落とすことができるような入力データを作る仕事です。
    • 解答作成は、入力データを受け取って、解答の出力を行うプログラムを作る仕事です(つまりは、皆さんがいつもコンテストで書いているプログラムを作る仕事)。
  • 問題文・入力検証器・解答作成
    • 問題文作成は、どういうストーリーにするか、入出力仕様はどうするか等を考えて、問題文全体を書く仕事です。
    • 入力検証器作成は、データセットが入力仕様通りであるか確認するプログラムを作成する仕事です。
  • 問題文チェック
    • 問題文の校正作業を行う仕事です。
    • 第三者しか気付けないようなことがたくさんあるので、大事な仕事。
    • この人が仕事することで、Clar率が断然減ります。

JAGでは、このように3人に仕事を割り振っていますが、多少割り振り方を変えても問題ありません。ただし、以下の注意点は守っておくのをオススメします。

  • 「解答作成者は最低でも2人」設けましょう。Outputを複数人で確認することで、バグを見つけることができるようになります。解答は、多ければ多いほど信頼度が増すので、自分の担当問題以外でも是非作成しましょう。
  • 「データセット作成と入力検証器作成は必ず別の人」にしましょう。同じ人が作ってしまった場合、データセットの間違いに気付かない可能性があります。
  • 「問題文校正は1人目・2人目とは別の人が望ましい」です。全く問題を知らない人が問題文をチェックすることで、より多くの間違いを指摘することができます。

ちなみに、仮に全部1人だけで1問を担当した場合、次のようなことが起こり得ます。

  • そもそも自分の想定解法が間違っている場合がある
  • Outputを誰とも比較することができず、バグを発見できない可能性がある
  • わかりづらい問題文ができあがりやすい

筆者も1人で全部作ったことがありますが、コンテスト中に2つ目が発覚して、冷や汗した経験があるので、1人だけで作るのだけは絶対やめましょう。

rime&testlibでコード作成

担当者が決まりました。では、実際に「コード」を書きましょう。
って言っても、どういうコードを書けばいいんだ？って思うかもしれません。作問では、いつもみたいに、解答コードを書けばいいだけではありません。

rime

そんなとき役に立つ作問ツールが「rime」です。
JAGもrimeを使用して、作問作業を行っています。rimeを使って、どのようなコードを書けばいいかは、詳しいことがリンク先に説明が記載されているので、そちらをご参照ください。実際のrimeを使った例もこちらにあがっているので、これも必見です。

testlib

さらにJAGでは「testlib」というライブラリを使用しています。
rimeが有名で、こちらはあまり名前を聞かない人もいるかもしれませんが、testlibはデータセット作成プログラムや、入力検証器プログラムで大活躍します。

例えば、AとBの整数 (1 <= A, B <= 1000)が次のような形式で1行で入力される問題を例にしましょう。

A B

この問題の入力検証器をライブラリなしで書こうとするとどうなるでしょう？たったこれだけの検証なのに、本当に正しくチェックしようとしたら、結構面倒だと思います。
もし、この入力検証器をtestlibを使って書くと、次のように簡単に書くことができます。プログラムも直感的でわかりやすいのではないでしょうか。

#include "testlib.h"
using namespace std;

#define MIN_AB 1
#define MAX_AB 1000

int main(){
  registerValidation();

  inf.readInt(MIN_AB, MAX_AB); // 1以上1000以下の整数
  inf.readSpace();             // 間に空白1つ
  inf.readInt(MIN_AB, MAX_AB); // 1以上1000以下の整数
  inf.readEoln();              // 最後に改行
  inf.readEof();               // ファイルの終わり

  return 0;
}

もし、間違った入力が与えられた場合は、エラーをはいてくれます。もっと詳しい使い方は、リンク先を参照してください。

Google docsを使って校正

問題文が書けた、コードもデータセットも全部用意した。これでコンテストを開けるぞー！なんて、舞い上がってはいけません。必ず「問題文の校正」を行いましょう。

「え？日本語の問題文だし、必要ないでしょ」なんて思った人、あまいです。
いくら、自分が良いと思う問題文を書いたつもりでも、他の人が見てみたら全然問題の意味がわからなかったとか、実は入力の制約やサンプルの値がちょっと違ってたみたいなことがよくあります。いくら見直しても足りないくらいです。

そんなことがないように、しっかり校正を行いましょう。ここでオススメしたいのが、「Google docs」です。JAGでも、docsを使用していて、複数人による問題文校正に向いていることがわかっています。
例えば、以下のような感じで校正をしています。

f:id:Respect2D:20141202054142p:plain

図の左側は、pukiwiki等で仕上げた初稿の問題文をコピーしてきたものです。右側は、コメント欄です。docsでは、図中のように、ある選択された領域に対する「コメント機能」があります。これが校正のときに非常に便利で重宝します。また、図中の伊織ちゃんのように、あるコメントに対して返信することもできるので、docs上で議論を進めることも可能です。

それ以外にも、「提案モード」というものがあり、ある選択された領域を別の文章に変更するように提案することができます。図中の、置換：〜と書かれたコメントは、そのモードで書かれたものです。提案コメントに表示されているチェックボタンを押すと、その提案を採用することができます。

このように、docsを使用すると、複数人による校正をスムーズに行うことができるので、作問のときに進んで使ってみましょう。

最終段階

これで、本当にコンテストに必要なものが全て揃いました。作問は、最終確認の段階に入ります。最終確認とは、具体的に何をすればいいでしょうか。

まずは、本番のジャッジシステムでの動作確認が必要です。AOJやAtCoder、使うジャッジシステムは人それぞれだと思いますが、以下のようなことを必ず本番環境で確認しましょう。

  • 問題文が意図した通りに見えているか（文字化けの発生、コピーミスして問題文の一部が消えていないか等）
  • 想定解、想定誤答を投げて、意図していないレスポンスが返らないか (TLEを想定していたのにWAが出る、ACのはずがWAが出る等)。
  • メモリ制限、タイムリミット制限が正しい値になっているか。
  • 開始時間、終了時間、凍結時間、その他の設定が正しく行われているか(AtCoderだと、これらの設定メニューがあるので要チェック)。

他に簡単に確認できることとして、問題文の入力仕様と、入力検証器の仕様に不一致がないかの確認があります。例えば、問題文には1 <= A, B <= 100と書いているのに、入力検証器では0 <= A, B <= 100のチェックになっているなんてミスが、よくあります。このような些細なミスでコンテストが失敗することがあるので、最後の最後に入力チェックは忘れないようにしましょう。

あとは、コンテストが成功することを祈って、解説スライドを作成しましょう。コンテストが始まる前に作っておくと、コンテスト終了後にすぐ解説を公開することができるので、オススメです。ちなみに、コンテスト中にスライドを作ろうとすると、Clar対応等で忙しくて結局作れなかったなんてことがあります。

JAGに入ろう！(番外編)

ー 宣伝は忘れない ー

記事内容とは全く関係ないですが、JAGではスタッフを募集中です。問題バリバリ作りたいという人はもちろん！作問はできないけど、英語ができる人、オンサイトのスタッフとして参加したいという人も募集中です。興味のある方は、JAGのjoinページからメールを送信ください。
ICPCを引退した方も、ICPCに出場していなかったけど競技プログラミング好きな方も、是非JAGへ入って、現役のみんなを応援しましょう！
OB/OG会一同、歓迎します。

f:id:Respect2D:20141202063912p:plain

↑JAGのマスコットキャラクターです(嘘)。

おわりに

以上、競技プログラミングの作問の進め方でした。
いかがだったでしょうか。この記事が、これから作問しようと思っている方々のお役に立てればうれしいです。読んでいただいてありがとうございました。

明日のCompetitive Programming Advent Calendarの担当は、JAGで数々の問題を生み出してきたnodchipさんです。お楽しみにー。