AtCoder Beginner Contest 170 (A~D)

先日「D問題はさくっとACできるようになってきた」などとほざきましたが、やってしまいました。

どうも、 予め要素ごとのboolなどの情報（今回のD問題で言えば割り切れるかどうか）を配列で持っておく 発想が身についていない模様。激しく反省せねば。。。

D問題までのPython ACコードです。

https://atcoder.jp/contests/abc170/tasks/abc170_a

import sys
sys.setrecursionlimit(10**6)

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

print(x.index(0)+1)

https://atcoder.jp/contests/abc170/tasks/abc170_b

"""
a+b = x
2*a+4*b = y

2*a+2*b = 2*x
2*a+4*b = y

b = y/2-x
a = 2*x-y/2
"""

import sys
sys.setrecursionlimit(10**6)

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

b = y/2-x
a = 2*x-y/2

if b >= 0 and b == int(b) and a >= 0 and a == int(a):
    print('Yes')
else:
    print('No')

https://atcoder.jp/contests/abc170/tasks/abc170_c

import sys
sys.setrecursionlimit(10**6)

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

if n != 0:
    p = list(map(int, input().split()))

    ll = [x]
    lu = [x]
    i = 1
    
    for _ in range(2*n):
        if ll[-1] not in p:
            print(ll[-1])
            break
        elif lu[-1] not in p:
            print(lu[-1])
            break
        ll.append(ll[-1]-i)
        lu.append(lu[-1]+i)
else:
    print(x)

https://atcoder.jp/contests/abc170/tasks/abc170_d

"""
Point: 割り切れるかどうかの情報を配列で持っておく
"""

N = int(input())
A = [int(i) for i in input().split()]

D = set()
S = set()
for i in range(N):
    if A[i] in S:
        D.add(A[i])
    else:
        S.add(A[i])

M = max(S)

X = [1 for i in range(M+1)] # 割り切れない場合1
for a in S:
    if a in D:
        X[a] = 0
    for i in range(2*a, M+1, a):
        X[i] = 0

ans = 0
for i in range(N):
    if X[A[i]] == 1:
        ans += 1
print(ans)

これまでのA-D問題を中心としたPythonコードは以下に入れています。

github.com