結果

問題 No.5006 Hidden Maze
ユーザー ra5anchor
提出日時 2025-04-19 05:12:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,236 ms / 2,000 ms
コード長 10,241 bytes
コンパイル時間 504 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 106,484 KB
スコア 89,109
平均クエリ数 109.89
最終ジャッジ日時 2025-04-19 05:13:19
合計ジャッジ時間 50,659 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

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.8] * (W+1) for _ in range(H)] # 縦棒
        self.pv = [[0.8] * 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 DFS(self):
        (gi, gj) = (self.H-1, self.W-1)
        que = deque()
        visited = set()
        prev = [[(-1,-1)] * self.W for _ in range(self.H)]
        visited.add((0, 0))
        que.append((0, 0))
        while que:
            nowi, nowj = que.pop()
            if (nowi, nowj) == (gi, gj):
                break
            # ランダムで次の行き先を選択
            L = random.sample(DIJ, 4)
            for di, dj in L:
                toi, toj = nowi+di, nowj+dj
                if toi < 0 or toi >= self.H or toj < 0 or toj >= self.W:
                    continue
                if (toi, toj) in visited:
                    continue
                visited.add((toi, toj))
                prev[toi][toj] = (nowi, nowj)
                que.append((toi, toj))
        path = self.get_path(prev, (gi,gj))
        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 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)
        # 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())) # 移動可能な数
    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)
0