AtCoder Beginner Contest 108 Revue des questions précédentes

Temps requis

スクリーンショット 2020-05-09 10.27.05.png

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.

スクリーンショット 2020-05-09 10.27.05.png

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.

IMG_0331.JPG

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.

IMG_0332.PNG

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])

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes
AtCoder Beginner Contest 125 Revue des questions précédentes
AtCoder Beginner Contest 109 Revue des questions précédentes
AtCoder Beginner Contest 118 Revue des questions précédentes
AtCoder Beginner Contest 080 Revue des questions précédentes