文書の過去の版を表示しています。
競プロインタラクティブ問題のローカルテスト
インタラクティブ形式の問題とは、入力が最初の1回きりではなく、 こちらの質問(クエリ出力)に従ってジャッジが回答となる新たな入力を与えるのを繰り返し、 その情報を元に隠された何かを突き止めるタイプの問題。
こういう形式は、提出前に正しく動作するかテストがしにくい。
また最大ケースに対してクエリ数がどれくらいになるかも、ちゃんと調べたい。
ジャッジ側のプログラムは自分で書くしかないが、それが比較的簡単に書けるなら、 ジャッジ側も自動化させれば、複雑なケースのテストも行いやすい。
ジャッジ側プログラムの流れ
- 最初に隠された答えを決める(手作りなり、ランダム生成なり)
- 提出用スクリプトを
subprocess.Popen()
で起動 - 最初の入力を与える
- クエリが来たら返答する
- 答えの出力が来たら、答え合わせして終了
- 下の実装例は、
?
がクエリ、!
が回答の合図である例
もちろん、上記の流れに沿わない問題(最初の入力が不要など)は、適宜コードを変更する。
クエリが来た回数をカウントできる。
補足・諸注意
プロセスを開始する Popen()
の引数を stdin=PIPE, stdout=PIPE
とすることにより、プロセス同士の対話が可能になる。
入出力のやりとりはstring型でなくbytes型なので、ジャッジ側が送ったり受け取ったりする文字列には decode(), encode()
が必要となる。
競プロではまずascii文字しか使わないので、デコードに用いる文字コードは utf8
や ascii
でよい。
(AtCoderではデフォルト文字コードが utf-8
なので無指定でもよいが、Codeforcesだと未定義なのでちゃんと指定しないとエラーになる)
末尾の改行は、明示的に付与しないと提出コード側が入力待ちのまま動かなくなる。忘れないよう注意。
ジャッジ側・提出側のデバッグ出力を、ジャッジ側の任意のタイミングでできる。
提出側のデバッグ出力は、提出側でprint()→ジャッジ側で受け取りprint() という過程を踏む。
その際、下記の実装例では、クエリや回答と混同しないよう、所定の形式に該当しない場合はスルーしている。
(実際のジャッジプログラムでは、余計な出力はWAとなるため、その点は全く同じ挙動では無いことに注意)
実装例
提出用スクリプト aaa/bbb/ccc.py
に対し、ジャッジ用スクリプトは aaa/bbb/ccc_judge.py
というファイル名での作成を前提としている。(異なる場合は script_path
の生成方法を変更)
import random import sys import subprocess def judge(): """ インタラクティブ問題のローカルテスト """ # [Edit] 最初にジャッジ側で決定される隠された答えなど n = 2000 ans = list(range(1, n + 1)) random.shuffle(ans) # 設定 encoding = 'utf-8' query_count = 0 # クエリ回数カウント # 提出用ファイルパス(ジャッジ用ファイル名 = 提出用ファイル名 + '_judge.py' の場合) script_path = __file__[:-9] + '.py' with subprocess.Popen([sys.executable, script_path], stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE) as p: # [Edit] はじめにジャッジ側から入力を与える処理 p.stdin.write(f'{n}\n'.encode(encoding)) p.stdin.flush() while True: query = p.stdout.readline().decode(encoding).strip() print('>', query) # [Edit] クエリへの返答処理 if query[0] == '?': i, j, k = map(int, query[2:].split()) if ans[i - 1] + ans[j - 1] > ans[k - 1]: response = 'Yes' else: response = 'No' p.stdin.write(f'{response}\n'.encode(encoding)) p.stdin.flush() query_count += 1 print('<', response) elif query[0] == '!': # [Edit] 解答があっているかチェックする処理 exec_ans = list(map(int, query[2:].split())) print('TrueAns:', ans) print('ExecAns:', exec_ans) print('Judge:', ans == exec_ans) print('QueryCount:', query_count) break else: pass if __name__ == '__main__': judge()