AtCoder Beginner Contest 172

AtCoder Beginner Contest 172

Last time I went to E problem in 20 minutes and thought about F problem for 100 minutes, but this time I went to D problem in 30 minutes and thought about E problem for 90 minutes, but it was useless. In the first place, limit with C problem It is rare to relax the amount of calculation while looking at it, but it seems that it is difficult for the ABC C problem to have to relax by double. However, it is certain that the C problem this time is difficult when only a little less than 30% is solved.

ABC172A - Calc

It took about 2 minutes to break through. The code test didn't work, so I submitted it after writing the B question. Just write it.

a = int(input())

print(a + a * a + a * a * a)

ABC172B - Minor Change

Break through in about 2 minutes. Just write. It's a different number. Hamming distance.

S = input()
T = input()

result = 0
for i in range(len(S)):
    if S[i] == T[i]:
        continue
    result += 1
print(result)

ABC172C - Tsundoku

Break through in 9 and a half minutes. * O * ( N </ i> log N </ i>) in cumulative sum + binary search. So, I thought that the * O * (* N * + * M *) solution in the explanation was smart.

PS: You didn't have to worry about boundary value bugs if you used bisect_right instead of bisect_left.

from itertools import accumulate
from bisect import bisect_right

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a = [0] + list(accumulate(A))
b = [0] + list(accumulate(B))

result = 0
for i in range(N + 1):
    if a[i] > K:
        break
    j = bisect_right(b, K - a[i])
    result = max(result, i + j - 1)
print(result)

Addendum: The explanation was a code that uses the cumulative sum and does not use the binary search, but it can be written without using the cumulative sum.

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

b_sum = sum(B)
for i in range(M - 1, -1, -1):
    if b_sum <= K:
        j = i
        break
    b_sum -= B[i]
else:
    j = -1
result = j + 1

a_sum = 0
for i in range(N):
    a_sum += A[i]
    if a_sum > K:
        break
    while a_sum + b_sum > K:
        b_sum -= B[j]
        j -= 1
    result = max(result, (i + 1) + (j + 1))
print(result)

ABC172D - Sum of Divisors

It breaks through in 14 minutes. About half is the same as the code of ABC152E --Flatten. If you add up, you will get the number of prime numbers. Use it to write f (X), and then follow the problem statement ∑ N </ sup> K = 1 </ sub> K × f ( Just ask for K). It was 2.8 seconds with PyPy, so it was a limit, or it wasn't a 2 second limit when I saw the result (laughs).

N = int(input())

sieve = [0] * (N + 1)
sieve[0] = -1
sieve[1] = -1
for i in range(2, N + 1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    for j in range(i * i, N + 1, i):
        if sieve[j] == 0:
            sieve[j] = i


def f(X):
    t = []
    a = X
    while a != 1:
        if len(t) != 0 and t[-1][0] == sieve[a]:
            t[-1][1] += 1
        else:
            t.append([sieve[a], 1])
        a //= sieve[a]
    result = 1
    for _, n in t:
        result *= n + 1
    return result


result = 0
for K in range(1, N + 1):
    result += K * f(K)
print(result)

ABC172E - NEQ

I thought about it for 90 minutes, but I couldn't solve it.

Recommended Posts