#770545 (PyPy3) No.5006 Hidden Maze

提出ソース

結果

問題	No.5006 Hidden Maze
ユーザー	netyo715
提出日時	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

権限があれば一括ダウンロードができます

ソースコード

raw source code

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)

yukicoder

結果

テストケース

ソースコード