結果

問題 No.5024 魔法少女うなと宝集め
コンテスト
ユーザー LNG
提出日時 2026-05-02 17:32:57
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 2,469 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 182 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 328,200 KB
スコア 476,869
最終ジャッジ日時 2026-05-02 17:34:43
合計ジャッジ時間 105,263 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import time

start = time.perf_counter()

raw = sys.stdin.read().split()
if not raw:
    sys.exit()

n = int(raw[0])
t = int(raw[1])

g = []
idx = 2
for i in range(n):
    row = []
    for j in range(n):
        v = int(raw[idx])
        row.append(v)
        idx = idx+1
    g.append(row)

init = []
for r in range(n):
    for c in range(n):
        s = g[r][c]
        fid = r*n+c
        bit = 1<<fid
        p = []
        p.append((r,c))
        st = (s,r,c,bit,p)
        init.append(st)

res_p = []
mx = -1

dr = [-1,1,0,0]
dc = [0,0,-1,1]

lim = 1.95
bw = 5

while True:
    now = time.perf_counter()
    if now-start > lim:
        break
    
    init.sort(key=lambda x:x[0],reverse=True)
    
    bm = []
    full = False
    if len(init) > bw:
        for i in range(bw):
            bm.append(init[i])
        full = True
    else:
        bm = init

    over = False
    for _ in range(t-1):
        nxt = []
        for cur in bm:
            cs = cur[0]
            cr = cur[1]
            cc = cur[2]
            cv = cur[3]
            cp = cur[4]
            
            if cs > mx:
                mx = cs
                res_p = cp

            for i in range(4):
                nr = cr+dr[i]
                nc = cc+dc[i]
                
                if nr >= 0 and nr < n:
                    if nc >= 0 and nc < n:
                        tid = nr*n+nc
                        tb = 1<<tid
                        
                        if (cv&tb) == 0:
                            ns = cs+g[nr][nc]
                            np = []
                            for pos in cp:
                                np.append(pos)
                            np.append((nr,nc))
                            nv = cv|tb
                            nxt.append((ns,nr,nc,nv,np))

        if len(nxt) == 0:
            break
            
        nxt.sort(key=lambda x:x[0],reverse=True)
        
        if len(nxt) > bw:
            bm = []
            for i in range(bw):
                bm.append(nxt[i])
            full = True
        else:
            bm = nxt

        if time.perf_counter()-start > lim:
            over = True
            break

    for fst in bm:
        if fst[0] > mx:
            mx = fst[0]
            res_p = fst[4]

    if over == True:
        break
    if full == False:
        break
        
    bw = int(bw*1.5)

print(len(res_p))
for pos in res_p:
    y = pos[0]
    x = pos[1]
    print(f"{y} {x}")
0