#770583 (PyPy3) No.5006 Hidden Maze

提出ソース

結果

問題	No.5006 Hidden Maze
ユーザー	netyo715
提出日時	2022-06-12 16:14:15
言語	PyPy3 (7.3.15)
結果	AC
実行時間	1,905 ms / 2,000 ms
コード長	2,976 bytes
コンパイル時間	366 ms
実行使用メモリ	115,468 KB
スコア	55,546
平均クエリ数	425.26
最終ジャッジ日時	2022-06-12 16:19:19
合計ジャッジ時間	105,999 ms
ジャッジサーバーID （参考情報）	judge14 / judge13
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,115 ms 108,976 KB
testcase_01	AC	1,905 ms 115,460 KB
testcase_02	AC	403 ms 105,328 KB
testcase_03	AC	867 ms 107,776 KB
testcase_04	AC	841 ms 108,048 KB
testcase_05	AC	1,366 ms 111,612 KB
testcase_06	AC	1,008 ms 107,568 KB
testcase_07	AC	1,560 ms 111,408 KB
testcase_08	AC	1,766 ms 112,312 KB
testcase_09	AC	549 ms 105,796 KB
testcase_10	AC	1,008 ms 109,096 KB
testcase_11	AC	469 ms 106,100 KB
testcase_12	AC	835 ms 108,800 KB
testcase_13	AC	522 ms 105,340 KB
testcase_14	AC	1,902 ms 112,260 KB
testcase_15	AC	351 ms 103,356 KB
testcase_16	AC	453 ms 105,224 KB
testcase_17	AC	262 ms 102,504 KB
testcase_18	AC	1,817 ms 111,948 KB
testcase_19	AC	506 ms 107,208 KB
testcase_20	AC	638 ms 107,032 KB
testcase_21	AC	1,835 ms 112,868 KB
testcase_22	AC	854 ms 108,896 KB
testcase_23	AC	512 ms 105,064 KB
testcase_24	AC	1,510 ms 113,100 KB
testcase_25	AC	407 ms 104,156 KB
testcase_26	AC	1,791 ms 110,936 KB
testcase_27	AC	513 ms 105,096 KB
testcase_28	AC	274 ms 102,548 KB
testcase_29	AC	704 ms 105,432 KB
testcase_30	AC	510 ms 106,472 KB
testcase_31	AC	543 ms 106,588 KB
testcase_32	AC	1,274 ms 108,328 KB
testcase_33	AC	599 ms 106,384 KB
testcase_34	AC	464 ms 104,732 KB
testcase_35	AC	1,000 ms 111,724 KB
testcase_36	AC	398 ms 103,492 KB
testcase_37	AC	947 ms 108,504 KB
testcase_38	AC	710 ms 105,980 KB
testcase_39	AC	320 ms 103,796 KB
testcase_40	AC	1,787 ms 110,516 KB
testcase_41	AC	679 ms 106,204 KB
testcase_42	AC	737 ms 106,596 KB
testcase_43	AC	1,852 ms 112,328 KB
testcase_44	AC	354 ms 103,400 KB
testcase_45	AC	1,301 ms 110,776 KB
testcase_46	AC	1,795 ms 113,576 KB
testcase_47	AC	430 ms 104,556 KB
testcase_48	AC	518 ms 104,772 KB
testcase_49	AC	1,819 ms 112,632 KB
testcase_50	AC	304 ms 103,016 KB
testcase_51	AC	1,074 ms 108,448 KB
testcase_52	AC	959 ms 108,744 KB
testcase_53	AC	1,480 ms 111,348 KB
testcase_54	AC	185 ms 101,372 KB
testcase_55	AC	761 ms 109,664 KB
testcase_56	AC	366 ms 104,684 KB
testcase_57	AC	812 ms 106,520 KB
testcase_58	AC	527 ms 104,420 KB
testcase_59	AC	465 ms 105,080 KB
testcase_60	AC	689 ms 105,212 KB
testcase_61	AC	131 ms 97,148 KB
testcase_62	AC	401 ms 105,196 KB
testcase_63	AC	998 ms 108,936 KB
testcase_64	AC	933 ms 111,128 KB
testcase_65	AC	328 ms 103,644 KB
testcase_66	AC	374 ms 104,112 KB
testcase_67	AC	583 ms 105,424 KB
testcase_68	AC	1,835 ms 115,468 KB
testcase_69	AC	465 ms 106,000 KB
testcase_70	AC	443 ms 104,752 KB
testcase_71	AC	326 ms 103,892 KB
testcase_72	AC	396 ms 106,028 KB
testcase_73	AC	1,786 ms 112,368 KB
testcase_74	AC	631 ms 107,336 KB
testcase_75	AC	1,893 ms 112,240 KB
testcase_76	AC	789 ms 108,984 KB
testcase_77	AC	893 ms 109,860 KB
testcase_78	AC	1,035 ms 108,600 KB
testcase_79	AC	1,878 ms 112,688 KB
testcase_80	AC	635 ms 107,508 KB
testcase_81	AC	374 ms 104,488 KB
testcase_82	AC	669 ms 105,848 KB
testcase_83	AC	295 ms 103,224 KB
testcase_84	AC	841 ms 109,144 KB
testcase_85	AC	1,832 ms 112,640 KB
testcase_86	AC	278 ms 102,000 KB
testcase_87	AC	964 ms 108,352 KB
testcase_88	AC	432 ms 104,964 KB
testcase_89	AC	772 ms 107,240 KB
testcase_90	AC	706 ms 108,204 KB
testcase_91	AC	964 ms 109,008 KB
testcase_92	AC	1,827 ms 111,368 KB
testcase_93	AC	347 ms 103,264 KB
testcase_94	AC	1,850 ms 112,852 KB
testcase_95	AC	1,408 ms 110,276 KB
testcase_96	AC	271 ms 102,756 KB
testcase_97	AC	1,744 ms 113,724 KB
testcase_98	AC	1,662 ms 112,528 KB
testcase_99	AC	272 ms 102,156 KB

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

ソースコード

raw source code

from heapq import heapify, heappop as pop, heappush as push
from random import sample
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"
    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)

yukicoder

結果

テストケース

ソースコード