AtCoder Beginner Contest 182の感想

ABC182に参加した。

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

A – twiblr

引き算するだけ。

a, b = map(int, input().split())
ans = 2 * a + 100 - b
print(ans)

B – Almost GCD

1からmax(A)までの数で総当りで割り算する。

O（NｘA）＝０（10^5）なので間に合う。

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

ans = 1
gcd_like = 0
for i in range(2, max(a) + 1):
    cnt = 0
    for j in range(n):
        if a[j] % i == 0:
            cnt += 1
    if cnt >= gcd_like:
        gcd_like = cnt
        ans = i

print(ans)

C – To 3

消すか消さないかの2通りを各桁で判定していくので、bit全探索が使える。

3の倍数は各桁の合計が3で割り切れる性質があるので、bit全探索で求めた値を総当りで判定すればOK。

N<10^18で最大18桁のbit全探索はO(2^18)=O(10^5)になる。

PythonだとTLEになる可能性があるが、pypyなら間に合う。

n = input()
k = len(n)

ans = 10 ** 10
for i in range(1, 2 ** k):
    pattern = [0] * k
    for j in range(k):
        if (i >> j) & 1:
            pattern[j] = 1

    temp = 0
    for p, q in zip(pattern, n):
        temp += p * int(q)
    if temp % 3 == 0:
        ans = min(ans, k - sum(pattern))

print(ans if ans != 10 ** 10 else -1)

D – Wandering

愚直に実装するとO(N^2)のループになって間に合わない。

現在座標、移動量、最大座標の値を持つようにするとO(N)で実装でき間に合う。

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

totalMove = 0
maxMove = 0
now = 0
ans = 0

for i in a:
    totalMove += i
    maxMove = max(maxMove, totalMove)
    ans = max(ans, now + maxMove)
    now += totalMove

print(ans)

C問題でTLEを出し、D問題でてこずってしまったのでパフォーマンスは良くなかった。