うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

yukicoder で testlib を使うためのメモ

yukicoder

この記事は

この記事は yukicoder での作問において testlib を用いて簡単に正確な入力の検証、およびスペシャルジャッジ作成をしよう、という記事です。 また、ローカルでの作業に Rime を使うことを想定しています。

実際のコードについては以下を参照してください

github.com

testlib とは？

testlib は、Codeforcces の admin の MikeMirzayanov 氏が作ったライブラリ（C++ のヘッダーファイル）です。

github.com

codeforces.com

主に以下を行う際に便利な関数が含まれています。

  • 入力生成器 (generator) の作成
  • 入力検証器 (validator) の作成
  • 出力検証器 (checker / judge) の作成

入力検証器、出力検証器は作らなくても問題を出題することはできますが、問題を用意する際には必ず用意するべきだと考えています。

なぜ入力検証器が必要なのか

入力検証器とは、生成した（または手で作った）入力ファイルが入力フォーマットを満たしているかを判定するプログラムのことを指します。

競技プログラミングに参加する人の多くは C++ を使っており、問題の準備において writer / tester による想定解が C++ のみしか用意されない、ということも少なくありません。 ところで C++ の istream（std::cin 等）は半角スペース、改行等を自動で読み飛ばしてくれます。

よって、例え制約等は assert 等でチェックしていたとしても、以下のようなケースを検出することができません。 そして、そのようなケースで正常に動作しないような言語は存在するため、コンテスト中に指摘された場合は入力を修正してリジャッジを行う必要が出てきます。 （以下は全て実際のコンテストで遭遇したことがあります）

  • 行頭または行末に不要な半角スペースが含まれている
  • 問題文中では空白区切りで入力されると書かれているが、実際には改行区切りで入力される

なぜ出力検証器が必要なのか

出力検証器とは、提出されたプログラムの出力が正答であるかを判定するプログラムのことを指します。

基本的には事前に用意した想定出力との diff を取ることで判定することができますが、最近は多くのジャッジで不要な半角スペースや改行を許容するジャッジになっていることが多く、これはそのような判定プログラムを書くことで実現しています。 また、想定出力が複数あるような場合は単純な diff では判定できないため、その場合も判定プログラムを書く必要があります。

これも C++ 等で普通に書けば良いような気がしますが、以下のようなケースで正常に判定できないことがあります。

  • プログラムの出力が足りない場合
    • std::cin は EOF に到達した状態でさらに値を読んでもなんらかの値を返すため
  • 実数が出力されるべきところで nan と出力された場合
    • 実際に、誤差ジャッジにおいて nan と出力して AC となってしまったような問題が存在しました

現在 testlib に関する詳細なドキュメントは存在しません（上に貼った Codeforces のページが一番詳しく、それ以上の情報は実際の実装を読むしかありません）。

自分もそこまで詳しくはないので、誰か複数人で非公式 doc でも用意できればいいんですが……

Rime とは？

Rime は、JAG（日本の ICPC の OB/OG 会）が作成した、プログラミングコンテストの問題作成支援ツールです。 ドキュメントやブログ記事が詳しいので詳しくは以下を見てください。

github.com

rime.readthedocs.io

beet-aizu.hatenablog.com

なぜ Rime なのか

Rime 以外にも作問支援ツールは多く存在するため、特に Rime を使う必要はありません。他の作問支援ツールについてはいくつかは以下の issue で触れられています。

github.com

その中で、今回は以下の理由から Rime を用いました（別に他のツールでも良いと思います）。

  • 大学合宿コンテスト等の有志コンテストの準備においてよく用いられている
  • 他の作問支援ツールに比べて機能が多い

yukicoder で testlib を用いる

最近、yukicoder の環境で testlib.h が使えるようになりました（ありがとうございます！！）。

ただ、実際には testlib (or Rime) で想定されている用い方と yukicoder の仕様が異なるケースも多く、そのまますぐスペシャルジャッジ等に使えるというわけではありません。

よって、この記事では以下を実現することを目的とします。

  • yukicoder 上で testlib を用いたジェネレータ、スペシャルジャッジ、リアクティブジャッジ、スコアリングジャッジを作る
    • バリデーターについては現状 yukicoder でバリデーターを登録する機能がないため、通常の AC コードの入力を受け取る部分を testlib に置き換えることで対応する必要があります。
  • yukicoder と Rime で同じコードでジェネレータ、スペシャルジャッジ、リアクティブジャッジ、スコアリングジャッジが動くようにする
    • ジェネレータについては、同じケースが生成されるようにする

詳しくは以下の README を参照してください！（あとでもう少し情報を追加するかもしれません）

github.com