Rapport de participation au concours de programmation AtCoder Acing 2020

Rapport de participation au concours de programmation AtCoder Acing 2020

J'avais tellement sommeil que j'ai fait une sieste de 20 minutes juste avant et j'ai fait de mon mieux.

aising2020A - Number of Multiples

Percer en une minute et demie. Il suffit d'écrire en fonction des conditions du problème. Cela prend du temps, donc je ne pense pas à le résoudre avec * 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)

Post-scriptum: * O * (1)

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

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

aising2020B - An Odd Problem

Percer en 2 minutes, il suffit d'écrire en fonction des conditions du problème.

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)

Post-scriptum: J'aurais dû découper le nombre pair ...

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

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

aising2020C - XYZ Triplets

Il a percé en 6 minutes et demie N ≤ 10 4 </ sup> Donc j'ai pensé que ça passerait même dans une triple boucle.

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

Je n'ai pas pu percer. Quand A = B * C, j'ai pensé que je pourrais utiliser A% m = (B% m) * (C% m)% m pour obtenir un grand nombre de restes, alors je l'ai utilisé pour le construire, mais TLE Je ne suis pas sûr car j'obtiens le RE et le RE. Le premier processus peut être * O * (1) par pré-calcul, mais que dois-je faire après le second?

Addendum: La valeur maximale renvoyée par * f * (* n ) est log 2 </ sub> ( n *), donc 2 2 × 10 5 </ sup> </ sup > → 2 × 10 5 </ sup> → 17,6 → 4,1 → 2,0 → 1 → 0 et il converge en un clin d'œil. Donc j'aurais dû le faire seulement la première fois. Regardez TLE * f * ( C'était stupide de courir pour accélérer * n *).

RE a été émis à l'origine lorsqu'un seul bit était défini, et lorsque le seul bit défini était inversé, * popcount * n'a pas été remarqué comme étant égal à 0 et a été divisé par 0. TLE S'affiche sans savoir que le journal 2 </ sub> (* X *) est même 2 × 10 5 </ sup> * O * ( N </ i> > log X </ i>) car il a été écrit.

Bien que l'idée soit correcte, j'ai senti que je ne pouvais pas la résoudre en raison de certaines 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