[PYTHON] AtCoder Anfängerwettbewerb 172

AtCoder Anfängerwettbewerb 172

Das letzte Mal bin ich in 20 Minuten zum E-Problem gegangen und habe 100 Minuten über das F-Problem nachgedacht, aber dieses Mal bin ich in 30 Minuten zum D-Problem gegangen und habe 90 Minuten über das E-Problem nachgedacht, aber es war nutzlos. Zunächst einmal mit dem C-Problem begrenzen Obwohl es selten vorkommt, den Rechenaufwand beim Betrachten zu lockern, scheint es für das ABC C-Problem schwierig zu sein, sich um das Doppelte zu entspannen. Selbst das EXCEL-Spaltennamen-C-Problem des vorherigen schreienden Ärgers wurde ein wenig gelöst. Es ist jedoch sicher, dass das C-Problem diesmal schwierig ist, wenn nur etwas weniger als 30% gelöst sind.

ABC172A - Calc

Es brach in ungefähr 2 Minuten durch. Der Code-Test funktionierte nicht und ich reichte ihn ein, nachdem ich das B-Problem geschrieben hatte. Schreiben Sie einfach.

a = int(input())

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

ABC172B - Minor Change

Brechen Sie in ungefähr 2 Minuten durch. Schreiben Sie einfach. Es ist eine andere Zahl. Summende Distanz.

S = input()
T = input()

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

ABC172C - Tsundoku

Durchbrechen Sie in 9,5 Minuten. * O * ( N </ i> log N </ i>) in kumulativer Summe + dichotome Suche. Also dachte ich, dass die * O * (* N * + * M *) Lösung in der Erklärung klug war.

PS: Sie mussten sich keine Gedanken über Randwertfehler machen, wenn Sie bisect_right anstelle von bisect_left verwendet haben.

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)

Nachtrag: Die Erklärung war ein Code, der die kumulative Summe verwendet und nicht die Dichotomie verwendet, aber ohne Verwendung der kumulativen Summe geschrieben werden kann.

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

In 14 Minuten durchbrechen. Etwa die Hälfte entspricht dem Code von ABC152E --Flatten. Wenn Sie addieren, erhalten Sie die Anzahl der Primzahlen. Verwenden Sie diese, um f (X) zu schreiben, und folgen Sie dann der Problemstellung ∑ N </ sup> K = 1 </ sub> K × f ( Fragen Sie einfach nach K). Mit PyPy waren es 2,8 Sekunden, also war es ein Limit, oder es war kein 2-Sekunden-Limit, als ich das Ergebnis sah (lacht).

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

Ich habe 90 Minuten darüber nachgedacht, aber ich konnte es nicht lösen.

Recommended Posts