結果

問題 No.5006 Hidden Maze
ユーザー netyo715netyo715
提出日時 2022-06-12 15:53:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,705 ms / 2,000 ms
コード長 2,813 bytes
コンパイル時間 447 ms
実行使用メモリ 107,984 KB
スコア 66,939
平均クエリ数 331.46
最終ジャッジ日時 2022-06-12 15:58:05
合計ジャッジ時間 67,111 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 306 ms
101,680 KB
testcase_01 AC 328 ms
101,744 KB
testcase_02 AC 319 ms
102,136 KB
testcase_03 AC 440 ms
102,660 KB
testcase_04 AC 448 ms
103,484 KB
testcase_05 AC 687 ms
104,404 KB
testcase_06 AC 972 ms
106,008 KB
testcase_07 AC 1,167 ms
105,540 KB
testcase_08 AC 1,300 ms
106,212 KB
testcase_09 AC 1,259 ms
105,320 KB
testcase_10 AC 285 ms
101,588 KB
testcase_11 AC 243 ms
101,812 KB
testcase_12 AC 449 ms
103,028 KB
testcase_13 AC 415 ms
102,324 KB
testcase_14 AC 1,482 ms
106,056 KB
testcase_15 AC 539 ms
102,376 KB
testcase_16 AC 699 ms
105,564 KB
testcase_17 AC 291 ms
101,484 KB
testcase_18 AC 747 ms
102,440 KB
testcase_19 AC 768 ms
105,740 KB
testcase_20 AC 324 ms
101,452 KB
testcase_21 AC 370 ms
102,152 KB
testcase_22 AC 196 ms
100,816 KB
testcase_23 AC 287 ms
101,364 KB
testcase_24 AC 421 ms
101,680 KB
testcase_25 AC 832 ms
104,508 KB
testcase_26 AC 1,705 ms
107,984 KB
testcase_27 AC 431 ms
102,644 KB
testcase_28 AC 1,316 ms
107,384 KB
testcase_29 AC 242 ms
101,428 KB
testcase_30 AC 314 ms
102,124 KB
testcase_31 AC 412 ms
104,148 KB
testcase_32 AC 602 ms
104,240 KB
testcase_33 AC 475 ms
102,524 KB
testcase_34 AC 255 ms
101,068 KB
testcase_35 AC 442 ms
102,580 KB
testcase_36 AC 412 ms
102,728 KB
testcase_37 AC 1,190 ms
104,844 KB
testcase_38 AC 1,231 ms
105,924 KB
testcase_39 AC 379 ms
103,632 KB
testcase_40 AC 266 ms
101,524 KB
testcase_41 AC 281 ms
101,184 KB
testcase_42 AC 341 ms
102,424 KB
testcase_43 AC 577 ms
104,400 KB
testcase_44 AC 302 ms
101,940 KB
testcase_45 AC 399 ms
102,012 KB
testcase_46 AC 493 ms
103,596 KB
testcase_47 AC 383 ms
102,864 KB
testcase_48 AC 1,276 ms
105,604 KB
testcase_49 AC 1,608 ms
107,884 KB
testcase_50 AC 352 ms
102,532 KB
testcase_51 AC 423 ms
102,536 KB
testcase_52 AC 277 ms
102,072 KB
testcase_53 AC 758 ms
103,972 KB
testcase_54 AC 748 ms
103,064 KB
testcase_55 AC 297 ms
102,032 KB
testcase_56 AC 352 ms
101,596 KB
testcase_57 AC 1,131 ms
104,304 KB
testcase_58 AC 1,191 ms
106,336 KB
testcase_59 AC 396 ms
102,156 KB
testcase_60 AC 215 ms
100,676 KB
testcase_61 AC 360 ms
102,588 KB
testcase_62 AC 456 ms
103,180 KB
testcase_63 AC 365 ms
102,600 KB
testcase_64 AC 525 ms
102,936 KB
testcase_65 AC 400 ms
101,736 KB
testcase_66 AC 372 ms
102,952 KB
testcase_67 AC 418 ms
103,436 KB
testcase_68 AC 472 ms
102,676 KB
testcase_69 AC 1,017 ms
104,344 KB
testcase_70 AC 315 ms
101,404 KB
testcase_71 AC 364 ms
102,412 KB
testcase_72 AC 560 ms
104,184 KB
testcase_73 AC 689 ms
105,980 KB
testcase_74 AC 664 ms
104,972 KB
testcase_75 AC 850 ms
104,708 KB
testcase_76 AC 950 ms
103,896 KB
testcase_77 AC 1,359 ms
107,572 KB
testcase_78 AC 799 ms
105,164 KB
testcase_79 AC 1,328 ms
107,748 KB
testcase_80 AC 259 ms
101,468 KB
testcase_81 AC 279 ms
101,500 KB
testcase_82 AC 311 ms
101,760 KB
testcase_83 AC 207 ms
100,992 KB
testcase_84 AC 288 ms
101,612 KB
testcase_85 AC 452 ms
103,048 KB
testcase_86 AC 375 ms
102,064 KB
testcase_87 AC 475 ms
101,828 KB
testcase_88 AC 642 ms
105,708 KB
testcase_89 AC 1,384 ms
107,172 KB
testcase_90 AC 322 ms
102,168 KB
testcase_91 AC 264 ms
100,788 KB
testcase_92 AC 751 ms
104,088 KB
testcase_93 AC 364 ms
102,336 KB
testcase_94 AC 877 ms
104,396 KB
testcase_95 AC 1,133 ms
105,772 KB
testcase_96 AC 194 ms
99,896 KB
testcase_97 AC 1,258 ms
105,028 KB
testcase_98 AC 1,170 ms
105,092 KB
testcase_99 AC 846 ms
104,324 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heapify, heappop as pop, heappush as push
D = ((-1, 0), (0, -1), (0, 1), (1, 0))
def solve(H, W, P):
    stop_cnt = [[0]*(H*W) for _ in range(H*W)]
    is_empty = [[False]*(H*W) for _ in range(H*W)]
    def rc2idx(row, col):
        return row*W+col
    def idx2rc(idx):
        return idx//W, idx%W
    def is_empty_idx(idx1, idx2):
        return is_empty[idx1][idx2]
    def is_empty_rc(row1, col1, row2, col2):
        return is_empty_idx(rc2idx(row1, col1), rc2idx(row2, col2))
    def empty_per_idx(idx1, idx2):
        return 0
    def empty_per_rc(row1, col1, row2, col2):
        return empty_per_idx(rc2idx(row1, col1), rc2idx(row2, col2))
    def through_per_idx(idx1, idx2):
        if is_empty_idx(idx1, idx2):
            return (100-P)/100
        return (pow(P, stop_cnt[idx1][idx2])/pow(100, stop_cnt[idx1][idx2]-1)-P)/100

    def through_per_rc(row1, col1, row2, col2):
        return through_per_idx(rc2idx(row1, col1), rc2idx(row2, col2))
    def cmd_rc(row1, col1, row2, col2):
        if row1 > row2:
            return "U"
        if row1 < row2:
            return "D"
        if col1 > col2:
            return "L"
        if col1 < col2:
            return "R"

    for try_cnt in range(1, 1000+1):
        q = [(-1, 0, 0)]
        fixed = [[False]*W for _ in range(H)]
        dist = [[10]*W for _ in range(H)]
        prev = [[None]*W for _ in range(H)]
        while q:
            qper, qh, qw = pop(q)
            if fixed[qh][qw]:
                continue
            fixed[qh][qw] = True
            for a, b in D:
                h = qh+a; w = qw+b
                if not 0 <= h < H:
                    continue
                if not 0 <= w < W:
                    continue
                if fixed[h][w]:
                    continue
                per = -(-qper*through_per_rc(qh, qw, h, w))
                if dist[h][w] < per:
                    continue
                q.append((per, h, w))
                prev[h][w] = (qh, qw)
                dist[h][w] = per
        nodes = []
        h, w = H-1, W-1
        while h+w:
            nodes.append((h, w))
            h, w = prev[h][w]
        nodes.append((0, 0))
        nodes.reverse()
        cmd = []
        for i in range(len(nodes)-1):
            cmd.append(cmd_rc(nodes[i][0], nodes[i][1], nodes[i+1][0], nodes[i+1][1]))
        
        print(*cmd, sep="")
        through_cnt = int(input())
        if through_cnt == -1:
            return
        for i in range(through_cnt):
            idx1, idx2 = rc2idx(*nodes[i]), rc2idx(*nodes[i+1])
            is_empty[idx1][idx2] = True
            is_empty[idx2][idx1] = True
        idx1, idx2 = rc2idx(*nodes[through_cnt]), rc2idx(*nodes[through_cnt+1])
        stop_cnt[idx1][idx2] += 1

H, W, P = map(int, input().split())
solve(H, W, P)
0