-
Notifications
You must be signed in to change notification settings - Fork 28
Home
Rime はプログラミングコンテストの問題セットの作成を補助するツールです。
ACM-ICPC 形式や TopCoder 形式のプログラミングコンテストを開く際、問題を出すために準備しなければならないものは何があるでしょうか。問題案は既にあるものとすると、必要なものは主に次の4つに大別されます。
- 問題文. 最初から凝った文章を作る必要はもちろんありませんが、少なくとも問題の骨子と入出力形式はあらかじめ決めておかなければなりません。
- 模範解答プログラム. 問題が解けることを証明するため、入出力データを作るため、その他あらゆる理由のために模範解答プログラムが必要です。ここで最も重要なことは、模範解答は複数用意されるべきだということです。複数の解答を複数の人間が用意して、その出力を照合することによって、解答プログラムの誤りを大幅に減らすことができます。また必須ではありませんが、想定解法と比べて計算量が大きすぎる解法や、一見正しそうに見えてエッジケースで間違う解法などの、想定「誤答」のプログラムを作成しておけば、それらを振り落とす入力データを作ることが容易になります。
- 入出力データ. 小さな入力データは手で直接作ることができますが、大きなエッジケースやランダムケースに対応する入力データはプログラムで作ることになります。出力データは入力データを模範解答プログラムに入れて作成します。
- 入出力検証器. 入力データのフォーマットが合っているかどうかは、模範解答プログラムとは別のプログラムであらためて検証することが望ましいでしょう。また、出力形式が浮動小数点数を含む場合など、単純な diff プログラムで間に合わない場合には、出力検証器を用意する必要もあります。
Rime は、この 4 つの項目のうち、問題文を除いた残りのすべての準備作業を補助します。たとえば、次のようなことができます。
- 手動で作成した入力データや入力ジェネレータを適切な場所に置いておけば、コマンド1つで入力ジェネレータを実行しデータセットを作成することができます。
- 生成された入力データセットを自動的に入力検証器に通し、フォーマット違反がないかどうかをチェックします。
- 複数の模範解答プログラムを自動的にコンパイルし、それらの出力が一致するかどうかをチェックします。
- "想定誤答プログラム"を置いておくと、そのプログラムがジャッジを通過しないことをチェックし、万が一通ってしまった場合は警告を出します。
- 各問題について、模範解答プログラムを走らせた結果を分かりやすく表示します。
ここでは、あらかじめ用意された設定例を使って Rime を実行し、Rime の機能の概略を紹介します。
まずは Rime をダウンロードして下さい。Github のプロジェクトページ https://github.com/nya3jp/rime から ZIP をダウンロードするか、次のように git clone してください:
$ git clone https://github.com/nya3jp/rime.git
以下では、仮に ~/src/rime に Rime を展開したと仮定します。
$ cd ~/src/rime
このディレクトリには次のようなファイルが存在するはずです(最新版ではもう少しファイルが多い可能性もあります)。
$ ls -l
total 12
-rw-r--r-- 1 nya nya 0 May 11 23:55 README
drwxr-xr-x 3 nya nya 4096 May 11 23:55 example
drwxr-xr-x 6 nya nya 4096 May 11 23:55 rime
-rwxr-xr-x 1 nya nya 1215 May 11 23:55 rime.py
rime.py および rime ディレクトリは Rime のプログラム本体です。example ディレクトリには設定例が用意されていますので、そこに移動しましょう。
$ cd example
$ ls -l
total 8
-rw-r--r-- 1 nya nya 96 May 11 23:55 PROJECT
drwxr-xr-x 6 nya nya 4096 May 11 23:55 a+b
lrwxrwxrwx 1 nya nya 7 May 12 00:10 rime -> ../rime
lrwxrwxrwx 1 nya nya 10 May 11 23:55 rime.py -> ../rime.py
このディレクトリ以下には、コンテストの問題・解答・入出力ジェネレータなど全てに関する設定が保存されています。このようなディレクトリをプロジェクトディレクトリと呼びます。
プロジェクトディレクトリには Rime 本体とプロジェクト設定ファイル(PROJECT)、そして問題ディレクトリを置きます。問題ディレクトリは通常複数あるでしょうが、この例では一問だけ (a+b) 用意されています。プロジェクトディレクトリ以下には Rime が認識するもの以外のディレクトリやファイルがあっても問題ありません。なお、このプロジェクト例では簡単のため Rime 本体をシンボリックリンクとして置いてありますが、通常のプロジェクトではファイルをまるごとコピーして置くと良いでしょう。
早速 Rime を実行してみましょう。
$ ./rime.py test
[ GENERATE ] a+b/tests: generator.py
[ VALIDATE ] a+b/tests: OK
[ COMPILE ] a+b/cpp-correct
[ REFRUN ] a+b/cpp-correct
[ COMPILE ] a+b/cpp-TLE
[ TEST ] a+b/cpp-TLE: 11-maximum.in: Time Limit Exceeded
[ COMPILE ] a+b/cpp-WA-multiply
[ TEST ] a+b/cpp-WA-multiply: Expectedly failed all challenge cases
[ TEST ] a+b/cpp-correct: max 0.00s, acc 0.09s
[ TEST ] a+b/python-correct: max 0.04s, acc 0.72s
Test Summary:
a+b ... 4 solutions, 24 tests
cpp-correct OK max 0.00s, acc 0.09s
python-correct OK max 0.04s, acc 0.72s
cpp-TLE OK 11-maximum.in: Time Limit Exceeded
cpp-WA-multiply OK Expectedly failed all challenge cases
Error Summary:
Total 0 errors, 0 warnings
このコマンドは数秒で終了するはずです。この間に Rime は次の処理を行いました。
- 問題ディレクトリ a+b 以下にある 4 つの解答 (cpp-correct, python-correct, cpp-TLE, cpp-WA-multiply) のコンパイル
- 入出力ディレクトリ a+b/tests 以下にある入力生成器と入力検証器のコンパイル
- 入力生成器を使ったランダム入力データの生成
- 入力検証器を使った全入力データのフォーマットチェック
- 解答プログラム a+b/cpp-correct に入力データを入れて走らせ、リファレンスとなる出力データを生成
- 解答プログラム a+b/python-correct を走らせ、リファレンス出力データと同じ出力を出すことを確認
- 誤答プログラム a+b/cpp-WA-multiply を走らせ、間違った出力を出すことを確認
- 誤答プログラム a+b/cpp-TLE を走らせ、指定したタイムリミット (1秒) 内に終了しないことを確認
つまりこのコマンドの実行だけで、解答のチェックに必要な全ての処理を行えたことになります。
Rime が正しく動いていることを確認するため、試しに解答プログラムにバグを入れてみましょう。名前からお察しのとおり、問題 a+b は標準入力から二つの数を受け取り、その和を標準出力に書き出すプログラムを書け、という問題です。python-correct プログラムは次のようなコードになっています:
$ cat a+b/python-correct/main.py
#!/usr/bin/python
import sys
def main():
a, b = map(int, sys.stdin.read().strip().split())
print a + b
if __name__ == '__main__':
main()
これを、掛け算をするプログラムに書き換えます。
$ vi a+b/python-correct/main.py
...
$ cat a+b/python-correct/main.py
#!/usr/bin/python
import sys
def main():
a, b = map(int, sys.stdin.read().strip().split())
print a * b # i can haz moar?
if __name__ == '__main__':
main()
再び Rime を実行してみましょう。
$ ./rime.py test
[ TEST ] a+b/cpp-TLE: 11-maximum.in: Time Limit Exceeded
[ TEST ] a+b/cpp-WA-multiply: Expectedly failed all challenge cases
[ TEST ] a+b/cpp-correct: max 0.01s, acc 0.09s
ERROR: a+b/python-correct: 00-sample1.in: Wrong Answer
judge log: /home/nya/src/rime/example/a+b/rime-out/python-correct/00-sample1.judge
[ TEST ] a+b/python-correct: 00-sample1.in: Wrong Answer
Test Summary:
a+b ... 4 solutions, 24 tests
cpp-correct OK max 0.01s, acc 0.09s
python-correct FAIL 00-sample1.in: Wrong Answer
cpp-TLE OK 11-maximum.in: Time Limit Exceeded
cpp-WA-multiply OK Expectedly failed all challenge cases
Error Summary:
ERROR: a+b/python-correct: 00-sample1.in: Wrong Answer
judge log: /home/nya/src/rime/example/a+b/rime-out/python-correct/00-sample1.judge
Total 1 errors, 0 warnings
python-correct が 00-sample1.in で間違っていた、とのメッセージが出ています。具体的にどのような出力をしたのかはジャッジログファイルに残っています。
$ cat /home/nya/src/rime/example/a+b/rime-out/python-correct/00-sample1.judge
--- /home/nya/src/rime/example/a+b/rime-out/tests/00-sample1.diff 2012-05-12 00:54:54.463139744 +0900
+++ /home/nya/src/rime/example/a+b/rime-out/python-correct/00-sample1.out 2012-05-12 01:08:55.827436428 +0900
@@ -1 +1 @@
-7
+12
Copyright (c) 2011-2012 Rime Project.