結果

問題 No.5006 Hidden Maze
コンテスト
ユーザー ra5anchor
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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)
0