はじめに
競技プログラミングでは「インタラクティブ問題」という、ジャッジとの対話形式の問題が存在します。
この形式はローカルテストがしにくくデバッグが難航しがちだったので、デバッグ補助プログラムを書いてみました。
しくみ
yield関数を使ってジャッジプログラムを書き、next()で値を取り出します。
さらにinput()とprint()の関数名を上書きすることで、答案の出力先を強引にジャッジとの対話に向かわせます。
コード全文
コメントは適宜削除してください。
デバッグプログラム
#インタラクティブ ローカルテスト
'''
【使い方】
答案・ジャッジプログラムを書き、実行テストの関数に渡してください。
直前の入出力ログは get_log() で出力できます。
【注意点】
・input, print関数を書き換えます。
本提出時はコメントアウトするか、 del input, print で初期状態に戻してください。
・ジャッジにはテストケースを受け取る機能か、自動生成する機能をつけてください。
・答案 → ジャッジ の入力は judge_input というリストに一時保存されています。
[0, 1, 2, ･･･]の順で、(前回のyield ～ 今)の答案からの出力が保存されています。
yieldで答案に出力するたび、 judge_input の中身を空にするので注意してください。
・答案 ← ジャッジ の出力は yield (出力したい値) としてください。
出力値はstr型が望ましいです。 一応自動str変換機能はつけていますが、気休めです。
・ジャッジはassert文でWAの判定を行ってください。
AC判定を終えた場合、returnでジャッジプログラムを終了してください。
【内部仕様】
・_judge_program_funcにジャッジプログラムを入れ、next関数で出力を順に取り出します。
・入出力ログは judge_log に保存されます。
答案 ← ジャッジ の出力は末尾に <judge> がついています。
・テストケースの情報(隠された文字列)は各自で確認してください。
・_judge_textは print( end = ) に対応するための仮保存スペースです。
改行文字が来るまで文字列を結合し、改行が来たら judge_input にappendします。
'''
#内部関数
judge_input, judge_log, _judge_text = [], [], []
_exec_print = print
def print(*value, sep = ' ', end = '\n', file = None, flush = False): #答案 → ジャッジ
global judge_input, judge_log, _judge_program_func, _judge_text
value = sep.join([ str(Vi) for Vi in value ]) #*value(tuple型)をアンパッキング
_judge_text.append(value)
if end == '\n': #改行文字が来た場合、ここまでの文字列を judge_input と _log に送信
judge_input.append( txt := ''.join( _judge_text ) )
judge_log.append( txt )
_judge_text.clear()
else:
_judge_text.append( end )
def input(): #答案 ← ジャッジ
global judge_input, judge_log, _judge_program_func
if type( value := next( _judge_program_func ) ) != str: #入力をstrに変換
if type(value) == list or type(value) == tuple:
value = ' '.join([str(Vi) for Vi in value])
else: value = str(value)
judge_input.clear() #ジャッジへの入力履歴を初期化
judge_log.append( f'{value} <judge>' )
return value
#実行テスト1. 連続テスト
def test_program( solve_program, judge_program, test_time = 1000 ):
'''
ジャッジが自力でランダムテストを生成できることを前提に、連続テストを行います。
(答案プログラム, ジャッジプログラム, テスト回数)を入力してください。
'''
global judge_input, judge_log, _judge_program_func
for counter in range(1, test_time + 1):
#ジャッジログ・ジャッジ入力履歴を初期化
judge_log.clear()
judge_input.clear()
#ジャッジプログラムを登録し実行
_judge_program_func = judge_program()
solve_program()
try: next( _judge_program_func )
except StopIteration: continue
#実行テスト2. 特定ケースでのチャレンジ
#関数後半にはジャッジに渡したいテストケースを入力してください
def test_corner( solve_program, judge_program, *value ):
'''
ジャッジプログラムがテストケース用の引数を受け取れることを前提とします。
ジャッジプログラムの引数を順に *value に入力してください。
たとえば judge(N: int, array: list) と N, array の順に引数指定がなされている場合、
test_corner( solve_program, judge, 3, [3, 1, 4] ) のように順に渡してください。
'''
global judge_input, judge_log, _judge_program_func
judge_log.clear()
judge_input.clear()
_judge_program_func = judge_program( *value )
solve_program()
try: next( _judge_program_func )
except StopIteration: pass
#ジャッジ入出力ログを順に出力
def get_log(): _exec_print(*judge_log, sep = '\n')
'''
ここからジャッジプログラムを書いてください。
ジャッジへの入力はjudge_input(list型)に、出力はyieldでお願いします。
プログラム終了前にAC判定をお願いします。WAの判定にはassertが便利です。
'''
使い方
ローカルテストの下に答案とジャッジプログラムを書き、実行テストの関数に入れてください。
答案プログラムは関数化し、exit()を使わないようにしてください。
ジャッジプログラムは以下の形式に則って書いてください。
- 答案 → ジャッジ の入力
judge_inputのリストから順に文字列を受け取ってください。 - 答案 ← ジャッジ の出力
yield (出力したい文字列)としてください。 - ジャッジ機能
WAの検知はassert文で行ってください。
ACの判定を終えたらreturnでジャッジプログラムを終了してください。
使用例
自作問題
ジャッジは長さ$N$の整数列$A = [A_1, ･･･, A_N]$を隠し持っています。
$N$回以下の質問で、隠し持っている整数列$A$の全要素を特定してください。はじめに、ジャッジは$N$を出力します。
次に、以下の形式で$N$回以下の質問を行ってください。
? i: $A_i$($1 \leq i \leq N$)の値を尋ねる。ジャッジは$A_i$を返す。
最後に、! A_1 ･･･ A_Nの形式で回答し、プログラムを終了してください。
$A$の全要素を順に尋ねる問題です。
答案例
答案例
def solve():
N = int(input())
A = [None] * (N + 1) #1-indexedにしたい
for i in range(1, N + 1):
print('?', i)
A[i] = int( input() )
print('!', *A[1:]) #A[0]の出力をしないよう注意
return
これをsolve()で実行すればよいです。(終)
これのジャッジプログラムを書いて、実際にテストしてみましょう。
関数名はjudgeにします。
隠し持つ$N$と$A$の決定
コーナーケースへの対処のため、$N, A$を引数に設定することをおすすめします。
ランダムテスト時は、random.randintで適当に決めればよいです。
隠し持つ値の決定
import random
def judge(N = None, A = None):
if N == None:
N = random.randint(1, 10) #1以上10以下の整数
if A == None or len(A) != N:
A = [random.randint(-100, 100) for _ in range(N)]
$N$の出力
値を出力したいときは yield を使います。
値の出力例
yield str(N)
一応自動でstr型に変換する機能はつけてあります。
なので下記の出力法でも大丈夫なのですが、変なバグを避けるため、可能なら文字列型での出力をお願いします。
出力例(おすすめしない)
yield N
$N$回以下の質問
!形式の回答が来るまで入力を受け取ればよいです。
下記では$N + 1$回質問クエリの受付を行い、!クエリが来たらbreakとしました。
入力はjudge_inputの配列に文字列型で格納されています。
たとえば、$A_1$の要素を尋ねるクエリが来る場合はjudge_input = ['? 1'] となっています。
質問と応答
for time in range(N + 1):
q, *i = judge_input[0].split()
if q == '!': #回答クエリ
break
assert q == '?'
assert time < N, f'質問回数が{N = }回を超えました。' #エラーメッセージ
i = int( i[0] ) #特殊な受け取り方をしていたので修正
assert 1 <= i <= N #iの条件を確認
#回答
yield str( A[i - 1] ) #0-indexedなので注意
回答の突き合わせ
この時点で答案プログラムは終了していますが、ジャッジプログラムにはまだACチェックが残っています。
隠し持っていた数列との一致を判定し、問題なければreturnしてください。
最終確認
assert q == '!'
B = [int(x) for x in i] #値をintに変換
assert A == B, f'wrong output: {A = }, {B = }'
return #問題なければジャッジプログラムも終了
ランダムテスト
実際に答案のsolve()とジャッジのjudge()を比較させます。
ランダムテストを10000回行わせるときはこのようにします。
ランダムテスト
test_program( solve, judge, test_time = 10000 )
これらを全てまとめると、以下のようになります。
長いので折りたたみにしてあります。
使用例
使用例
#インタラクティブ ローカルテスト
'''
【使い方】
答案・ジャッジプログラムを書き、実行テストの関数に渡してください。
直前の入出力ログは get_log() で出力できます。
【注意点】
・input, print関数を書き換えます。
本提出時はコメントアウトするか、 del input, print で初期状態に戻してください。
・ジャッジにはテストケースを受け取る機能か、自動生成する機能をつけてください。
・答案 → ジャッジ の入力は judge_input というリストに一時保存されています。
[0, 1, 2, ･･･]の順で、(前回のyield ～ 今)の答案からの出力が保存されています。
yieldで答案に出力するたび、 judge_input の中身を空にするので注意してください。
・答案 ← ジャッジ の出力は yield (出力したい値) としてください。
出力値はstr型が望ましいです。 一応自動str変換機能はつけていますが、気休めです。
・ジャッジはassert文でWAの判定を行ってください。
AC判定を終えた場合、returnでジャッジプログラムを終了してください。
【内部仕様】
・_judge_program_funcにジャッジプログラムを入れ、next関数で出力を順に取り出します。
・入出力ログは judge_log に保存されます。
答案 ← ジャッジ の出力は末尾に <judge> がついています。
・テストケースの情報(隠された文字列)は各自で確認してください。
・_judge_textは print( end = ) に対応するための仮保存スペースです。
改行文字が来るまで文字列を結合し、改行が来たら judge_input にappendします。
'''
#内部関数
judge_input, judge_log, _judge_text = [], [], []
_exec_print = print
def print(*value, sep = ' ', end = '\n', file = None, flush = False): #答案 → ジャッジ
global judge_input, judge_log, _judge_program_func, _judge_text
value = sep.join([ str(Vi) for Vi in value ]) #*value(tuple型)をアンパッキング
_judge_text.append(value)
if end == '\n': #改行文字が来た場合、ここまでの文字列を judge_input と _log に送信
judge_input.append( txt := ''.join( _judge_text ) )
judge_log.append( txt )
_judge_text.clear()
else:
_judge_text.append( end )
def input(): #答案 ← ジャッジ
global judge_input, judge_log, _judge_program_func
if type( value := next( _judge_program_func ) ) != str: #入力をstrに変換
if type(value) == list or type(value) == tuple:
value = ' '.join([str(Vi) for Vi in value])
else: value = str(value)
judge_input.clear() #ジャッジへの入力履歴を初期化
judge_log.append( f'{value} <judge>' )
return value
#実行テスト1. 連続テスト
def test_program( solve_program, judge_program, test_time = 1000 ):
'''
ジャッジが自力でランダムテストを生成できることを前提に、連続テストを行います。
(答案プログラム, ジャッジプログラム, テスト回数)を入力してください。
'''
global judge_input, judge_log, _judge_program_func
for counter in range(1, test_time + 1):
#ジャッジログ・ジャッジ入力履歴を初期化
judge_log.clear()
judge_input.clear()
#ジャッジプログラムを登録し実行
_judge_program_func = judge_program()
solve_program()
try: next( _judge_program_func )
except StopIteration: continue
#実行テスト2. 特定ケースでのチャレンジ
#関数後半にはジャッジに渡したいテストケースを入力してください
def test_corner( solve_program, judge_program, *value ):
'''
ジャッジプログラムがテストケース用の引数を受け取れることを前提とします。
ジャッジプログラムの引数を順に *value に入力してください。
たとえば judge(N: int, array: list) と N, array の順に引数指定がなされている場合、
test_corner( solve_program, judge, 3, [3, 1, 4] ) のように順に渡してください。
'''
global judge_input, judge_log, _judge_program_func
judge_log.clear()
judge_input.clear()
_judge_program_func = judge_program( *value )
solve_program()
try: next( _judge_program_func )
except StopIteration: pass
#ジャッジ入出力ログを順に出力
def get_log(): _exec_print(*judge_log, sep = '\n')
'''
ここからジャッジプログラムを書いてください。
ジャッジへの入力はjudge_input(list型)に、出力はyieldでお願いします。
プログラム終了前にAC判定をお願いします。WAの判定にはassertが便利です。
'''
#ジャッジプログラムを書く
import random
def judge(N = None, A = None):
if N == None:
N = random.randint(1, 10) #1以上10以下の整数
if A == None or len(A) != N:
A = [random.randint(-100, 100) for _ in range(N)]
#Nの出力
yield str(N)
#N回以下の質問
for time in range(N + 1):
q, *i = judge_input[0].split()
if q == '!': #回答クエリ
break
assert q == '?'
assert time < N, f'質問回数が{N = }回を超えました。' #エラーメッセージ
i = int( i[0] ) #特殊な受け取り方をしていたので修正
assert 1 <= i <= N #iの条件を確認
#回答
yield str( A[i - 1] ) #0-indexedなので注意
#最終確認
assert q == '!'
B = [int(x) for x in i] #値をintに変換
assert A == B, f'wrong output: {A = }, {B = }'
return #問題なければジャッジプログラムも終了
#答案を書く
def solve():
N = int(input())
A = [None] * (N + 1) #1-indexedにしたい
for i in range(1, N + 1):
print('?', i)
A[i] = int( input() )
print('!', *A[1:]) #A[0]の出力をしないよう注意
return
#ランダムテストを実行
test_program( solve, judge, test_time = 10000 )
実行してみるとエラーメッセージが出ず、問題なくテストができました。
なのでsolve()部分だけ抜き出して提出してください。
ABC299D Find by Query
問題文はこちら
長さ$N$の01列$S$の中にある、$S_p ≠ S_{p + 1}$なる整数$p$を$20$質問以内に特定してください。
実行例(ジャッジ・答案あり)
ジャッジプログラムは先述の自作問題に似ているので、上記の実行例リンクからご確認ください。
ここではコーナーケースの作成について説明します。
明らかに間違った回答として、$N - 1$から降順に$0$が出るまで探すという方法があります。
誤答例
def solve_WA(): #S[N - 1]から順に、0が出るまでO(N)回探す
N = int( input() )
for i in range(N - 1, 0, -1):
print('?', i)
Si = int( input() )
if Si == 1: continue
if Si == 0: #S[i] == 0, S[i + 1] == 1 となるのでp = iとして出力
print('!', i)
return
$S = [0, 1, 1, ･･･, 1, 1, 1]$のような場合に$N - 1$回の探索を要するので誤答なのですが、ランダムテストでこれを落とすのは難しいです。
この答案を落とすには右から最低でも$21$連続で$1$が続いていないといけないのですが、ランダムテストでそうなる確率は$1 / 2^{20}$と極めて低いからです。
なので、test_corner()というコーナーケースを自分で作ってチャレンジする機能を使います。
今回であれば$N = 22, A = [0] + [1] * 21のケースを試せばよさそうなので、このように実行してみます。
test_corner()に渡す引数の入力順は judge()関数に渡す引数の順にしてください。
特定ケースのチャレンジ
def solve_WA():
#中略
def judge(N = None, A = None):
#中略
#N = 22, A = [0] + [1] * 21 のケースでチャレンジする
test_corner( solve_WA, judge, 22, [0] + [1] * 21 )
AssertionError: too many questionとassert文でWAの検知ができました。
ABC305F Dungeon Explore
問題文はこちら
$N$頂点$M$辺の単純連結無向グラフをなるはやで抜けてください。
グラフの生成は折りたたみのように行います。
単純連結無向グラフの生成
グラフ作成
#N頂点の木を作成し、隣接リストとして返す(Prufer列使用) O(NlogN)
import random, heapq
def make_wood(N: int):
assert N > 0
if N == 1: return [ [] ]
G = [[] for _ in range(N)]
P = [random.randint(0, N - 1) for _ in range(N - 2)] #Prufer列
D = [1] * N #次数
for Pi in P:
D[Pi] += 1
heapq.heapify( Q := [i for i in range(N) if D[i] == 1] )
for Pi in P: #Prufer列を順に当てる
assert D[ Vi := heapq.heappop(Q) ] == 1
G[Vi].append(Pi)
G[Pi].append(Vi)
D[Vi] -= 1
D[Pi] -= 1
assert D[Vi] == 0 and D[Pi] > 0
if D[Pi] == 1:
heapq.heappush(Q, Pi)
assert len(Q) == 2
Ui, Vi = Q[0], Q[1]
G[Ui].append(Vi)
G[Vi].append(Ui)
D[Ui] -= 1
D[Vi] -= 1
for i in range(N):
assert D[i] == 0
G[i].sort()
return G
#N頂点M辺の単純連結無向グラフを作成 expect O(NlogN + M)
def make_graph(N: int, M: int):
assert 0 < N < 1 << 31 and N - 1 <= M <= N * (N - 1) // 2
if N == 1 and M == 0: return [ [] ]
G = make_wood(N)
randb = random.getrandbits(32)
#M / 総辺数 が高いなら、残辺を全列挙して乱択する ここでは50%をカットオフとする
if 2 * M > (N * (N - 1) // 2):
S = {(i << 31 | j) ^ randb for i in range(N) for j in range(i + 1, N)}
for i in range(N):
for j in G[i]:
if i < j: S.discard( (i << 31 | j) ^ randb )
random.shuffle( S := list(S) )
for x in range( M - (N - 1) ):
G[ Ui := (S[x] ^ randb) >> 31 ].append( Vi := (S[x] ^ randb) & 0x7fffffff )
G[Vi].append(Ui)
else: #木で使った辺をsetに登録し、乱択で辺を追加する
S = {(i << 31 | j) ^ randb for i in range(N) for j in G[i] if i < j}
while len(S) < M:
Ui, Vi = random.randint(0, N - 1), random.randint(0, N - 1)
if Ui == Vi: continue
if Ui > Vi: Ui, Vi = Vi, Ui
if (Ui << 31 | Vi) ^ randb not in S:
S.add( (Ui << 31 | Vi) ^ randb )
G[Ui].append(Vi)
G[Vi].append(Ui)
for i in range(N):
G[i].sort()
return G
プリューファー列から木を生成し、そこに辺をランダムに足す方法をとっています。(終)
さて、実装例のsolve_WAを手元で実行すると以下のエラーが出てしまいました。
assert False, 'too many movement'
AssertionError: too many movement
これは移動回数が$2N$回を超えたときのエラーです。
どのような移動をしていたのか、ログを確認してみましょう。
入出力ログはget_log()で確認できます。
get_log() 実行結果
8 10 <judge>
3 3 4 5 <judge>
5
3 1 2 7 <judge>
7
3 2 5 6 <judge>
6
3 2 4 7 <judge>
4
2 1 6 <judge>
6
3 2 4 7 <judge>
2
3 5 6 7 <judge>
6
3 2 4 7 <judge>
7
3 2 5 6 <judge>
2
3 5 6 7 <judge>
7
3 2 5 6 <judge>
5
3 1 2 7 <judge>
2
3 5 6 7 <judge>
5
3 1 2 7 <judge>
1
3 3 4 5 <judge>
4
2 1 6 <judge>
1
ジャッジ側からの返答は末尾に<judge>がついています。
移動経路を辿ると (1→)5→7→6→4→6→2→6→7→2→7→5→2→5→1→4→1→･･･となっており、どうも頂点$6$や頂点$7$に複数回入る無駄がありそうですね。
このように、入出力ログはデバッグの助けになることがあります。
ぜひご利用ください。
おわりに
おわりです。
おもいだしたら追記します。