[PYTHON] Wettbewerbsfähiges Tagebuch für berufliche Hingabe vom 20. bis 22. Tag (14.07. Bis 16.07.)

<! - Wettbewerbsfähige Vorlage für professionelle Hingabe->

Impressionen

In letzter Zeit habe ich das Gefühl, dass es viele gierige Methoden gibt. Ich bin nicht gut darin, also möchte ich mich daran gewöhnen. Es wäre großartig, wenn wir die Rate bald erhöhen könnten ...

20. Tag

ABC141-E Who Says a Pun?

Zeit genommen

50 Minuten Ich dachte, es würde vergehen, wenn ich $ O (N ^ 3) $ drückte, aber ich konnte es nicht tun und schmolz es für weitere 20 Minuten.

Erwägung

Um an eine Zeichenfolge zu denken, die mehrmals vorkommt, reicht es aus, wenn eine bestimmte Zeichenfolge mindestens zweimal vorkommt. Geben Sie diese beiden Zeichenfolgen also als $ s_1 $, $ s_2 $ unten ein.

Erstens bezweifle ich DP, weil es ein Teilstring ist. Ich habe mich jedoch verlaufen, als ich versucht habe, zwei Dinge zu verarbeiten, bei denen sich die Zeichenfolgen nicht überlappen ** und ** gleichzeitig in derselben Zeichenfolge ** denken, und sie vor dem Zeichen $ i $ und nach dem Zeichen $ i + 1 $ zu unterteilen. Ich dachte, aber das war ein schlechter Schachzug.

Während meiner Überlegungen konzentrierte ich mich auf ** Kontinuität ** und dachte, dass dies durch eine einfache Methode gelöst werden könnte, die der Skalierungsmethode ** ähnelt. Das heißt, das erste Zeichen von $ s_1 $ ist das Zeichen $ i $ ($ N $ street), und das erste Zeichen von $ s_2 $ ist das Zeichen $ j (i + 1 \ leqq j \ leqq N) $ ($ Ni $). Betrachten Sie die längste Zeichenfolge, in der $ s_1 $ und $ s_2 $ übereinstimmen (bis zu $ N $). In diesem Fall ist es $ O (N ^ 3) $, also nicht rechtzeitig. (Es ist nicht gut, dass die Diskussion bisher fast 30 Minuten gedauert hat.)

Um diese Methode effizient zu berechnen, ** sollten Sie daher prüfen, ob eine verschwenderische Untersuchung vorliegt **. Dann können Sie sehen, dass ** dasselbe Teil wiederholt in dem Teil berechnet wird, das bestimmt, ob die fortlaufenden Teile übereinstimmen **. Daher ** können Sie die Effizienz verbessern, indem Sie zuerst den hinteren Teil berechnen **, sodass Sie das folgende Array vorbereiten und DP ausführen können.

$ dp [i] [j]: = $ (Das längste gemeinsame Präfix, wenn $ s_1 $ mit dem Zeichen $ i $ beginnt und $ s_2 $ mit dem Zeichen $ j $ beginnt, aber wenn $ i = 0 $ Und $ s_1 $ und $ s_2 $ überlappen sich nicht, auch wenn $ j = 0 $)

Hier ist die Fallklassifizierung des DP-Übergangs bei der Berechnung aus dem letzten Teil wie folgt, und der Maximalwert in dp ist die Antwort, indem dies implementiert wird.

(1) Wenn ($ i $ Zeichen von $ s $) $ = $ ($ j $ Zeichen von $ s $) 　　dp[i][j]=dp[i+1][j+1]+1

(2) Wenn ($ i $ Zeichen von $ s $) $ \ neq $ ($ j $ Zeichen von $ s $) 　　dp[i][j]=0

(✳︎) $ dp [i] [j] $ kann höchstens $ j-i $ sein Wenn dies überschritten wird, kann $ dp [i] [j] = 0 $ gesetzt werden.

