Concours de programmation Atcoder Acing Python

Résumé

C'était difficile. C'était A, B, C 3 questions AC. Je ne connais pas bien le nombre binaire, donc D saute le moment où je vois le problème, et j'ai l'impression de pouvoir résoudre le problème E, mais je ne comprends pas même si je regarde l'exemple de réponse.

problème

(https://atcoder.jp/contests/aising2020/tasks)

A. Number of Multiples

Répondre

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

count = 0
for i in range(L, R+1):
    if i % d == 0:
        count += 1

print(count)

Je l'ai écrit docilement. D'autres semblent écrire d'une manière plus cool.

B. An Odd Problem

Répondre

N = int(input())
a = list(map(int, input().split()))

count = 0
for i in range(0, N, 2):
    if i % 2 == 0 and a[i] % 2 != 0:
        count += 1
print(count)

J'ai aussi écrit ceci honnêtement. Le problème est étrange, mais les indices de la liste sont pairs.

C. XYZ Triplets

Répondre

N = int(input())

keys = [i for i in range(1, N+1)]
values = [0] * N
count_dict = dict(zip(keys, values))

for x in range(1, N//6+7):
    for y in range(x, N//6+7):
        for z in range(y, N//6+7):
            n = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if n > N:
                break
            if x == y and y == z:
                count_dict[n] += 1
            elif x != y and x != z and y != z:
                count_dict[n] += 6
            else:
                count_dict[n] += 3

for v in count_dict.values():
    print(v)

Pour être honnête, tournez la boucle for de range (1, N + 1) '' pour chacun des x, y, z et `` x ** 2 + y ** 2 + z ** 2 + x Il semble que * y + y * z + z * x = n``` devrait être jugé. Cependant, comme la contrainte est 10 ** 4, elle ne sera pas à temps pour une triple boucle normale, pensez donc à réduire la quantité de calcul.

La première chose à laquelle j'ai pensé était que si (x, y, z) = (1,1,1) , n est 6, donc la valeur maximale qui peut être tournée dans une boucle for est . N // 6 semble bon. Cependant, considérant que l'indice doit être + 1```, j'ai choisi N // 6 + 7 ''avec une marge. (En production, j'ai utilisé `` `` N // 6 + 7```, mais si j'utilise la contrainte `` `` 10 ** 4``` à l'envers, `` `` (x, y, z) Vous pouvez voir que `` ne peut être utilisé que jusqu'à environ 100. Je n'ai pas remarqué cela pendant la production ...)

Donc, il semble que cela seul ne sera probablement pas à temps, alors je vais envisager de réduire un peu plus la quantité de calcul.

Si vous donnez quelques exemples, vous remarquerez ce qui suit. --(1,2,3)et (1,3,2) `` et (2,1,3) et`` (2,3) , 1) `` et (3,1,2) et`` (3,2,1) , où x, y, z sont tous différents, n est la même valeur Il y a 6 combinaisons

• Les deux sont les mêmes, comme (1,1,2) et (1,2,1) '' et (2,1,1) 1 Il y a trois combinaisons où n est le même lorsque les deux sont différents --Il y a une combinaison où n est la même valeur lorsque tous les nombres sont identiques, comme (1,1,1) ''.

Par conséquent, la plage de la boucle for de x, y, z est range (1, N // 6 + 7) , range (x, N // 6 + 7) '', respectivement. Comme range (y, N // 6 + 7) '' ``, il semble que count devrait être +6, +3, +1 dans les trois cas ci-dessus.

Après cela, si n dépasse N, vous pouvez réussir à le faire en ajoutant break```.