前文・謝辞
この記事は、『OUPC2021 開催記』で触れたドキュメントのうち、競技プログラミング作問支援ツール Rime の使い方を示したものです。
基本的にドキュメントの内容をそのまま掲載していますが、この公開のために7節を追加しました。初期設定以外の全てのワークフローを網羅しています。初期設定は上記公式GitHubのREADME.mdにあります。
執筆に協力してくれたkotamanegiに三度感謝申し上げます。
1. インストール
pip install rime
pipを通じてインストールすると、rime
と先頭に打つことでRimeのコマンドを扱えるようになる。
2. 問題の作成
まず、OUPC2021のトップディレクトリにアクセスする(LICENSEとか置いてあるディレクトリです)。そこで、以下のコマンドを実行する。
git checkout -b (branchname) # すでに作っていれば git checkout (branchname) rime add . problem (問題名)
最後のコマンドを実行すると、問題名と同名のディレクトリが作られ、その下にRimeで問題を動かすために必要なファイルが生成される。同時にviが開いて、PROBLEMというファイルを編集する画面に移るが、この作業は後でできるのですぐに終了して(ESC :q!)構わない*1*2。
このコマンドを打ち、Slackに投稿した原案を問題文としてmarkdown形式で整形したものを、README.mdとしてアップロードする。ここまでが問題作成の最初の作業となる。
3. 解答の作成
以下のコマンドを打つ。
rime add . solution (解答名)
注意すべき点として、最初に作成する解答は、想定解を生成するプログラムとして参照するものであった方が良い(これを指定しないと、2個目以降のsolutionを作成できない)。これは自分が書いた問題の解答を、普段競プロで解くようなプログラムで書けば良い。
またviが開くが、同様にすぐに終了する。
実際にPROBLEMファイルを見る。PROBLEMファイルはPythonのプログラムと同様の作りになっており、#
がコメントを指す。
# -*- coding: utf-8; mode: python -*- ## Solution #c_solution(src='main.c') # -lm -O2 as default #cxx_solution(src='main.cc', flags=[]) # -std=c++11 -O2 as default #kotlin_solution(src='main.kt') # kotlin #java_solution(src='Main.java', encoding='UTF-8', mainclass='Main') ...
実際に開くとこのように表示される。ここで対応する言語の行の先頭の #
を削除し、有効化する。同時に2つ以上の解答プログラムを登録することはできないことに注意する。
ソースファイル名は何でもよいが、rime add . solution (解答名)
の (解答名)
と同じにすることを推奨する(取り違えを防ぐため)。
そして自分の解答を書いた後、階層をひとつ戻してPROBLEMファイルを開く。PROBLEMファイルの中身はこのようになっている。
# -*- coding: utf-8; mode: python -*- pid='X' problem( time_limit=1.0, id=pid, title=pid + ": Your Problem Name", #wiki_name="Your pukiwiki page name", # for wikify plugin #assignees=['Assignees', 'for', 'this', 'problem'], # for wikify plugin #need_custom_judge=True, # for wikify plugin #reference_solution='???', ) atcoder_config( task_id=None # None means a spare )
ここに、作問者が想定している制限時間、問題名を記述する。また、#reference_solution='???',
と書かれている行の先頭の #
を削除し、 ???の部分を、先ほど自分で書いた解答の ディレクトリ名 で置き換える。
想定解以外の解答の作成
想定解以外の解法(誤答を含む)も上と全く同様にして登録する。つまり、PROBLEMのある階層で rime add . solution hogehoge
、移動してSOLUTIONの編集、解答の追加という順序で行う。
AC解の場合はそのままで良いが、誤答の場合はしておくと良い工夫があるので紹介する。SOLUTIONファイルに誤答の場合は以下のように記載する。
# -*- coding: utf-8; mode: python -*- ## Solution #c_solution(src='main.c') # -lm -O2 as default cxx_solution(src='wa_badly.cpp', flags=[], challenge_cases=[]) # -std=c++11 -O2 as default expected_verdicts([AC, WA]) ...
challenge cases
と expected_verdicts
を追加した。challenge_cases
はどのテストケースで解答を撃墜するかを決める引数で、空のリストを指定するとすべてのテストケースをチェックしてくれる。逆にここで何か有効なテストケースファイルを指定してしまうと、そのテストケースに通ってさえいれば自動でACと判定されるかなり罠っぽい仕様があるので、基本的には空リストであることを推奨する。challenge_cases
引数がない場合、その解答はAC解として扱われる。 expected_verdicts
はその解答にすべてのテストケースを入力として与えたとき、予想される結果を書く欄である。文字列ではなくすべて定数で、AC, WA, TLE
の3つがある。TLE解でもWA解でも、誤答はあるケースで落ちるが、別のケースでは通ることが期待されることが多いため、通常はAC
もセットで指定することになる(ACを指定しないと、すべてのテストケースでWA/TLEということになる)。
4. generatorの作成
Rimeにも搭載されており、generatorやvalidator、カスタムジャッジのプログラミングに広く使われているのが、testlib.hである。
基本的な使い方はREADME.mdに記載されているので、そちらを参照する。
テストケースを作成するgeneratorを追加するには、以下のコマンドを実行する。
rime add . testset (generator名)
まずはTESTSETファイルの中身を見よう。
# -*- coding: utf-8; mode: python -*- ## Input generators. #c_generator(src='generator.c') #cxx_generator(src='generator.cc', dependency=['testlib.h']) #java_generator(src='Generator.java', encoding='UTF-8', mainclass='Generator') #rust_generator(src='generator.rs') #go_generator(src='generator.go') #script_generator(src='generator.pl') ...
解答と同様の設定をすればよいことがわかる。C++のジェネレータなら以下のように設定する。
# -*- coding: utf-8; mode: python -*- ## Input generators. #c_generator(src='generator.c') cxx_generator(src='generator.cc', dependency=['testlib.h']) #java_generator(src='Generator.java', encoding='UTF-8', mainclass='Generator') #rust_generator(src='generator.rs') #go_generator(src='generator.go') #script_generator(src='generator.pl') ...
あとはgenerator.ccにgeneratorの内容を記述するだけである。testlib.hをincludeするのをお忘れなく。generatorは後述するvalidatorと比べるとアドホックな実装が多くなるため参考にしづらいが、testlib.hのリポジトリのgeneratorsディレクトリに「ランダムな木の生成」などの、本当によくあるテストケースの作成方法が紹介されている。参考にしてほしい。
ここまでの振り返り
この段階で、フォルダ構成は以下の通りになっているはずである。
(問題名ディレクトリ) | |-- PROBLEM | |-- .gitignore | |-- README.md | |-- (generator名) | | | |-- TESTSET | | | |-- (サンプルなどの手動で追加したテストケースファイル).in | | | |-- (generatorのファイル) | |-- (解答の名前) | |- SOLUTION | |- (解答のファイル)
ただし、.gitignoreは設定次第では見えない隠しファイル扱いになっている可能性がある。 .gitignore以外がない場合はもう一度やり残したステップがないか確認しよう。
5. テスト
まだ問題は完成ではないが、ここまで作業すればrime test
コマンドによってテストの実行が可能になる。問題ディレクトリ(PROBLEMと同階層)以下で実行するとその問題だけ、さらに上の階層(PROJECTと同階層)で実行すると現在ある問題全てについてテストが実行される。
また、OUPC2021ではCIによるrimeの自動実行機能を兼ね備えており、rime test
が正しく通らない場合にはPRをマージすることができない仕組みになっている。
6. validatorの作成
validator(入力検証器)はrime test
に必須というわけではないが、作問作業の際には欠かせないもののひとつだ。validatorもtestlib.hを使って作成するとスムーズである。
例えば以下のような入力について考える。
N A_1 A_2 ... A_N S
N, A_i
は整数(1以上10000以下)S
は文字列(最大N文字)
これを正しく検証するvalidatorをtestlib.hを用いて書くと、以下のようになる。
#include "testlib.h" #include <string> const int MIN_N = 1; const int MAX_N = 10000; int main(int argc, char *argv[]){ registerValidation(argc, argv); int n = inf.readInt(MIN_N, MAX_N); inf.readEoln(); for(int i=0;i<n;i++){ inf.readInt(MIN_N MAX_N); if(i == n-1){ inf.readEoln(); }else{ inf.readSpace(); } } string token = "[a-zA-Z0-9]{1," + to_string(n) + "}"; inf.readToken(token, "s"); inf.readEoln(); inf.readEof(); return 0; }
よくあるケースについて詳しくはtestlib.hのリポジトリのvalidatorsディレクトリにあるので参考にしてほしい。スペースの数に厳密である点と、最後にEoln+Eofが必要である点に注意する。
7. コンテストデータを出力する
一通り作問作業が終わったら、各種コンテストサイトにテストデータを登録するための書き出しを行う。
cd OUPC2021 # リポジトリのトップディレクトリに移動する rime pack
rime pack
の結果は、各問題ディレクトリのrime-out
ディレクトリ以下に保存される。デフォルトではatcoderが有効になっているため、rime-out/atcoder
というディレクトリが作成され、そこにテストケースのデータが入る。トップディレクトリの PROJECT
ファイルからテストケースを書き出す際に使用するモードを選択することができる。atcoder, aoj, hacker_rankの3種類が存在するので使い分ける。ただし、AOJにVoluntary Contestとして提出する際にはatcoderを使う*3。
しかしこれらのディレクトリは、全ての問題で名前が共通である、比較的深い位置に存在する、テストケースの中身を見ても問題が分からない、と人為的ミスの温床となる。そこで、提出用ファイルを作成するスクリプトを書いておくことが望ましい。スクリプトは何でも良いが、以下のような仕様になっていると良さそうだ。
- 各問題のテストケースの入ったディレクトリが、コンテスト内での順番で並んでいる
- ディレクトリ内には、テストケース(AOJの場合はatcoderディレクトリそのまま)と問題文が入っている
- トップディレクトリに、実行時間制限や実際の問題名などを対応づけたファイルを載せる
これらの要件をもとに、OUPC2021では以下のPython3スクリプトを作成した。
import shutil, os, random problemList = [[2, 'Doping-Slayer'], [3, 'Expectation of ST Informant'], [4, 'lcm-tour'], [1, 'longest-match'], [6, 'spreadsheet'], [7, 'SumOfColoringProblem'],\ [5, 'Teaching-Assistant'], [8, 'ExponentialPath'], [0, 'Jigsaw_Puzzle_and_Detective']] problemInfo = { 'Doping-Slayer':['Doping-Slayer', 2.0], 'Expectation of ST Informant':['Expectation-of-ST-Informant', 2.0], 'ExponentialPath':['Exponential-Path', 2.0], 'Jigsaw_Puzzle_and_Detective':['Jigsaw-Puzzle-and-Detective', 2.0], 'lcm-tour':['LCM-Tour', 2.0], 'longest-match':['Longest-Match', 2.0], 'spreadsheet':['Spreadsheet', 2.0], 'SumOfColoringProblem':['Sum-of-Coloring-Problem', 2.0], 'Teaching-Assistant':['Teaching-Assistant', 2.0] } problemList.sort() # 問題を本番の順番に並べ替える suffix = '/rime-out/atcoder/' target = 'OUPC2021Trial' # atcoderディレクトリのコピー os.makedirs('./'+target, exist_ok=True) for i in range(len(problemList)): shutil.copytree(problemList[i][1]+suffix, './'+target+'/'+str(i+1).zfill(2)+problemInfo[problemList[i][1]][0]) problemSentence = [] with open(problemList[i][1]+'/problem.html', mode='r') as f: problemSentence = f.readlines() # 問題文を整形して含める with open('./'+target+'/'+str(i+1).zfill(2)+problemInfo[problemList[i][1]][0]+'/problem.txt', mode='w') as f: lineIndex = 0 while lineIndex < len(problemSentence): if '<body>' in problemSentence[lineIndex]: lineIndex += 1 break lineIndex += 1 while lineIndex < len(problemSentence): if '</body>' in problemSentence[lineIndex]: break f.write(problemSentence[lineIndex]) lineIndex += 1 # 時間制限などを示したファイルを作る with open('./'+target+'/problem,timelimit.csv', 'w') as f: f.write('directory name,actual problem name,time limit\n') for i in range(len(problemList)): f.write(str(i+1).zfill(2)+problemInfo[problemList[i][1]][0]+','+problemInfo[problemList[i][1]][0].replace('-', ' ')+','+str(problemInfo[problemList[i][1]][1])+'\n')
AOJには問題文のhtmlファイルそのままではなく一部整形して提出しているが、これについてはベストな方法かどうか議論の余地があるため、AOJでコンテストを開くときには担当者とよく相談してほしい。