AtCoder Beginner Contest 176の感想

AtCoder

2020.08.232020.09.08

ABC176に参加した。

AtCoder Beginner Contest 176 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – Takoyaki

やるだけ。

n, x, t = map(int, input().split())

if n % x == 0:
    ans = n // x
else:
    ans = n // x + 1

ans *= t
print(ans)

B – Multiple of 9

Pythonのint型は精度の上限が無いので、各桁の和を見なくてもそのまま割り算すればOK。

n = int(input())
print('Yes' if n % 9 == 0 else 'No')

C – Step

高さの最小値を更新しながら線形探索。

踏み台の高さ（差分）を加算していく。

n = int(input())
a = list(map(int, input().split()))

ans = 0
h = a[0]
for i in a[1:]:
    if i <= h:
        ans += h - i
    else:
        h = i

print(ans)

D – Wizard in Maze

幅優先探索を２つ組み合わせるところまでは思いついたが本番中に実装間に合わず。

下記コードはPythonで間に合わずPyPyでAC。

各マスごとにワープする回数（コスト）を最小化していく。

歩いていける場所は歩いて、ワープしなければ行けないところはワープする。

ワープの時は歩きよりもコストが１高いことに注意する。

後は境界条件や配列外参照に気をつけながら幅優先探索。

from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
maze = [list(input()) for _ in range(h)]

inf = 10 ** 10
cost = [[inf] * w for _ in range(h)]

walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[i, j] for i in range(-2, 3) for j in range(-2, 3) if [i, j] not in [[0, 0]] + walk]

q = deque()
cost[ch][cw] = 0
q.append([ch, cw, 0])

while q:
    x, y, c = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and cost[nx][ny] > c:
            cost[nx][ny] = c
            q.appendleft([nx, ny, c])

    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and cost[nx][ny] > c + 1:
            cost[nx][ny] = c + 1
            q.append([nx, ny, c + 1])

ans = cost[dh][dw] if cost[dh][dw] != inf else -1
print(ans)

Cまでの早解きでなんとか緑パフォーマンス。