La dernière fois, je suis allé au problème E en 20 minutes et j'ai pensé au problème F pendant 100 minutes, mais cette fois je suis allé au problème D en 30 minutes et j'ai pensé au problème E pendant 90 minutes, mais c'était inutile. En premier lieu, limite avec le problème C Bien qu'il soit rare de relâcher la quantité de calcul tout en le regardant, il semble difficile pour le problème ABC C. d'avoir à se détendre par double. Cependant, il est certain que le problème C est cette fois difficile lorsque seulement un peu moins de 30% est résolu.
Il a éclaté en environ 2 minutes. Le test de code n'a pas fonctionné et je l'ai soumis après avoir écrit le problème B. Il suffit d'écrire.
a = int(input())
print(a + a * a + a * a * a)
Pause en 2 minutes environ. Il suffit d'écrire. C'est un chiffre différent.
S = input()
T = input()
result = 0
for i in range(len(S)):
if S[i] == T[i]:
continue
result += 1
print(result)
Percer en 9 minutes et demie. * O * ( N </ i> log N </ i>) en somme cumulée + dichotomie. J'ai pris soin de ne pas provoquer de bug de valeur limite dans la dichotomie. J'ai donc pensé que la solution * O * (* N * + * M *) dans l'explication était intelligente.
PS: Vous n'aviez pas à vous soucier des bogues de valeur limite si vous utilisiez bisect_right au lieu de 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)
Post-scriptum: l'explication était un code qui utilise la somme cumulée et n'utilise pas la dichotomie, mais il peut être écrit sans utiliser la somme cumulée.
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)
Percer en 14 minutes. Environ la moitié est identique au code de ABC152E --Flatten. Si vous additionnez, vous obtiendrez le nombre de nombres premiers. Utilisez-le pour écrire f (X), puis suivez l'énoncé du problème ∑ N </ sup> K = 1 </ sub> K × f ( Il suffit de demander K). C'était 2,8 secondes avec PyPy, donc c'était une limite, ou ce n'était pas une limite de 2 secondes quand j'ai vu le résultat (rires).
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)
J'y ai réfléchi pendant 90 minutes, mais je n'ai pas pu le résoudre.
Recommended Posts