ABC384Eを解いた【優先度付きキュー】

筆者はレート800前後の茶～緑コーダ

ABC384当日にACできなかったE問題を解いていく

実装コード

優先度付きキューを使い、
隣り合うスライムの強さと場所を格納していく

最小値のスライムが吸収できるならそいつを取り込み、
隣り合う場所が増えるので、新たな近傍をキューにまた追加

吸収できなかったら終了

main.py

import sys
import heapq
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)


class Minheapq(object):
    q = []
    def push(self, v):
        heapq.heappush(self.q, v)

    def pop(self):
        return heapq.heappop(self.q)

    def get(self):
        return self.q[0]

    def values(self):
        for _q in self.q:
            yield _q

dy = [-1, 0, 1, 0]
dx = [ 0, 1, 0, -1]

def out_of_bounds(y, x, h, w):
    return y < 0 or y >= h or x < 0 or x >= w


def main():
    H, W, X = rLI()
    P, Q = rLI1()
    A = [rLI() for _ in range(H)]
    q = Minheapq()
    q.push((float('inf'),(-1,-1)))
    q.push((0,(P,Q)))
    visited = set()
    visited.add((P,Q))
    p = A[P][Q]
    e = p/X
    while q.q:
        cp,cur = q.pop()
        y,x = cur
        if cp >= e:
            break
        p += cp
        e = p/X
        # err(cur,p,e)
        for i0,j0 in zip(dy,dx):
            i=y+i0
            j=x+j0
            if out_of_bounds(i,j,H,W):continue
            if (i,j) in visited:continue
            cp = A[i][j]
            visited.add((i,j))
            q.push((cp,(i,j)))
    print(p)
    
    
if __name__ == '__main__':
    main()

まとめ

ABC384当日は優先度付きキューと普通のキューを２つ組み合わせてしまい
処理が冗長的だったので優先度付きキューのみで実装してみた

グリッドの近傍をスニペットに登録してから
だいぶ苦手意識が減ってきたが、考えをもうちょっとシンプルにしたい