【電脳少女プログラミング2088-壊レタ君を再構築-】SとAを解いてみた

はじめに

なぜか、ゴルフイベント、pythonで3位スコア出したのに、ランキングに入らない、緑コーダーです

まあ感想でも書きますか(書かないと趣旨がおかしい)

A問題の感想

見える範囲のいれずかに、行く時の移動回数の最小値と、言い換えられるので、そちらの方針で実装する
まあ普通にBFSすればいいので、実装したら、ACしました(語彙力ない)

ACコード

from collections import deque

MOVES = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
S = [list(input()) for _ in [0] * H]
ax, ay = -1, -1
bx, by = -1, -1

for i in range(H):
    for k in range(W):
        if S[i][k] == "A":
            ax, ay = i, k
            S[i][k] = "."

        if S[i][k] == "B":
            bx, by = i, k
            S[i][k] = "."

B = [(bx, by)]

for mx, my in MOVES:
    x, y = bx, by

    while 0 <= x + mx < H and 0 <= y + my < W:
        x += mx
        y += my

        if S[x][y] == "#":
            break

        B.append((x, y))

Q = deque()
used = [[1 << 60] * W for _ in [0] * H]
used[ax][ay] = 0
Q.append((ax, ay))

while Q:
    x, y = Q.popleft()

    for mx, my in MOVES:
        nx, ny = x + mx, y + my

        if not (0 <= nx < H and 0 <= ny < W):
            continue

        if used[x][y] + 1 >= used[nx][ny]:
            continue

        if S[nx][ny] == "#":
            continue

        used[nx][ny] = used[x][y] + 1
        Q.append((nx, ny))

ans = 1 << 60

for x, y in B:
    ans = min(ans, used[x][y])

print(-1 if ans == 1 << 60 else ans)

S問題の感想

これは、単調性があるかつ、最大化問題なので、二分探索が適当
でも、他の縄張りの場所をシュミレートすると、二分探索しても$O(HW^2 * log N)$ぐらいになって、間に合わない
だけど、言い換えると、他の縄張りと接触しない条件は、マンハッタン距離が、縄張りの範囲+自分の範囲以下なら、接触すると言い換えられる、これを使えば、毎回、座標を探索しなくてよくなるので、$O(H \cdot W \cdot M \cdot log HW)$ぐらいになって、十分間に合うって感じでした。

ACコード

H, W, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in [0] * M]

ans = -1

for i in range(H):
    for k in range(W):
        ng, ok = -1, (H * W) + 1

        while ok - ng > 1:
            mid = (ok + ng) // 2

            for r, c, s in L:
                r -= 1
                c -= 1

                if abs(r - i) + abs(c - k) <= s + mid:
                    break
            else:
                ng = mid
                continue

            ok = mid

        ans = max(ans, ng)

print(ans)

最後に

S問題はなかなか、面白かったです
プログラミング問題は埋められそうですけど、sqlは、D問題でも無理でした

:qa!