🔄

online judge tools t/r 機能まとめ

2024/02/11に公開

競技プログラミング

AtCoder

tech

背景

今さらながら改めて online judge tools の t/r 機能を利用してみたいので備忘録として使い方をまとめてみます。

方法

oj の t/r (test-reactive) サブコマンドは、サーバとやり取りをするような問題を想定しているいわゆる AHC や AtCoder のインタラクティブな問題を解くのに使う機能です。

以下の document に使い方がのっているので document で紹介されている例題を実際に解いてみます。

例題

問題を先に自分で解きたい方もいると思うので念のため解法は以下に見えないようにまとめています。

解法

サーバ側が制約 $1 \le x \le 1000000$ で $x$ の値を秘密裏に持っているのでそれを当てる問題です。ある値 $y$ を出力するとサーバは $y$ が $x$ 未満なら $\lt$ , $y$ 以上なら $\ge$ を返してくれるので二分探索で $x$ の範囲を狭めていけば $log2(1000000) = 19.93156$ より 20 回やり取りをすれば答えを得ることができます。

最後に、答えがわかったら ! 100 のように先頭に $!$ のプレフィックスを付けて出力するように指示されています。

まず、先にサーバ側のコードを書いてみます。要件定義をすると

最初に制約の範囲で秘密裏に $n$ をアサインする
input で $a$ を含まない値を $x$ が入力されるとそれが $n$ 未満なら $\lt$ , $y$ 以上なら $\ge$ を print する
$a$ を先頭に含む値の場合は $n$ と一致しているか調べ、一致していたら終了する。一致していない場合 assert で強制終了する
期待以外の入力などがあったら assert で強制終了する

といったところでしょうか。

online judge tools の document とほぼ同じですが以下のように judge.py を実装しました。
先頭は自分が使っている Python のパスに合わせて変更してください。
(type python などで確認できます)

judge.py

#! /root/.pyenv/versions/3.11.4/bin/python
import sys
import random


def debug(*args, end="\n") -> None:
    print(*args, end=end, file=sys.stderr)


n = random.randint(1, 10**6)
debug(f"{n=}")
for i in range(25 + 1):
    s = input()
    if s.startswith("!"):
        x = int(s.split()[1])
        assert x == n
        exit()
    else:
        print("<" if n < int(s) else ">=")
assert False

print, debug 関数を使い分けて標準出力とエラー出力に出力を切り替えてわかりやすくしています。
(judge.py と後述する自身のコード tutorial.py の間でやり取りする出力は print だけなので debug は文字通りデバッグに使えます)

続いて judge.py を python judge.py だけでなく .judge.py としても実行できるように例えば 700 と権限を変えておきます。

chomd 700 judge.py

続いて回答となる tutorial.py を先程述べたように二分探索で実装してみます。

tutorial.py

bottom = -1
top = 1000001

while top - bottom > 1:
    mid = (top + bottom) // 2
    print(mid)
    resp = input()
    if resp == "<":
        top = mid
    else:
        bottom = mid

print(f"! {bottom}")

テスト

最後に oj t/r サブコマンドを用いて tutorial.py がワークするか確認します。
-c オプションに実行するコマンドを指定できるので python tutorial.py とします。

> oj t/r ./judge.py -c "python tutorial.py"
[INFO] online-judge-tools 11.5.1 (+ online-judge-api-client 10.10.1)
n=765369
[SUCCESS] AC

AC することができました。３行目の n=765369 は debug 関数で出力しており、こちらのみがターミナルに出力されており、 print 部分は judge.py と tutorial.py の間でやり取りされているので出力されておりません。目視でどのような値がやり取りされているかを確認したければ print しているものとまったく同じものを debug するとよいです。

例えば、 print しているものをすべて debug すると以下のようになります。

> oj t/r ./judge.py -c "python tutorial.py"
[INFO] online-judge-tools 11.5.1 (+ online-judge-api-client 10.10.1)
500000
n=119572
<
249999
<
124999
<
62499
>=
93749
>=
109374
>=
117186
>=
121092
<
119139
>=
120115
<
119627
<
119383
>=
119505
>=
119566
>=
119596
<
119581
<
119573
<
119569
>=
119571
>=
119572
>=
! 119572
[SUCCESS] AC

今さらながら非常に高機能なサブコマンドだなと思いました。これからどんどん使っていきたいです。

💡 まとめ

online judge tools の t/r サブコマンドの使い方をまとめてみました
print と debug 関数を使い分けてデバッグライトしやすくしました

背景

方法

テスト

💡 まとめ

Discussion