AtCoder Beginner Contest 160の感想

AtCoder

2020.03.282020.04.14

ABC160に参加した。

AtCoder Beginner Contest 160 - AtCoder

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

A – Coffee

そのまま実装。

s = input()

if s[2] == s[3] and s[4] == s[5]:
    print('Yes')
else:
    print('No')

B – Golden Coins

出来るだけ多くの500円硬貨を持てるように計算する。

x = int(input())

a = x // 500
x %= 500

b = x // 5

ans = a * 1000 + b * 5
print(ans)

C – Traveling Salesman around Lake

円周を数直線で考え、家と家の間の距離を格納したリストを作成する。

AnとA1の距離がk – An + A1になることに注意する。

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

diff = [a[i + 1] - a[i] for i in range(n - 1)] + [k - a[-1] + a[0]]
ans = sum(diff) - max(diff)
print(ans)

D – Line++

時間内に解けなかったのでコンテスト終了後に考察。

幅優先探索を行い、全ての頂点までの距離を探索する。

探索済みのフラグとしてINF利用しつつ、距離を計算していく。

計算した距離が何個出てきたのかを回答の配列に加算していくが、そのままだと右から移動してきた場合と左から移動してきた場合の両方を出力してしまうため、2で割った値が答えになる。

XとYはあらかじめ1を引いてくとリストの参照がやりやすい。

配列外参照をしないようif分に条件を加えておくと安心。

from collections import deque

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

inf = 100100100
x -= 1
y -= 1

ans = [0] * n

for i in range(n):
    dist = [inf] * n
    queue = deque()
    queue.append(i)
    dist[i] = 0
    while queue:
        current = queue.popleft()
        d = dist[current]

        if current - 1 >= 0 and dist[current - 1] == inf:
            queue.append(current - 1)
            dist[current - 1] = d + 1
        if current + 1 < n and dist[current + 1] == inf:
            queue.append(current + 1)
            dist[current + 1] = d + 1
        if current == x and dist[y] == inf:
            queue.append(y)
            dist[y] = d + 1
        if current == y and dist[x] == inf:
            queue.append(x)
            dist[x] = d + 1

    for j in range(n):
        ans[dist[j]] += 1

for k in range(1, n):
    print(ans[k] // 2)

C問題で手こずって大幅に時間がかかってしまい、灰色パフォーマンスになってしまった。