ABC123D Revue des questions précédentes

J'ai examiné ABC123 dans Article séparé, mais je peux publier la solution AC. Je ne l'ai pas fait, alors j'aimerais publier la solution AC et l'expliquer dans cet article. Article de Kenchon et Explication J'y fais allusion.

スクリーンショット 2020-01-19 14.39.57.png

Solution AC 1 (solution solution Writer 3)

Cette méthode utilise Priority_queue. Insérez la taille totale dans Priority_queue dans l'ordre comme priorité. ** Il n'y a pas de combinaison de gâteaux qui ne sont pas dans la Priority_queue qui a une priorité plus élevée que la combinaison de gâteaux qui sont dans la Priority_queue (✳︎) ** (je pense que ce ne sera pas difficile à mettre en œuvre si vous faites de votre mieux dans cette verbalisation. Si vous pouvez effectuer l'opération d'insertion tout en garantissant), vous pouvez afficher k de Priority_queue avec la priorité la plus élevée dans l'ordre. Cependant, il est clair que si vous essayez toutes les combinaisons de gâteaux, vous ne pourrez pas le faire à temps en raison de restrictions. Plus précisément, a, b et c sont triés par ordre croissant après avoir ajouté- (tri par ordre décroissant substantiel, traitement pour l'extraction par ordre de priorité décroissante avec heapq), et a [0] avec la priorité la plus élevée parmi eux. ], B [0], c [0] combinaison est insérée dans Priority_queue. Considérez la prochaine combinaison la plus probable dans cette situation. Ensuite, l'un des a [1], b [0], c [0], a [0], b [1], c [0], a [0], b [0], c [1] Vous pouvez voir que c'est une combinaison de. En généralisant ceci, la prochaine combinaison de priorité la plus élevée après ** a [j], a [k], a [l] est a [j + 1], a [k], a [l], a [ Il peut s'agir de j], a [k + 1], a [l], a [j], a [k], a [l + 1] . Par conséquent, l'élément de priorité la plus élevée de Priority_queue est extrait, et pour cet élément a [j + 1], a [k], a [l], a [j], a [k + 1], a [l], En insérant les trois manières de a [j], a [k] et a [l + 1] dans Priority_queue, il est possible d'insérer en satisfaisant (✳︎). Aussi, a [j + 1], a [k], a [l], a [j], a [k + 1], a [l], a [j], a [k], a [l + Puisqu'il est possible qu'il ait déjà été inséré lors de l'insertion des trois voies de 1], j'ai utilisé set pour vérifier s'il était inséré. En outre, il convient de noter que la sortie doit être marquée avec - car heapq est marqué avec - pour récupérer par ordre de priorité décroissante. ( J'ai appris pour la première fois que l'insertion avec un taple fait du premier élément un critère de priorité. **)

answerD.py


import heapq
x,y,z,k=map(int,input().split())
#Comme heapq ne peut être organisé que par ordre croissant,-Si vous ajoutez, ce sera dans l'ordre décroissant
a=sorted([-int(i) for i in input().split()])
b=sorted([-int(i) for i in input().split()])
c=sorted([-int(i) for i in input().split()])
check=set()
ans=[]
heapq.heappush(ans,(a[0]+b[0]+c[0],0,0,0))
check.add((0,0,0))
for i in range(k):
    h=heapq.heappop(ans)
    print(-h[0])
    if h[1]+1<x:
        if (h[1]+1,h[2],h[3]) not in check:
            heapq.heappush(ans,(a[h[1]+1]+b[h[2]]+c[h[3]],h[1]+1,h[2],h[3]))
            check.add((h[1]+1,h[2],h[3]))
    if h[2]+1<y:
        if (h[1],h[2]+1,h[3]) not in check:
            heapq.heappush(ans,(a[h[1]]+b[h[2]+1]+c[h[3]],h[1],h[2]+1,h[3]))
            check.add((h[1],h[2]+1,h[3]))
    if h[3]+1<z:
        if (h[1],h[2],h[3]+1) not in check:
            heapq.heappush(ans,(a[h[1]]+b[h[2]]+c[h[3]+1],h[1],h[2],h[3]+1))
            check.add((h[1],h[2],h[3]+1))

Solution AC 2 (Solution de Writer 1?)

La solution précédente est-elle assez technique? C'était une solution simple (** je pense que c'est basique compte tenu de la façon de gérer Priority_queue. **), mais je pense que cette méthode est extrêmement naturelle. En premier lieu, ce problème a la caractéristique que la quantité de calcul devient importante car A, B et C peuvent être sélectionnés dans n'importe quel ordre. Par conséquent, on pense que la quantité de calcul peut être économisée en ** réduisant d'abord la méthode de sélection entre les deux, puis en pensant à la méthode restante ** (j'avais l'habitude de faire cette méthode, mais c'est inutile. J'en ai trop fait. J'ai senti que ** le problème devait être simplifié **.). Si vous pensez d'abord à x * y, ce sera 10 $ ^ 6 $ au maximum, mais comme k est égal ou inférieur à 3000, vous pouvez voir que vous n'avez pas besoin de penser à 10 $ ^ 6 . Par conséquent, nous savons que nous devons considérer le kth supérieur de la combinaison de a et b. Après cela, en considérant c, il peut être réduit à O ( x \ fois y + k \ fois z $). Cependant, tel quel, il est nécessaire de calculer le montant maximum de calcul de 3 $ \ fois 10 ^ 6 $, qui est la limite en Python. Par conséquent, il est nécessaire de travailler dur pour augmenter la vitesse d'un facteur constant ici. Les accélérations que j'ai faites sont (1) utiliser le tri sans utiliser trié (la différence entre destructif et non destructif, trié est un peu plus lent), et (2) même dans le cas de doubles boucles, utilisez la notation d'inclusion. Surtout ce dernier est beaucoup plus rapide. ** Si vous pensez que la boucle est lente, utilisez la notation d'inclusion **.

Postscript

Lorsque je l'ai vérifié en écrivant, le tri était plus rapide que le tri. Je ne sais pas pourquoi. Je vous serais reconnaissant si vous pouviez me le dire. De plus, mettez tout dans la fonction principale et traitez-la comme une variable locale. Il existe des accélérations telles que l'exécution avec PyPy. Surtout PyPy est incroyablement rapide. Le même code est environ 3 à 5 fois plus rapide que Python.

answerD.py


x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
a.sort()
b.sort()
c.sort()
ab=[a[i]+b[j] for j in range(y) for i in range(x)]
ab.sort(reverse=True)
ab=ab[:k]
l=len(ab)
abc=[ab[i]+c[j] for j in range(z) for i in range(l)]
abc.sort(reverse=True)
for i in range(k):
    print(abc[i])

answerD.py


x,y,z,k=map(int,input().split())
a=sorted([int(i) for i in input().split()])
b=sorted([int(i) for i in input().split()])
c=sorted([int(i) for i in input().split()])
ab=sorted([a[i]+b[j] for j in range(y) for i in range(x)],reverse=True)
ab=ab[:k]
l=len(ab)
abc=sorted([ab[i]+c[j] for j in range(z) for i in range(l)],reverse=True)
for i in range(k):
    print(abc[i])

Recommended Posts

ABC123D Revue des questions précédentes
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 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 127 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 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 067 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 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 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 126 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 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 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 088 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 068 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