AtCoder Acing Programming Contest 2020 Participation Report

AtCoder Acing Programming Contest 2020 Participation Report

I was so sleepy that I took a nap for 20 minutes just before and did my best.

aising2020A - Number of Multiples

Break through in one and a half minutes. Just write according to the conditions of the problem. It takes time, so I do not think about solving it with * O * (1).

L, R, d = map(int, input().split())

result = 0
for i in range(L, R + 1):
    if i % d == 0:
        result += 1
print(result)

Postscript: * O * (1)

L, R, d = map(int, input().split())

print(R // d - (L - 1) // d)

aising2020B - An Odd Problem

Break through in 2 minutes. Just write according to the conditions of the problem.

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

result = 0
for i in range(N):
    if (i + 1) % 2 == 1 and a[i] % 2 == 1:
        result += 1
print(result)

Postscript: I should have skipped even-numbered slices ...

N, *a = map(int, open(0).read().split())

print(sum(1 for e in a[::2] if e % 2 == 1))

aising2020C - XYZ Triplets

It broke through in 6 and a half minutes. N ≤ 10 4 </ sup> So I thought it would pass even in a triple loop. In fact, it passed.

N = int(input())

result = [0] * (N + 1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            n = x * x + y * y + z * z + x * y + y * z + z * x
            if n > N:
                break
            result[n] += 1

print(*result[1:], sep='\n')

aising2020D - Anything Goes to Zero

I couldn't break through. When A = B * C, I thought that I could get a large number of remainders using A% m = (B% m) * (C% m)% m, so I built it using it, but TLE I'm not sure because I get the RE and the RE. The first process can be * O * (1) by pre-calculation, but what should I do after the second?

Addendum: The maximum value returned by * f * (* n ) is log 2 </ sub> ( n *), so 2 2 × 10 5 </ sup> </ sup > → 2 × 10 5 </ sup> → 17.6 → 4.1 → 2.0 → 1 → 0 and it converges in a blink of an eye. So I should have managed it only the first time. Look at TLE * f * ( It was stupid to run to speed up * n *).

RE was originally issued when only one bit was set, and when the only set bit was inverted, * popcount * was not noticed to be 0, and it was divided by 0. TLE Was displayed in log 2 </ sub> (* X *) without being aware that it was 2 × 10 5 </ sup> * O * ( N </ i> > log X </ i>) because it was written.

Although the idea was correct, I felt that I could not solve it due to some omissions.

def popcount(n):
    return bin(n).count("1")


def f(n):
    if n == 0:
        return 0
    return 1 + f(n % popcount(n))


N = int(input())
X = input()

c = X.count('1')
t1 = [0] * N
t1[0] = 1 % (c + 1)
for i in range(1, N):
    t1[i] = (t1[i - 1] << 1) % (c + 1)
x1 = 0
for i in range(N):
    if X[i] == '0':
        continue
    x1 += t1[N - 1 - i]

if c - 1 != 0:
    t2 = [0] * N
    t2[0] = 1 % (c - 1)
    for i in range(1, N):
        t2[i] = (t2[i - 1] << 1) % (c - 1)
    x2 = 0
    for i in range(N):
        if X[i] == '0':
            continue
        x2 += t2[N - 1 - i]

result = []
for i in range(N):
    if X[i] == '0':
        n = (x1 + t1[N - 1 - i]) % (c + 1)
    elif X[i] == '1':
        if c - 1 == 0:
            result.append(0)
            continue
        n = (x2 - t2[N - 1 - i]) % (c - 1)
    result.append(1 + f(n))
print(*result, sep='\n')

Recommended Posts