(1), (2), (✳︎) können jeweils gezeigt werden, aber sie werden hier weggelassen.

Nachtrag

・ Was ist das längste gemeinsame Präfix? Dies ist das längste gemeinsame Präfix der Zeichenfolgen s und t. Das längste gemeinsame Präfix bei s = ABCBC, t = ABD ist AB, und das längste gemeinsame Präfix bei s = ABC, t = BCD ist eine leere Zeichenfolge.

・ Dieses Mal erhaltenes Wissen Das Problem des Musters, $ N $ um etwa $ O (N ^ 3) $ → $ O (N ^ 2) $ zu schneiden, ist ** Wenn Sie darauf achten, ob es einen Ort gibt, an dem Sie wiederholt verschwenderisch rechnen, wird dies durch DP oder Vorberechnung berechnet Ich kann den Betrag reduzieren **, also habe ich beschlossen, ihn zu bestellen. Es scheint auch, dass dieses Problem auf verschiedene Weise gelöst werden kann, indem verschiedene String-Algorithmen verwendet werden.

n=int(input())
s=input()
dp=[[0]*(n+1) for i in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
        if s[j]==s[i] and dp[i+1][j+1]+1<=j-i:
            dp[i][j]=dp[i+1][j+1]+1
ans=0
for i in range(n):
    for j in range(n):
        ans=max(ans,dp[i][j])
print(ans)

ABC091-C 2D Plane 2N Points

Zeit genommen

Ich dachte über 30 Minuten nach und gab auf.

Fehlerursache

Ich habe versucht, es mit einer gierigen Methode zu lösen, die nicht eindeutig bewiesen werden konnte. Ich konnte keine typische Lösung ausprobieren. (Es sollte nicht so schwierig sein ...)

Erwägung

Da es zwei Sätze von blauen und roten Punkten gibt, betrachten wir hier zunächst die optimalen roten Punkte **, wenn die blauen Punkte festgelegt sind ($ \ weil $ die roten Punkte festgelegt sind). Die Auswahl des besten blauen Punkts für die Zeit ist im Wesentlichen dieselbe.)

Wenn man bedenkt, dass nur wenige rote Punkte für blaue Punkte mit kleinen x-Koordinaten ausgewählt werden können, ist es hier besser, zuerst solche Punkte auszuwählen ($ , weil $ ** x-Koordinaten und y gleichzeitig). In Anbetracht der Koordinaten ist es schwierig, so dass nur eine ** zuerst berücksichtigt wird.) Daher wählen wir die blauen Punkte in der Reihenfolge aus dem mit der kleinsten x-Koordinate aus und wählen für jeden den optimalen roten Punkt aus ($ \ weil $ ** Bei der gierigen Methode ist die Reihenfolge der Auswahl wichtig !! **).

Unter den obigen Angaben ist der optimale Punkt ** der Punkt mit der größten y-Koordinate (unabhängig von der x-Koordinate) unter den auswählbaren roten Punkten **. Dies liegt daran, dass die x-Koordinaten der roten Punkte, die jetzt ausgewählt werden können, immer kleiner sind als die blauen Punkte, die danach ausgewählt werden, da die blauen Punkte mit den kleinsten x-Koordinaten der Reihe nach ausgewählt werden und die y-Koordinate so klein wie möglich sein sollte.

Aus der obigen Überlegung kann durch Speichern des roten Punkts in absteigender Reihenfolge der y-Koordinate und des blauen Punkts in aufsteigender Reihenfolge der x-Koordinate implementiert werden, indem die for-Schleife nur zweimal gedreht wird und $ O (N ^ 2) Es ist eine Lösung für $ (es kann auf $ O (N \ log {N}) $ fallen gelassen werden, aber die Implementierung ist etwas umständlich).

(Es scheint, dass wir das Problem der maximalen Übereinstimmung von zweiteiligen Graphen reduzieren können, also hoffe ich, dass wir es eines Tages auf diese Weise angehen können.)

