結果
| 問題 |
No.3018 目隠し宝探し
|
| ユーザー |
 navel_tos
|
| 提出日時 | 2025-01-25 17:59:23 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 142 ms / 2,000 ms |
| コード長 | 9,430 bytes |
| コンパイル時間 | 277 ms |
| コンパイル使用メモリ | 82,816 KB |
| 実行使用メモリ | 78,976 KB |
| 平均クエリ数 | 2.64 |
| 最終ジャッジ日時 | 2025-01-25 23:59:38 |
| 合計ジャッジ時間 | 4,451 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 21 |
ソースコード
#インタラクティブ デバッグセット
'''
グローバルのinput・printを上から書き換え、ジャッジ側をyieldで律速する仕組みです。
■使い方
1. 書式通りに答案プログラム・ジャッジプログラムを用意してください。
- 答案: 普段通りinput()とprint()を使ってください exit()があれば書き換えてください
- ジャッジ: 入力受取はinput()、答案への出力はyield、WAの判定はassertを使ってください
2. テストケースを渡し実行してください。WAが出た場合エラーを出して停止します。
3. テストケースは testcase に、直近のin-outログは judge_log に格納されています。
printデバッグを行う場合、 pprint() とすると従来のprintと同様の関数が扱えます。
'''
#内部関数
pprint, _judge_text, _nonflush_text, judge_log = print, [], [], []
def _solve_input(): #答案 ← ジャッジ 主な律速部分
global input, print, _judge_generator
input = _judge_input #ジャッジ実行前の調整
_judge_text.reverse()
if type( txt := next( _judge_generator ) ) != str:
if type(txt) == list or type(txt) == tuple:
txt = ' '.join([ str(Ti) for Ti in txt ])
else:
txt = str(txt)
input = _solve_input #答案実行用に修正
assert len( _judge_text ) == 0, 'Too many questions printed.'
judge_log.append( f'{txt} <judge>' )
return txt
def _solve_print(*value, sep = ' ', end = '\n', file = None, flush = False):
_nonflush_text.append( sep.join([ str(Vi) for Vi in value ]) )
if end == '\n': #ここまでの文字列を結合し、judge_textに正式に送る
_judge_text.append( txt := ''.join( _nonflush_text ) )
judge_log.append( txt )
_nonflush_text.clear()
else:
_nonflush_text.append( end )
def _judge_input(): #答案 → ジャッジ
assert len( _judge_text ) > 0, 'No output from solver_program.'
return _judge_text.pop()
def _control_panel( solve_program, judge_program, current_testcase ): #1ケース実行
global input, print, _judge_generator, testcase
_judge_text.clear(); _nonflush_text.clear(); judge_log.clear()
testcase = current_testcase
_judge_generator = judge_program( * current_testcase )
input, print = _solve_input, _solve_print
solve_program()
input = _judge_input
try:
txt = next( _judge_generator )
assert False, f'judge program did not stop properly: {txt = }'
except StopIteration:
return
def _test_one( solve_program, judge_program, current_testcase ):
global input, print
try:
_control_panel( solve_program, judge_program, current_testcase )
input = print = 1; del input, print
except Exception as exp: #エラーの出現を留保して終了処理
input = print = 1; del input, print
print('Wrong Answer.')
raise exp
def _test_mul( solve_program, judge_program, make_testcase_program, test_time ):
global input, print
for t in range(1, test_time + 1):
case = make_testcase_program()
try:
_control_panel( solve_program, judge_program, case )
except Exception as exp:
input = print = 1; del input, print
print('Wrong Answer in testcase', t)
raise exp
else:
input = print = 1; del input, print
print('Accepted all testcases.')
#実行テスト1. 1ケース実行
def test1( solve_program, judge_program, current_testcase: list ):
'''
testcaseにはjudge_programの引数指定順に値を入力してください。
judge( N, K, A )の場合、test( solve, judge, [N, K, A] ) のようにしてください。
'''
_test_one( solve_program, judge_program, current_testcase )
#実行テスト2: ランダムテスト
def test2( solve_program, judge_program, make_testcase_program, test_time = 1000 ):
'''
テストケース生成器を基にランダムテストを行います。
生成器の出力順は、judge_programの引数指定順にしてください。
'''
_test_mul( solve_program, judge_program, make_testcase_program, test_time )
#ジャッジ入出力ログを展開
def open_log():
print( * judge_log, sep = '\n' )
'''
ここからジャッジプログラムを作成してください。
答案 → ジャッジ の入力には print() を、
答案 ← ジャッジ の出力には yield を使ってください。
従来の組み込み関数のprintでデバッグする場合、printの代わりにpprintと入力してください。
'''
#verified with:
#1. ABC299D Find by Query
#https://atcoder.jp/contests/abc299/submissions/61996827
#2. ABC305F Dungeon Explore
#https://atcoder.jp/contests/abc305/tasks/abc305_f
#3. ABC313D Odd or Even
#https://atcoder.jp/contests/abc313/tasks/abc313_d
#4. practice contest B Interactive Sorting
#https://atcoder.jp/contests/practice/submissions/62002330
#5. yukicoder3018 目隠し宝探し
#https://yukicoder.me/problems/no/3018
from random import randint
def make_test( maxH = 6, maxW = 6 ):
h = randint( 1, H := randint(1, maxH) )
w = randint( 1, W := randint(1, maxW) )
return H, W, h, w
#H, Wを与える。宝(h, w)の位置を問わず答えを導ける最小の質問回数を返す
memo_P = dict()
def calc_P(H, W):
if (H, W) in memo_P:
return memo_P[ (H, W) ]
#ジャッジでは1-indexedだが、ここでは0-indexedで扱う
#P: 質問履歴をソートしたもの
#DP[P]: P個の質問を投げた状態から、「どこに宝があったとしても解が一意に定まる状態」に
# なるまでの最小の質問回数
#･･･ と定義し、メモ化再帰を行う。状態数は 2 ** HW
DP = dict()
stack = [(0, tuple())]
while stack:
flag, P = stack.pop()
if flag == 0: #行きがけの処理
if P in DP: #既に解が出ているなら
continue
#sub[h][w]: 真の宝が(h, w)にあると仮定したとき、すべての質問履歴と矛盾ない
# マスの個数。特に、(h, w)は矛盾がないので1以上を取る
sub = [[0] * W for _ in range(H)]
for h in range(H):
for w in range(W):
for x in range(H): #暫定のマス
for y in range(W):
if all( (h - i) ** 2 + (w - j) ** 2 ==
(x - i) ** 2 + (y - j) ** 2 for i, j in P ):
sub[h][w] += 1
if all( sub[h][w] == 1 for h in range(H) for w in range(W) ):
DP[P] = 0 #どこに宝があっても一意に定まる状態
continue
#次の質問を飛ばす
stack.append((~ 0, P))
for i in range(H):
for j in range(W):
if (i, j) in P: #質問済みなら
continue
nP = tuple( sorted(list(P) + [(i, j)]) )
if nP not in DP:
stack.append((0, nP))
else: #返りがけの処理
#DP[P] = min( DP[次の状態] ) + 1 とすればよい
cnt = 10 ** 18
for i in range(H):
for j in range(W):
if (i, j) in P: continue
nP = tuple( sorted(list(P) + [(i, j)]) )
cnt = min(cnt, DP[nP])
DP[P] = cnt + 1
memo_P[ (H, W) ] = DP[ tuple() ]
return DP[ tuple() ]
#上記のP計算を用いてジャッジを行う
def judge(H, W, h, w):
P = calc_P(H, W)
Q = []
yield H, W
for q in range(P + 1):
t, i, j = input().split()
assert 1 <= ( i := int(i) ) <= H and 1 <= ( j := int(j) ) <= W, 'out of grid'
if t == '!':
break
assert t == '?'
assert q < P, 'question over P times.'
yield (i - h) ** 2 + (j - w) ** 2
Q.append((i, j)) #質問履歴
#以上の質問で一意に定まっているか判定
assert t == '!'
candidate = []
for x in range(1, H + 1):
for y in range(1, W + 1):
if all((i - h) ** 2 + (j - w) ** 2 == (i - x) ** 2 + (j - y) ** 2
for i, j in Q):
candidate.append((x, y))
assert len(candidate) == 1, f'left other candidates: {candidate =}'
return
#答案作成
def solve():
H, W = map(int, input().split())
if H == W == 1:
print('!', 1, 1)
return
print('?', 1, 1)
c1 = int(input())
if c1 == 0:
print('!', 1, 1)
return
if H == 1:
for w in range(1, W + 1):
if (1 - w) ** 2 == c1:
print('!', 1, w)
return
if W == 1:
for h in range(1, H + 1):
if (1 - h) ** 2 == c1:
print('!', h, 1)
return
print('?', 1, 2)
c2 = int(input())
for h in range(1, H + 1):
for w in range(1, W + 1):
if (1 - h) ** 2 + (1 - w) ** 2 == c1 and\
(1 - h) ** 2 + (2 - w) ** 2 == c2:
print('!', h, w)
return
#テストを実行
#test2(solve, judge, make_test, 10000)
#大丈夫そうなので提出
solve()