えびちゃんの日記

えびちゃん（競プロ）の日記です。

リアクティブ問題のデバッグに関して

ABC 269 E や ABC 244 C など、リアクティブ・インタラクティブ形式の問題は ABC でもたまに出題されます。典型 90 :: 53 にもありますね。

普通の形式の問題であれば、oj などを使ってデバッグしている人でも、リアクティブ形式だと手作業で実行する人は多いのではないでしょうか。

実際には（これくらいの難易度帯の）リアクティブのジャッジを書くのは、（それくらいの難易度帯に挑戦するくらいの）競プロ er にとっては造作もないことかと思います。 とはいえ、デバッグ用の情報をいちいち出力したりするのは面倒な上、全ての問題で共通するパートでしょうから、そういうのは予め準備しておきたいです。

つくった

% sniff_reactive ./e -- ./e-judge test/e/sample-1.in
 +--------------------------------------+-------------------------------------+
 | contestant                           | judge                               |
 +--------------------------------------+-------------------------------------+
 |                                      | 3                                   |
 | ? 1 2 1 3                            |                                     |
 |                                      | 2                                   |
 | ? 1 3 1 3                            |                                     |
 |                                      | 2                                   |
 | ? 1 3 1 2                            |                                     |
 |                                      | 2                                   |
 | ? 1 3 1 3                            |                                     |
 |                                      | 2                                   |
 | ! 3 3                                |                                     |
 |                                      | AC                                  |
 +--------------------------------------+-------------------------------------+

e が提出用のプログラム、e-judge がジャッジのプログラムです。test/e/sample-1.in がテストケースで、e-judge はこれを読んでケースの情報を取得し、それに基づいて e とやり取りをする想定です。

% sniff_reactive solution_program -- judge_program

の形式で実行します。sniff は（通信を）盗聴するとかの意味合いがあるようなので、そういう名前にしてみました。

solution_program は複数コマンドでもよく、judge_program は（上記と違って）自分でケースを生成しながらやり取りするタイプでもよいです。

% # examples
% sniff_reactive python3 e.py -- cargo run --bin e-judge
% sniff_reactive ./e -- ./e-judge 'test/e/sample-1.in'

test/e/sample-1.in の内容は、（自分で用意する）ジャッジが読みやすい形式ならなんでもよいです。 ABC 269 E の例では、たとえば以下のような感じでよいでしょう。

3
0 1 0
1 0 0
0 0 0

ケースに関して

別で e-gen などを用意して、テストケースの生成をするのがよいでしょう。oj が便利です。

% oj g/i ./e-gen

ジャッジが自分でケースをランダム生成するタイプだと、前に試して WA になったケースなどを再現させるのに手間がかかるので、分離させておく方がえびちゃん的には好みです。 ランダム生成をするのに手間がかかると、こうした作業をするまでのハードルが高くなってしまうので、楽にできるような環境を整えておくのがおすすめです。 えびちゃんは、rand_gen! というマクロを用意しています。

rand_gen! {
    rng: ChaCha20Rng;    // 乱数生成器を指定

    n in 10_usize..=20;  // n in [10, 20] を生成
    a in [1_i32..10; n]; // a_i in [1, 10) を n 個生成
}

これは、リアクティブ問題に限らず便利です。

つかう

Gist へのリンクを貼っておきます。

  • sniff_reactive.py
    • Python のスクリプトだけ置いています。適切な場所に置いて python3 sniff_reactive.py solution -- judge のように使ってもよいでしょう。よしなに。
    • インストールしている Python のバージョンが古いと動かないかもしれません。バージョンを上げるという解決策があります。
  • e-gen.rs
    • ABC 269 E のジェネレータです。Rust 製なので、Rust に詳しくない人は自分の好きな言語で書いてもよいでしょう。
    • えびちゃんのライブラリに依存しているので、Cargo.toml も添えておきます。
      • Rust に詳しくない人は読み飛ばしていいです。
  • e-judge.rs
    • ABC 269 E のジャッジです（AtCoder のサーバで動いているという意味ではないです）。
    • これも Rust なので、好みの言語で作り直してもよいでしょう。

gist.github.com

試していないのでわかりませんが、Windows だと動かないかもしれません。Windows 以外の PC を買うという解決策があります。

意図的なバグは入れていないはずですが、「このツールを使って WA/RE になったから提出しなかったのに、コンテスト後に投げてみたら AC だった」のような苦情は受け付けません。

おわり

ねこちゃんです。