AtCoder ABC472振り返り (PythonでABCD問題)

ABC472を振り返ります

今回はABCDまで4問解答でした。
久々に４問解けて嬉しかったのですが、思ったよりも順位は良くなく...。
今回はC,Dの難易度が低かったようです。

D問題は「多始点 BFS」という頻出分野の問題のようですけども、今回は解答にちょっと時間がかかってしまいました。
次回出題時は覚えておきたいところです。

A - A

問題文のとおりに文字を置換します。

S = list(input())

# Aでなければ.に置換
for i in range(len(S)):
    if S[i] != "A":
        S[i] = "."

print("".join(S))

B - Break a Stick

• はじめに、配列全体の合計を求めておく
• 区切り箇所を全探索で動かす。区切りから左側の合計値と、右側の合計の差の最小値を求める

INF = 10 ** 18

N = int(input())
L = list(map(int, input().split()))

# Lの合計値を求める
all = sum(L)

left = 0
answer = INF # 答えを巨大な数にしておく

for i in range(N-1):
    # 区切りの左と右の値を比較
    left += L[i] 
    right = all - left
    answer = min(answer, abs(left-right))

print(answer)

C - On a Diet

Queueを使って、食べたものを管理します。

from collections import deque

sys.setrecursionlimit(10 ** 8)
INF = 10 ** 18

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
A.insert(0, 0)

queue = deque()
cal = 0
for i in range(1, len(A)):
    # 削除
    while len(queue) > 0:
        deleted = False
        (day, c) = queue[0]
        if day < i - M + 1:
            queue.popleft()
            cal -= c

        if deleted == False:
            break

    # たべる
    food = A[i]
    eat = False
    if cal + food <= K:
        queue.append((i, food))
        cal += food
        eat = True

    if eat:
        print("Yes")
    else:
        print("No")

D - Bomber Mad

• "安全な空マス" を探す
• "安全な空マス"から、移動可能な回数分だけ、移動可能マスに移動する(幅優先探索)
• 移動したマスの数をカウント

というふうに求めました。

import heapq

INF = 10 ** 18

H, W, K = map(int, input().split())
S = []
S.append("*" * (W + 2))
for i in range(H):
    S.append("*" + input() + "*")
S.append("*" * (W + 2))

# "#"がある行と列を求めておく
exist_rows = set()
exist_cols = set()

for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j] == "#":
            exist_rows.add(i)
            exist_cols.add(j)

# 安全な空マスかどうか判定
def isSafe(x, y):
    return x not in exist_cols and y not in exist_rows

# 安全な空マスを探す
safe_spots = []
for y in range(1, H+1):
    for x in range(1, W+1):
        if isSafe(x, y):
            safe_spots.append( (x, y))

# 重み付きqueue
que = []
heapq.heapify(que)

# 初期条件
visited = [[INF] * (W + 2) for _ in range(H + 2)]

for spot in safe_spots:
    (sx, sy) = spot
    heapq.heappush(que, (0, sx, sy))
    visited[sy][sx] = 0

while que:
    # キューから要素を取り出す
    (cost, cx, cy) = heapq.heappop(que)

    # 移動限界なら探索終了
    if cost + 1 > K:
        continue 

    moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for move in moves:
        (dx, dy) = move
        nx, ny = cx + dx, cy + dy

        # 移動先が空きマスでない
        if S[ny][nx] != ".":
            continue

        next_cost = cost + 1

        if isSafe(nx, ny):
            next_cost = 0

        # 移動先が探索済
        if visited[ny][nx] <= next_cost:
            continue

        visited[ny][nx] = next_cost
        heapq.heappush(que, (next_cost, nx, ny))

# 移動したマスの数をカウントする
count = 0
for y in range(1, H+1):
    for x in range(1, W+1):
        if visited[y][x] != INF:
            count += 1

print(count)