AtCoder Beginner Contest 151の感想

ABC151に参加した。

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

A – Next Alphabet

アルファベットの文字列を定義してループを回し、入力した文字と一致すれば次のアルファベットを出力する。

c = input()

alphabet = 'abcdefghijklmnopqrstuvwxyz'

for i in range(len(str(alphabet))):
    if alphabet[i] == c:
        print(alphabet[i + 1])

B – Achieve the Goal

求める点数を計算する。

K点満点なのと、マイナスになった場合は0を出力するよう注意する。

n, k, m = map(int, input().split())
a = [int(x) for x in input().split()]

ans = m * n - sum(a)

if ans > k:
    print(-1)
else:
    print(max(ans, 0))

C – Welcome to AtCoder

ACとWAのフラグを格納する配列を作る。

各提出毎にフラグを更新していき、ACした問題ではWAを更新しないようにする。

WAだけしてACに至らなかったケースを途中まで思いつかず、2WA出してしまった。

n, m = map(int, input().split())

submit = []
for i in range(m):
    temp = [x for x in input().split()]
    submit.append(temp)

ac = [0] * (n + 1)
wa = [0] * (n + 1)

for i in range(m):
    result = submit[i][1]
    question = int(submit[i][0])

    if result == 'AC' and ac[question] == 0:
        ac[question] = 1
    elif result == 'WA' and ac[question] == 0:
        wa[question] += 1

for i in range(n + 1):
    if ac[i] != 1:
        wa[i] = 0

print(sum(ac), sum(wa))

D – Maze Master

グラフと木、探索問題だというのはわかったが、実装したことがなかったので解けず。

今後練習して解けるようにしておく。

追記：下記のアルゴリズムの本を読み、幅優先探索を少し理解できた。

配列外参照を避けるため、与えられた迷路の外枠をすべて壁で囲む。

HとWの制限が緩いため、スタート地点を総当りで探索しても時間内に間に合う。

探索済みのフラグと移動距離を更新しながら幅優先探索を行い、スタート地点からの最大移動距離が答えになる。

from collections import deque


def bfs(maze, x, y):
    m = [1, 0, -1, 0]
    n = [0, 1, 0, -1]
    queue = deque([[x, y]])
    dist = [[-1] * (w + 2) for _ in range(h + 2)]
    dist[x][y] = 0

    while queue:
        sx, sy = queue.popleft()

        for dx, dy in zip(m, n):
            nx = sx + dx
            ny = sy + dy
            if maze[nx][ny] != '#' and dist[nx][ny] == -1:
                queue.append([nx, ny])
                dist[nx][ny] = dist[sx][sy] + 1

    return max(max(x) for x in dist)


h, w = map(int, input().split())

maze = [['#'] * (w + 2)]
for i in range(h):
    maze.append(['#'] + list(map(str, input())) + ['#'])

maze.append(['#'] * (w + 2))

ans = 0
for sy in range(1, w + 1):
    for sx in range(1, h + 1):
        if maze[sx][sy] != '#':
            ans = max(ans, bfs(maze, sx, sy))

print(ans)