n=int(input())
red=sorted([list(map(int,input().split())) for i in range(n)],key=lambda x:x[1],reverse=True)
blue=sorted([list(map(int,input().split())) for i in range(n)])
ans=0
for bx,by in blue:
    for rx,ry in red:
        if rx<bx and ry<by:
            ans+=1
            red.remove([rx,ry])
            break
print(ans)

21. Tag

Gelöst Acing Programming Contest 2020-E Kamelzug. Dieser Artikel erklärt ・

22. Tag

ABC144-E Gluttony

Zeit genommen

27 Minuten

Erwägung

Erstens ist die Kombination, die den Maximalwert des Produkts minimiert, die Kombination der Verdauungskosten in aufsteigender Reihenfolge und der Schwierigkeit, in absteigender Reihenfolge zu essen. Es ist gut zu zeigen, dass ** Sie keinen Vorteil erhalten, wenn Sie die optimale Kombination neu anordnen ** (oder Sie erhalten einen Vorteil, wenn Sie die nicht optimale Kombination neu anordnen **) (für weitere Informationen [ARMERIA] Artikel](siehe https://betrue12.hateblo.jp/entry/2019/10/30/011052). Das Folgende ist eine kurze Erklärung.

(Im Folgenden werden in dieser Kombination die $ i $ -ten Verdauungskosten von vorne durch $ a [i] $ und die $ i $ -ten von vorne durch $ f [i] $ dargestellt.)

Ich habe diese Kombination im Ausgangszustand gemacht und versucht, ** $ K $ mal ** mit priority_queue von dort ** zu simulieren, aber $ K $ ist so groß wie $ 10 ^ {18} $, also ist es rechtzeitig. nicht.

Als ich nun darüber nachdachte, $ K $ auf einmal anstatt einzeln zu reduzieren, ging ich davon aus, dass ** jedes Produkt kleiner oder gleich einem bestimmten Wert von $ x $ ** sein könnte. Wenn dann die Kombination von $ (f [i], a [i]) $ $ a [i] \ rightarrow [\ frac {x} {f [i]}] $ ist, ist das Produkt die Mindestanzahl von Schulungen. Kann kleiner als $ x $ sein ($ a [i] \ leqq [\ frac {x} {f [i]}] $, das Produkt ist bereits kleiner als $ x $, daher beträgt die Anzahl der Schulungen 0 ). Wenn daher die Summe der Mindestanzahl von Schulungen für alle mit $ O (N) $ berechnet wird, ist dies ausreichend, wenn sie weniger als $ K $ beträgt.

Hier kann der Mindestwert ($ x ^ {'} $) ** des ** $ x $ gefunden werden, und $ x $ kleiner als $ x ^ {'} $ erfüllt das Thema und $ x ^ nicht Sie können leicht ** Monotonie ** zeigen, dass es nicht zufrieden ist, wenn $ x $ größer als {'} $ ist, also können Sie dieses $ x ^ {'} $ durch Dichotomie nachschlagen. (** Sie können sich das aus der Tatsache vorstellen, dass $ x $ aufgrund von Einschränkungen auf $ a_ {max} \ times f_ {max} $ anwächst **.)

Aus dem oben Gesagten ergibt sich ein Gesamtbetrag der Berechnung von $ O (N \ log (a_ {max} \ mal f_ {max})) $. Wenn ich es normal implementieren würde, würde es in Python nicht funktionieren, also habe ich PyPy verwendet.

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
#Ich kann das nicht ändern
f=sorted(list(map(int,input().split())),reverse=True)
l,r=0,10**12
def cal(x):
    global n,f,a,k
    ret=0
    for i in range(n):
        ret+=max(0,a[i]-(x//f[i]))
    return ret
while l+1<r:
    x=l+(r-l)//2
    if cal(x)<=k:
        r=x
    else:
        l=x
if cal(l)<=k:
    print(l)
else:
    print(r)