AtCoder Beginner Contest 170の感想

ABC170に参加した。

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

A – Five Variables

総和の15から差分を取る。

ans = 15 - sum(list(map(int, input().split())))
print(ans)

B – Crane and Turtle

制約が小さいので総当り。

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

for i in range(101):
    for j in range(101):
        if i + j == x and 2 * i + 4 * j == y:
            print('Yes')
            exit()

print('No')

C – Forbidden List

pに含まれない整数を全て求めるには、全体の集合とpの排他的論理和を取ればいい。

問題文に整数は正とは限らないと書いてあるので、負の値も対象にする。

制約が100なので、少し多めに-200~200で考える。

最後に、正解の候補が複数ある時は最小の１つを答える、という条件判定を加えて完成。

x, n = map(int, input().split())
p = list(map(int, input().split()))

if n == 0:
    print(x)
else:
    num = list(set(range(-200, 200)) ^ set(p))
    num = sorted([[abs(i - x), i] for i in num])
    if len(num) >= 2 and num[0][0] == num[1][0]:
        print(min(num[0][1], num[1][1]))
    else:
        print(num[0][1])

D – Not Divisible

コンテスト中に解けなかった。

愚直に組むとO(N^2)になって間に合わない。

最初に10^6の配列より少し大きいを作っておき、Ajの倍数になる所だけフラグを降ろしていけばいい。

フラグが残っている箇所の総和が答え。

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
prime = [1] * 1000010

for i in a:
    for j in range(i + i, 1000001, i):
        prime[j] = 0

c = Counter(a)
ans = 0
for i in a:
    if prime[i] and c[i] == 1:
        ans += 1
print(ans)

Cで時間がかかり、Dが解けなかったのでパフォーマンスは振るわなかった。