[PYTHON] 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.
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
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