結果
問題 |
No.5006 Hidden Maze
|
ユーザー |
|
提出日時 | 2025-04-24 23:03:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 931 ms / 2,000 ms |
コード長 | 6,055 bytes |
コンパイル時間 | 401 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 105,680 KB |
スコア | 89,904 |
平均クエリ数 | 101.95 |
最終ジャッジ日時 | 2025-04-24 23:04:15 |
合計ジャッジ時間 | 50,441 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
import sys import random import math import argparse from heapq import heappush, heappop # directions mapping DIRS = {'R': (0, 1), 'D': (1, 0), 'L': (0, -1), 'U': (-1, 0)} V2C = {v: k for k, v in DIRS.items()} 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, self.WV, self.STEPS = WH, WV, STEPS # 通過できる確率 # 確率0.8で通過できる self.ph = [[0.80] * (W+1) for _ in range(H)] # 縦棒 self.pv = [[0.80] * W for _ in range(H+1)] # 横棒 # 周囲の壁 for row in self.ph: row[0] = row[-1] = 0 self.pv[0] = [0]*W self.pv[-1] = [0]*W def output(self, t, ans): if self.DEBUG: print(ans) i = j = cnt = 0 cnt_wall = -1 for c in ans: di, dj = DIRS[c] # 判定:壁に当たったら記録してループ脱出 if (di == -1 and self.WV[i][j] == 1) or \ (di == 1 and self.WV[i+1][j] == 1) or \ (dj == -1 and self.WH[i][j] == 1) or \ (dj == 1 and self.WH[i][j+1] == 1): cnt_wall = cnt break i += di; j += dj; cnt += 1 return -1 if cnt_wall == -1 else min(self.STEPS[t], cnt_wall) else: print(ans, flush=True) print(ans, file=sys.stderr) return int(input()) def path_to_ans(self, path): return ''.join( V2C[(ni - i, nj - j)] for (i, j), (ni, nj) in zip(path, path[1:]) ) def get_path(self, prev, cur): path = [] while cur != (-1, -1): path.append(cur) cur = prev[cur[0]][cur[1]] return path[::-1] def get_prob(self, i, j, di, dj): # 通過できる確率p if di: return self.pv[i + (di > 0)][j] return self.ph[i][j + (dj > 0)] def get_cost(self, i, j, di, dj): # 通過できる確率pに対して # 対数変換して(-1)を乗じたものをコストとすることで # コストの和の最小化=経路の通過できる確率の積の最大化が求められる p = self.get_prob(i, j, di, dj) return 10**18 if p == 0 else -math.log(p) def dijk(self, noise_scale): # 到達できる確率を最大化する経路を選択 gi, gj = self.H - 1, self.W - 1 INF = 10**18 dist = [[INF]*self.W for _ in range(self.H)] prev = [[(-1, -1)]*self.W for _ in range(self.H)] seen = set() dist[0][0] = 0 heap = [(0, (0, 0))] while heap: d, (i, j) = heappop(heap) if (i, j) in seen: continue seen.add((i, j)) for di, dj in DIRS.values(): ni, nj = i + di, j + dj if not (0 <= ni < self.H and 0 <= nj < self.W): continue cost = self.get_cost(i, j, di, dj) if cost >= INF: continue cost += noise_scale * random.random() nd = d + cost if nd < dist[ni][nj]: dist[ni][nj] = nd prev[ni][nj] = (i, j) heappush(heap, (nd, (ni, nj))) return self.get_path(prev, (gi, gj)) 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 (i, j), (ni, nj) in zip(path, path[1:res+1]): di, dj = ni - i, nj - j arr, (ai, aj) = (self.pv, (i + (di>0), j)) if di else (self.ph, (i, j + (dj>0))) arr[ai][aj] = 1 # 2. 通過できなかった辺は、確率を更新 i, j = path[res]; ni, nj = path[res+1] di, dj = ni - i, nj - j arr, (ai, aj) = (self.pv, (i + (di>0), j)) if di else (self.ph, (i, j + (dj>0))) if arr[ai][aj] != 1: arr[ai][aj] = self.calp(arr[ai][aj]) # 3. 通過できなかった辺以降は、通路の確率をわずかに下げる(不正解なので少なくとも1箇所は壁) p0 = 1 for (i, j), (ni, nj) in zip(path[res+1:], path[res+2:]): p0 *= self.get_prob(i, j, ni - i, nj - j) r = 1 - p0 for (i, j), (ni, nj) in zip(path[res+1:], path[res+2:]): di, dj = ni - i, nj - j arr, (ai, aj) = (self.pv, (i + (di>0), j)) if di else (self.ph, (i, j + (dj>0))) if arr[ai][aj] != 1: arr[ai][aj] *= r def solve(self): for t in range(self.T): noise_scale = min(0.2, 0.05 + t/100) path = self.dijk(noise_scale) ans = self.path_to_ans(path) ### 出力 res = self.output(t, ans) if res == -1: return 1000 - t self.update_prob(path, res) return 0 def main(DEBUG): ### 入力 T = 1000 # 試行回数 H, W, p = map(int, input().split()) p /= 100 # 移動に失敗する確率 (6–15%) if DEBUG: M = int(input()) # 壁の数 WH = [list(map(int, input().split())) for _ in range(H)] # 縦棒:1が壁, H×(W+1) WV = [list(map(int, input().split())) for _ in range(H+1)] # 横棒:(H+1)×W STEPS = list(map(int, input().split())) # 移動可能な数 else: WH = WV = STEPS = [] solver = Solver(DEBUG, T, H, W, p, WH, WV, STEPS) sc = solver.solve() 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)