結果

問題 No.5006 Hidden Maze
ユーザー netyo715netyo715
提出日時 2022-06-12 18:04:21
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,075 bytes
コンパイル時間 518 ms
実行使用メモリ 113,352 KB
スコア 40,719
平均クエリ数 123.33
最終ジャッジ日時 2022-06-12 18:06:55
合計ジャッジ時間 152,501 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 AC 713 ms
107,280 KB
testcase_03 AC 1,128 ms
106,736 KB
testcase_04 AC 1,342 ms
110,580 KB
testcase_05 TLE -
testcase_06 AC 325 ms
103,980 KB
testcase_07 TLE -
testcase_08 TLE -
testcase_09 AC 361 ms
103,392 KB
testcase_10 TLE -
testcase_11 AC 332 ms
103,432 KB
testcase_12 AC 1,993 ms
112,732 KB
testcase_13 AC 622 ms
105,212 KB
testcase_14 TLE -
testcase_15 AC 622 ms
106,908 KB
testcase_16 AC 345 ms
103,668 KB
testcase_17 AC 333 ms
103,340 KB
testcase_18 TLE -
testcase_19 AC 470 ms
103,952 KB
testcase_20 AC 890 ms
110,192 KB
testcase_21 TLE -
testcase_22 AC 823 ms
107,308 KB
testcase_23 TLE -
testcase_24 TLE -
testcase_25 AC 549 ms
104,648 KB
testcase_26 TLE -
testcase_27 AC 375 ms
104,208 KB
testcase_28 AC 352 ms
103,524 KB
testcase_29 AC 1,933 ms
113,352 KB
testcase_30 AC 726 ms
106,768 KB
testcase_31 AC 857 ms
111,776 KB
testcase_32 TLE -
testcase_33 AC 1,060 ms
113,240 KB
testcase_34 TLE -
testcase_35 AC 667 ms
107,144 KB
testcase_36 AC 564 ms
104,396 KB
testcase_37 TLE -
testcase_38 AC 1,962 ms
112,052 KB
testcase_39 AC 393 ms
103,568 KB
testcase_40 TLE -
testcase_41 AC 1,110 ms
110,964 KB
testcase_42 TLE -
testcase_43 TLE -
testcase_44 AC 271 ms
102,460 KB
testcase_45 TLE -
testcase_46 TLE -
testcase_47 AC 537 ms
103,752 KB
testcase_48 AC 824 ms
107,536 KB
testcase_49 TLE -
testcase_50 TLE -
testcase_51 TLE -
testcase_52 TLE -
testcase_53 TLE -
testcase_54 AC 527 ms
105,000 KB
testcase_55 AC 697 ms
108,456 KB
testcase_56 AC 650 ms
106,476 KB
testcase_57 TLE -
testcase_58 AC 1,301 ms
110,452 KB
testcase_59 AC 324 ms
102,840 KB
testcase_60 AC 764 ms
108,512 KB
testcase_61 AC 142 ms
96,716 KB
testcase_62 AC 593 ms
104,348 KB
testcase_63 AC 500 ms
104,944 KB
testcase_64 TLE -
testcase_65 AC 795 ms
109,224 KB
testcase_66 AC 317 ms
102,868 KB
testcase_67 AC 875 ms
107,924 KB
testcase_68 TLE -
testcase_69 AC 567 ms
105,280 KB
testcase_70 AC 356 ms
103,120 KB
testcase_71 AC 782 ms
108,772 KB
testcase_72 AC 605 ms
104,172 KB
testcase_73 TLE -
testcase_74 AC 576 ms
108,652 KB
testcase_75 TLE -
testcase_76 AC 507 ms
105,600 KB
testcase_77 AC 869 ms
107,656 KB
testcase_78 TLE -
testcase_79 TLE -
testcase_80 AC 622 ms
107,676 KB
testcase_81 AC 1,115 ms
109,148 KB
testcase_82 TLE -
testcase_83 AC 285 ms
103,440 KB
testcase_84 AC 644 ms
107,508 KB
testcase_85 TLE -
testcase_86 AC 254 ms
102,852 KB
testcase_87 AC 1,319 ms
107,280 KB
testcase_88 TLE -
testcase_89 TLE -
testcase_90 TLE -
testcase_91 AC 574 ms
106,216 KB
testcase_92 TLE -
testcase_93 AC 273 ms
103,972 KB
testcase_94 TLE -
testcase_95 TLE -
testcase_96 AC 277 ms
102,520 KB
testcase_97 TLE -
testcase_98 TLE -
testcase_99 AC 249 ms
102,428 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heapify, heappop as pop, heappush as push
from random import sample, randint
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
        if stop_cnt[idx1][idx2]==1 and randint(1, 100)<=3:
            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"
    def cmd_idx(idx1, idx2):
        r1, c1 = idx2rc(idx1)
        r2, c2 = idx2rc(idx2)
        return cmd_rc(r1, c1, r2, c2)

    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 sample(D, 4):
                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
        node_idxs = []
        h, w = H-1, W-1
        while h+w:
            node_idxs.append(rc2idx(h, w))
            h, w = prev[h][w]
        node_idxs.append(0)
        node_idxs.reverse()
        cmd = []
        for i in range(len(node_idxs)-1):
            cmd.append(cmd_idx(node_idxs[i], node_idxs[i+1]))
        
        print(*cmd, sep="")
        through_cnt = int(input())
        if through_cnt == -1:
            return
        for i in range(through_cnt):
            is_empty[node_idxs[i]][node_idxs[i+1]] = True
            is_empty[node_idxs[i+1]][node_idxs[i]] = True
        stop_cnt[node_idxs[through_cnt]][node_idxs[through_cnt+1]] += 1
        stop_cnt[node_idxs[through_cnt+1]][node_idxs[through_cnt]] += 1

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