[PYTHON] AtCoder Beginner Contest 108 Revue des questions précédentes

Temps requis

Impressions

Je n'ai pas pu me consacrer à l'écriture un article de plus de 10 000 caractères sur itertools. De plus, quand je résolvais cela, j'étais coincé dans un mystère à B et je manquais de temps, donc je ne pouvais pas passer assez de temps sur D. Impossible! Quand j'ai regardé la réponse, c'était la solution attendue, donc je dois bien réfléchir ... Ce manque de stabilité est la raison pour laquelle il reste vert, mais comment peut-il être amélioré?

Problème A

Le nombre impair est calculé par «k // 2», donc le reste est un nombre pair.

answerA.py

k=int(input())
print((k-k//2)*(k//2))

Problème B

Ce problème à lui seul a pris plus de 30 minutes. Pour une raison quelconque, j'ai mal compris qu'un côté du carré était parallèle à x et y ... Après tout, puisque nous pouvons dessiner un triangle congruent comme indiqué ci-dessous, nous pouvons dériver linéairement les coordonnées des carrés restants à partir des coordonnées des deux points donnés.

answerB.py

x1,y1,x2,y2=map(int,input().split())
a=x1-x2
b=y1-y2
print(x2+b,y2-a,x1+b,y1-a)

Problème C

Puisque $ a + b, b + c, c + a $ est un multiple de K, considérons le reste de $ a, b, c $ divisé par K.

Ici, si chaque reste est $ x, y, z (0 \ leqq x, y, z \ leqq K) $, alors $ x + y = (0 \ ou \ K), y + z = (0) Il suffit que \ ou \ K), z + x = (0 \ ou \ K) $ tienne, et $ (x, y, z) = (\ frac {K} {2}, \ frac {K} {2}, \ frac {K} {2}) \ ou \ (0,0,0) $.

De plus, j'ai rapidement découvert que j'avais besoin d'un reste, j'ai donc sauvegardé tous les restes dans le dictionnaire, mais je n'ai besoin de les enregistrer que pour k // 2 ou 0.

answerC.py

n,k=map(int,input().split())
d=dict()
for i in range(k):
    d[i]=0
for i in range(1,n+1):
    d[i%k]+=1
#print(d)
if k%2!=0:
    print(d[0]**3)
else:
    print(d[0]**3+d[k//2]**3)

Problème D

** Les problèmes de graphes sont toujours effrayants ... **. Je veux résoudre beaucoup de problèmes de graphes et m'y habituer, mais je n'ai pas le temps. Je n'ai pas pu le résoudre pendant le concours, j'ai donc jeté un coup d'œil à ce blog, mais je suis simplement conforme à la politique que j'ai établie. J'ai réalisé que c'était bon et flétri. ** Je n'ai pas assez de puissance pour le pousser selon ma propre politique ** ...

Étant donné que tous les chemins sont différents et que tous les chemins de 0 à L-1 doivent être générés par incréments de 1 et qu'il y a de nombreuses restrictions, j'ai d'abord pensé que ** il n'est pas bon de penser correctement aux chemins **. De plus, comme il peut y avoir deux façons selon que le chemin est passé ou non, j'ai remarqué que ** les côtés peuvent être exprimés par le fait que le bit est défini ou non **.

Je ne pouvais pas ** dessiner un diagramme précis et expérimenter ** pour voir si cela pouvait être exprimé avec ce bit. Bien qu'il s'agisse d'une descente, vous pouvez changer le côté sélectionné selon que le bit est défini ou non en procédant comme suit.

Dans le cas ci-dessus, 0 à 15 peuvent être représentés comme 16 chemins différents en considérant chaque ** $ i → i + 1 $ comme le bit $ i-1 $ ** (L = 16). dans le cas de). De la même manière, vous pouvez facilement voir que 0 à 31 peut être représenté en ajoutant les 6 sommets (L = 32). Par conséquent, si L est une puissance de 2, il semble qu'elle puisse être exprimée, et dans d'autres cas (L = 19).

Ici, plus vous ajoutez d'arêtes, plus vous aurez de chemins différents, alors pensez à augmenter les arêtes, mais ne les augmentez pas aveuglément. Par exemple, supposons que vous ajoutiez 4 → 5 côtés. À ce stade, le nombre de chemins différents augmente de $ 2 ^ 3 $ ($ \ car $ 1 → 4 chemins valent $ 2 ^ 3 $), donc le nombre total de chemins différents est de 24. Par conséquent, il dépasse 19 lignes. En pensant de la même manière, ** ajouter un côté qui s'étend de chaque sommet $ i $ au plus grand nombre de sommets augmentera le nombre de chemins qui diffèrent de $ 2 ^ {i-1} $ **. De plus, le chemin qui augmente à ce moment peut être exprimé par incréments de 1 (ce n'est pas difficile si vous dessinez un diagramme et expérimentez).

Par conséquent, lorsque L est affiché en binaire, déterminez combien de sommets il y a à partir du bit du chiffre le plus élevé, regardez ceux de 1 dans l'ordre avec les bits en dessous, et s'il y a un de ce bit, En étendant les côtés des sommets correspondants aux derniers sommets, il est possible de créer L chemins différents tout en satisfaisant le nombre de sommets et le nombre de côtés.

De plus, je pense que l'explication est un peu difficile à comprendre, je vais donc vous montrer comment la résoudre lorsque L = 19 (à la main) ci-dessous.

De plus, dans le code ci-dessous, la fonction drop while est utilisée pour trouver le bit supérieur (en cherchant à partir du haut de $ \ car $ pour trouver l'élément qui devient 1 pour la première fois). Il était vivant d'étudier itertools en écrivant cet article.

answerD.py

from itertools import dropwhile
l=int(input())
#Alignez à partir du bit supérieur
k=[(l>>i & 1) for i in range(20)][::-1]
#Liste ci-dessous 1 bit pour la première fois
k=list(dropwhile(lambda x:x==0,k))

n=len(k)
path=[]
for i in range(n-1):
    path.append((i+1,i+2,0))
    path.append((i+1,i+2,2**i))

path_len=2**(n-1)
for i in range(1,n):
    if k[i]:
        x=n-1-i
        path.append((x+1,n,path_len))
        path_len+=(2**x)

m=len(path)
print(n,m)
for i in path:
    print(i[0],i[1],i[2])