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.
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)
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)
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)
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)
I thought about it for 90 minutes, but I couldn't solve it.
Recommended Posts