[PYTHON] ABC123D Rückblick auf frühere Fragen

Ich habe ABC123 in Separater Artikel überprüft, kann aber die AC-Lösung veröffentlichen. Ich habe es nicht getan, deshalb möchte ich die AC-Lösung veröffentlichen und in diesem Artikel erklären. Kenchons Artikel und Erklärung Ich beziehe mich darauf.

AC-Lösung 1 (Writer-Lösungslösung 3)

Diese Methode verwendet Priority_queue. Fügen Sie die Gesamtgröße in der Reihenfolge Priority_queue als Priorität ein. ** Es gibt keine Kombination von Kuchen, die nicht in der Priority_queue enthalten sind und eine höhere Priorität haben als die Kombination von Kuchen, die in der Priority_queue enthalten sind (✳︎) ** (Ich denke, es wird nicht schwierig sein, sie zu implementieren, wenn Sie in dieser Verbalisierung Ihr Bestes geben. Wenn Sie die Einfügeoperation ausführen können, während Sie garantieren, können Sie k der Priority_queue mit der höchsten Priorität in der angegebenen Reihenfolge ausgeben. Es ist jedoch klar, dass Sie es aufgrund von Einschränkungen nicht rechtzeitig schaffen, wenn Sie alle Kuchenkombinationen ausprobieren. Insbesondere werden a, b und c in aufsteigender Reihenfolge mit Addition sortiert (wesentliche Sortierung in absteigender Reihenfolge, Verarbeitung zum Extrahieren in absteigender Reihenfolge der Priorität mit heapq) und die höchste Priorität a [0 ], B [0], c [0] Kombination wird in Priority_queue eingefügt. Betrachten Sie die nächstwahrscheinlichste Kombination in dieser Situation. Dann eines von a [1], b [0], c [0], a [0], b [1], c [0], a [0], b [0], c [1] Sie können sehen, dass es eine Kombination von ist. Verallgemeinernd ist die nächsthöhere Prioritätskombination nach ** a [j], a [k], a [l] a [j + 1], a [k], a [l], a [ Es kann eines von j], a [k + 1], a [l], a [j], a [k], a [l + 1] ** sein. Daher wird das Element mit der höchsten Priorität von Priority_queue extrahiert und für dieses Element a [j + 1], a [k], a [l], a [j], a [k + 1], a [l], Durch Einfügen aller drei Möglichkeiten von a [j], a [k] und a [l + 1] in Priority_queue ist es möglich, bei Erfüllung von (✳︎) einzufügen. Auch a [j + 1], a [k], a [l], a [j], a [k + 1], a [l], a [j], a [k], a [l + Da es die Möglichkeit gibt, dass es beim Einfügen der drei Möglichkeiten von 1] bereits eingefügt wurde, habe ich set verwendet, um zu überprüfen, ob es eingefügt wurde. Darüber hinaus sollte beachtet werden, dass die Ausgabe mit markiert werden muss, da heapq mit markiert ist, um sie in der Reihenfolge ihrer Priorität abzurufen. (** Ich habe zum ersten Mal erfahren, dass das Einfügen mit einem Taple das erste Element zu einem Prioritätskriterium macht. **)

answerD.py

import heapq
x,y,z,k=map(int,input().split())
#Da heapq nur in aufsteigender Reihenfolge angeordnet werden kann,-Wenn Sie hinzufügen, wird es in absteigender Reihenfolge sein
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))

AC-Lösung 2 (Writer-Lösung Lösung 1?)

Ist die vorherige Lösung ziemlich technisch? Es war eine einfache Lösung (** Ich denke, es ist grundlegend, wenn man bedenkt, wie man mit Priority_queue umgeht. **), aber ich denke, diese Methode ist äußerst natürlich. Erstens hat dieses Problem die Eigenschaft, dass der Rechenaufwand groß wird, weil A, B und C in beliebiger Reihenfolge ausgewählt werden können. Daher wird angenommen, dass der Rechenaufwand eingespart werden kann, indem ** zuerst die Auswahlmethode zwischen den beiden eingegrenzt wird und dann über die verbleibende ** nachgedacht wird (ich habe diese Methode verwendet, aber sie ist nutzlos. Ich habe zu viel getan. Ich hatte das Gefühl, dass ** das Problem vereinfacht werden sollte **.). Wenn Sie zuerst an x * y denken, sind es maximal $ 10 ^ 6 $, aber da k 3000 oder weniger ist, können Sie sehen, dass Sie nicht an $ 10 ^ 6 $ denken müssen. Daher wissen wir, dass wir das oberste k-te der Kombination von a und b berücksichtigen sollten. Danach kann es unter Berücksichtigung von c auf O reduziert werden ($ x \ mal y + k \ mal z $). Es ist jedoch erforderlich, den maximalen Berechnungsbetrag von $ 3 \ mal 10 ^ 6 $ zu berechnen, was die Grenze in Python darstellt. Daher muss hier hart gearbeitet werden, um die Geschwindigkeit um einen konstanten Faktor zu erhöhen. Die Beschleunigungen, die ich durchgeführt habe, sind: (1) Sortieren ohne Sortieren verwenden (der Unterschied zwischen destruktiv und zerstörungsfrei, sortiert ist etwas langsamer) und (2) selbst bei Doppelschleifen die Einschlussnotation verwenden. Besonders letzteres ist viel schneller. ** Wenn Sie der Meinung sind, dass die Schleife langsam ist, verwenden Sie die Einschlussnotation **.

Nachtrag

Als ich es beim Schreiben überprüfte, war das Sortieren schneller als das Sortieren. Ich weiß nicht warum. Ich würde es begrüßen, wenn Sie es mir sagen könnten. Fügen Sie außerdem alles in die Hauptfunktion ein und behandeln Sie es als lokale Variable. Es gibt Beschleunigungen wie das Ausführen mit PyPy. Besonders PyPy ist wahnsinnig schnell. Der gleiche Code ist ungefähr 3-5 mal schneller als 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])