結果
| 問題 |
No.5006 Hidden Maze
|
| ユーザー |
 ra5anchor
|
| 提出日時 | 2025-04-19 05:51:19 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,495 ms / 2,000 ms |
| コード長 | 10,085 bytes |
| コンパイル時間 | 259 ms |
| コンパイル使用メモリ | 82,852 KB |
| 実行使用メモリ | 107,296 KB |
| スコア | 88,985 |
| 平均クエリ数 | 111.13 |
| 最終ジャッジ日時 | 2025-04-19 05:52:19 |
| 合計ジャッジ時間 | 53,375 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
import sys
import random
import math
from time import perf_counter
import argparse
from collections import deque
from heapq import heapify, heappop, heappush
class TimeKeeper:
def __init__(self):
self.start_time = perf_counter()
def is_time_over(self, LIMIT):
return (perf_counter() - self.start_time) >= LIMIT
def time_now(self):
return (perf_counter() - self.start_time)
DIJ = [(0, 1), (1, 0), (0, -1), (-1, 0)]
DC = ['R', 'D', 'L', 'U']
ctod = dict()
ctod['R'] = 0
ctod['D'] = 1
ctod['L'] = 2
ctod['U'] = 3
dtoc = dict()
dtoc[(0,1)] = 'R'
dtoc[(1,0)] = 'D'
dtoc[(0,-1)] = 'L'
dtoc[(-1,0)] = 'U'
class Solver:
def __init__(self, DEBUG, T, H, W, p, WH, WV, STEPS):
self.DEBUG = DEBUG
self.T = T
self.H = H
self.W = W
self.p = p
self.WH = WH
self.WV = WV
self.STEPS = STEPS
# 通過できる確率
# 確率0.8で通過できる
self.ph = [[0.80] * (W+1) for _ in range(H)] # 縦棒
self.pv = [[0.80] * W for _ in range(H+1)] # 横棒
# 周囲の壁
for i in range(H):
self.ph[i][0] = 0
self.ph[i][W] = 0
for i in range(W):
self.pv[0][i] = 0
self.pv[H][i] = 0
def output(self, t, ans):
if self.DEBUG:
print(ans)
nowi, nowj = 0, 0
cnt = 0
cnt_wall = -1
for i, c in enumerate(ans):
if c == 'U' and self.WV[nowi][nowj] == 1:
if cnt_wall == -1:
cnt_wall = cnt
break
if c == 'D' and self.WV[nowi+1][nowj] == 1:
if cnt_wall == -1:
cnt_wall = cnt
break
if c == 'L' and self.WH[nowi][nowj] == 1:
if cnt_wall == -1:
cnt_wall = cnt
break
if c == 'R' and self.WH[nowi][nowj+1] == 1:
if cnt_wall == -1:
cnt_wall = cnt
break
d = ctod[c]
di, dj = DIJ[d]
nowi += di
nowj += dj
cnt += 1
if cnt_wall == -1:
return -1
else:
return min(self.STEPS[t], cnt_wall)
else:
print(ans, flush=True)
print(ans, file=sys.stderr)
res = int(input())
return res
def path_to_ans(self, path):
res = []
n = len(path)
for i in range(n-1):
nowi, nowj = path[i]
toi, toj = path[i+1]
di, dj = toi - nowi, toj - nowj
c = dtoc[(di, dj)]
res.append(c)
ans = "".join(res)
return ans
def get_path(self, prev, now):
path = []
while now != (-1, -1):
path.append(now)
now = prev[now[0]][now[1]]
path.reverse()
return path
def get_cost(self, i, j, di, dj):
# 通過できる確率pに対して
# 対数変換して(-1)を乗じたものをコストとすることで
# コストの和の最小化＝経路の通過できる確率の積の最大化 が求められる
if di == 1:
p = self.pv[i+1][j]
if di == -1:
p = self.pv[i][j]
if dj == 1:
p = self.ph[i][j+1]
if dj == -1:
p = self.ph[i][j]
if p == 0: # 100%壁
cost = 10**18
else:
cost = math.log(p) * (-1)
return cost
def get_prob(self, i, j, di, dj):
# 通過できる確率p
if di == 1:
p = self.pv[i+1][j]
if di == -1:
p = self.pv[i][j]
if dj == 1:
p = self.ph[i][j+1]
if dj == -1:
p = self.ph[i][j]
return p
def dijk(self):
# 到達できる確率を最大化する経路を選択
(gi, gj) = (self.H-1, self.W-1)
dist = [[10**18] * self.W for _ in range(self.H)]
prev = [[(-1,-1)] * self.W for _ in range(self.H)]
visited = set()
que = []
dist[0][0] = 0
heappush(que, (0, (0,0)))
while que:
_, now = heappop(que)
if now in visited:
continue
visited.add(now)
for di, dj in DIJ:
toi, toj = now[0]+di, now[1]+dj
if toi < 0 or toi >= self.H or toj < 0 or toj >= self.W:
continue
cost = self.get_cost(now[0], now[1], di, dj)
if cost == 10**18:
continue
if dist[now[0]][now[1]] + cost < dist[toi][toj]:
dist[toi][toj] = dist[now[0]][now[1]] + cost
prev[toi][toj] = now
heappush(que, (dist[toi][toj], (toi, toj)))
path = self.get_path(prev, (gi,gj))
return path
def calp(self, p0):
return max(0, min(1, p0 * self.p / (p0 * self.p + (1 - p0))))
def update_prob(self, path, res):
# 各辺の通過できる確率の更新（ベイズ）
# 1. 通過できた辺は確率を1に修正
for k in range(res):
(nowi, nowj) = path[k]
(toi, toj) = path[k+1]
di = toi - nowi
dj = toj - nowj
if di == 1:
self.pv[nowi+1][nowj] = 1
if di == -1:
self.pv[nowi][nowj] = 1
if dj == 1:
self.ph[nowi][nowj+1] = 1
if dj == -1:
self.ph[nowi][nowj] = 1
# 2. 通過できなかった辺は、確率をベイズの定理により更新
(nowi, nowj) = path[res]
(toi, toj) = path[res+1]
di = toi - nowi
dj = toj - nowj
if di == 1 and self.pv[nowi+1][nowj] != 1:
self.pv[nowi+1][nowj] = self.calp(self.pv[nowi+1][nowj])
if di == -1 and self.pv[nowi][nowj] != 1:
self.pv[nowi][nowj] = self.calp(self.pv[nowi][nowj])
if dj == 1 and self.ph[nowi][nowj+1] != 1:
self.ph[nowi][nowj+1] = self.calp(self.ph[nowi][nowj+1])
if dj == -1 and self.ph[nowi][nowj] != 1:
self.ph[nowi][nowj] = self.calp(self.ph[nowi][nowj])
# print(res, nowi, nowj, check, file=sys.stderr)
# 3. 通過できなかった辺以降は、通路の確率をわずかに下げる（不正解なので少なくとも1箇所は壁）
p0 = 1
for k in range(res+1, len(path)-1):
(nowi, nowj) = path[k]
(toi, toj) = path[k+1]
di = toi - nowi
dj = toj - nowj
prob = self.get_prob(nowi, nowj, di, dj)
p0 *= prob
r = 1 - p0
for k in range(res+1, len(path)-1):
(nowi, nowj) = path[k]
(toi, toj) = path[k+1]
di = toi - nowi
dj = toj - nowj
if di == 1 and self.pv[nowi+1][nowj] != 1:
self.pv[nowi+1][nowj] *= r
if di == -1 and self.pv[nowi][nowj] != 1:
self.pv[nowi][nowj] *= r
if dj == 1 and self.ph[nowi][nowj+1] != 1:
self.ph[nowi][nowj+1] *= r
if dj == -1 and self.ph[nowi][nowj] != 1:
self.ph[nowi][nowj] *= r
return
def update_prob_all(self):
e0 = 0.8 * (self.H-1) * (self.W-1) * 2
c = 1
for _ in range(20):
e = 0
for i in range(1, self.H):
for j in range(1, self.W):
if self.pv[i][j] != 1:
self.pv[i][j] = min(1, self.pv[i][j] * c)
if self.ph[i][j] != 1:
self.ph[i][j] = min(1, self.ph[i][j] * c)
e += self.pv[i][j]
e += self.ph[i][j]
c = e0 / e
return
def solve(self, tk):
H = self.H
W = self.W
for t in range(self.T):
# path = self.DFS()
path = self.dijk() # ゴールに到達する確率を最大化する経路
ans = self.path_to_ans(path)
# print(path, file=sys.stderr)
### 出力
res = self.output(t, ans)
if res == -1: # ゴールに到達
# print("OK turn:", t, file=sys.stderr)
sc = 1000 - t
return sc
else:
# 各辺の通過できる確率の更新
self.update_prob(path, res)
# 全体の確率を更新
self.update_prob_all()
# print(self.pv, self.ph, file=sys.stderr)
return 0
###########################################
def main(DEBUG):
tk = TimeKeeper()
### 入力
T = 1000 # 試行回数
if DEBUG == True:
H, W, p = map(int, input().split())
p = p/100
# H = W = 20
# 6 <= p <= 15 (%) # ロボットが移動に失敗する確率
# 迷路情報（ジャッジ用）
M = int(input()) # 壁の数
WH = [list(map(int, input().split())) for _ in range(H)] # 縦棒:1が壁, 20*21
WV = [list(map(int, input().split())) for _ in range(H+1)] # 横棒:21*20
STEPS = list(map(int, input().split())) # 移動可能な数
# print(M, file=sys.stderr)
# exit()
else:
H, W, p = map(int, input().split())
p = p/100
# H = W = 20
# 6 <= p <= 15 (%) # ロボットが移動に失敗する確率
# 以下、ダミー
WH = []
WV = []
STEPS = []
solver = Solver(DEBUG, T, H, W, p, WH, WV, STEPS)
sc = solver.solve(tk)
print(f'sc: {sc}', file=sys.stderr)
if __name__ == '__main__':
parser = argparse.ArgumentParser(description='Debug mode')
parser.add_argument('--debug', action='store_true', help='Enable debug mode')
args = parser.parse_args()
main(args.debug)