Rime とは¶
Rime はプログラミングコンテストの問題セットの作成を補助するツールです。
ACM-ICPC 形式や TopCoder 形式のプログラミングコンテストを開く際、問題を出すために準備しなければならないものは何があるでしょうか。問題案は既にあるものとすると、必要なものは主に次の 4 つに大別されます。
- 問題文
最初から凝った文章を作る必要はもちろんありませんが、少なくとも問題の骨子と入出力形式はあらかじめ決めておかなければなりません。
- 模範解答プログラム
問題が解けることを証明するため、入出力データを作るため、その他あらゆる理由のために模範解答プログラムが必要です。ここで最も重要なことは、模範解答は複数用意されるべきだということです。複数の解答を複数の人間が用意して、その出力を照合することによって、解答プログラムの誤りを大幅に減らすことができます。また必須ではありませんが、想定解法と比べて計算量が大きすぎる解法や、一見正しそうに見えてエッジケースで間違う解法などの、想定「誤答」のプログラムを作成しておけば、それらを振り落とす入力データを作ることが容易になります。
- 入出力データ
小さな入力データは手で直接作ることができますが、大きなエッジケースやランダムケースに対応する入力データはプログラムで作ることになります。出力データは入力データを模範解答プログラムに入れて作成します。
- 入出力検証器
入力データのフォーマットが合っているかどうかは、模範解答プログラムとは別のプログラムであらためて検証することが望ましいでしょう。また、出力形式が浮動小数点数を含む場合など、単純な diff プログラムで間に合わない場合には、出力検証器を用意する必要もあります。
Rime は、この 4 つの項目のうち、問題文を除いた残りのすべての準備作業を補助します。たとえば、次のようなことができます。
手動で作成した入力データや入力ジェネレータを適切な場所に置いておけば、コマンド 1 つで入力ジェネレータを実行しデータセットを作成することができます。
生成された入力データセットを自動的に入力検証器に通し、フォーマット違反がないかどうかをチェックします。
複数の模範解答プログラムを自動的にコンパイルし、それらの出力が一致するかどうかをチェックします。
"想定誤答プログラム" を置いておくと、そのプログラムがジャッジを通過しないことをチェックし、万が一通ってしまった場合は警告を出します。
各問題について、模範解答プログラムを走らせた結果を分かりやすく表示します。