[PYTHON] Wettbewerbsfähiger professioneller Andachtsrekord 1. bis 3. Tag (10 / 14,15,17)
Ich werde einen Artikel veröffentlichen, in dem ich die Rezension von Arimoto (mit Schwerpunkt auf dem Problem von Mr. Kenchons Artikel) und AtCoders Hingabe aufzeichne. Ich möchte mindestens einen Monat lang mein Bestes geben. Außerdem werde ich nur einen Link in den Code einfügen, da dies viele Probleme in einem Artikel verursachen kann.
Erster Tag
Arimoto Hingabe
Ich habe auch JOIs Darts AGC033-A gelöst, aber ich werde es diesmal weglassen, weil es einfach ist.
ARC037B - Baumtest
** $ N $ Verketteter Graph ohne geschlossene Eckpunkte $ \ leftrightarrow $$ N $ Top Tree $ \ leftrightarrow $$ N $ Graph mit $ N-1 $ Kanten, die durch Eckpunkte verbunden sind **
Ich vergesse manchmal die obige Paraphrase, also werde ich sie in meinem Kopf behalten.
In diesem Problem müssen Sie nur die Verbindungskomponenten zählen, die einen Baum bilden, und Sie müssen nur die Verbindungskomponenten mit Union Find ineinander zerlegen und herausfinden, wie viele Seiten jede enthält.
Einreichung → Link
AtCoder Hingabe
diff:1831
Ergebnis: Wechselstrom? Insgesamt ca. 1,5 Stunden (Ich kenne die genaue Zeit nicht, weil ich den Computer lange nicht berühre)
Erwägung
Ich möchte die Wörterbuchreihenfolge minimieren, daher werde ich zunächst über den ** optimalen Weg zur Reduzierung der Peaks ** nachdenken. Anfangs ist $ i \ in [0, n-1] $ der größte Peak und das kleinste Indexelement $ k $. Durch schrittweises Reduzieren dieses Peaks ** finden Sie den kleinsten Index mit dem größten Peak **. Dann wird $ i \ in [0, k-1] $ das Element mit dem größten Peak und dem kleinsten Index $ l $. Dies wird ** rekursiv wiederholt **. Wenn Sie also das kumulative Maximum (indiziert) ermitteln, können Sie feststellen, welcher Berg mit $ O (n) $ der größte in der Mitte ist.
Die obige Diskussion hat uns gezeigt, wie man den maximalen Index verschiebt, aber wir müssen herausfinden, wie oft jeder Index erscheint. Betrachten Sie zu diesem Zeitpunkt die folgende Abbildung (der rote Kreis ist die Position des Index, durch den Sie sich bewegen).
Mit anderen Worten, die Häufigkeit, mit der der Index eines Berges $ i $ erscheint, ist (die Summe der Höhen jedes Berges, reduziert auf die Höhe des nächsten Berges $ j $), also (die Anzahl der Berge, die größer oder gleich dem Berg $ i $ sind) $ \ mal. $ (Höhe des Berges $ i $ - Höhe des Berges $ j $) + $ \ sum_ {k} $ {(Höhe des Berges $ k $ niedriger als Berg $ i $ und höher als Berg $ j $) - ( Berg $ j $ Höhe)} ist die Antwort. Dies kann als $ O (n) $ angesehen werden, indem ** die Berge in aufsteigender Reihenfolge angeordnet und die Anzahl der Berge mit einer Höhe von $ i $ oder mehr ** gespeichert werden.
Daher besteht die Antwort darin, die Häufigkeit aufzuzeichnen, mit der jeder Index gespeichert wird, und schließlich alle zusammen auszugeben. Außerdem wird der Engpass sortiert und der Gesamtbetrag der Berechnung beträgt $ O (n \ log {n}) $.
Einreichung → Link
der 2. Tag
AtCoder Hingabe
diff:1740
Ergebnis: AC in ca. 20 Minuten (aber Esper)
Erwägung
Ich habe es durch Intuition gelöst, aber es scheint, dass die Antwort richtig war. Allerdings neige ich dazu, in letzter Zeit mit BIT zu schlagen, daher möchte ich es mit der $ O (N) $ -Lösung lösen können.
Mir ist aufgefallen, dass ** die Operation reversibel ist ** (✳︎). Da es reversibel ist und nur zu $ A $ oder $ B $ vereinheitlicht werden kann, habe ich beschlossen, hier jedes Zeichen zu $ B $ ** zu vereinheitlichen. Dann kann jede Zeichenfolge in eine beliebige von (leere Zeichenfolge, $ B, BB $) umgewandelt werden. Es muss auch geprüft werden, ob es zwischen ** (leere Zeichenfolge, $ B, BB $) ** konvertiert werden kann, was [redaktionell] ist (https://img.atcoder.jp/arc071/editorial). Es kann nicht wie in pdf gezeigt transformiert werden.
Wenn es mit $ B $ vereinheitlicht ist, wird welche von (leere Zeichenfolge, $ B, BB $) durch den Rest der Division der Länge der Zeichenfolge durch 3 bestimmt. Das heißt, ** $ (xs \ times 2 + xt), wobei die Anzahl von $ A und B $ in der ausgewählten partiellen fortlaufenden Zeichenfolge von $ S und T $ $ (xs, ys) bzw. (xt, yt) $ beträgt. Wenn % 2 = (ys \ times 2 + yt) % 2 $ gilt, kann dieselbe Zeichenfolge ** erstellt werden. Wenn daher die kumulative Summe ** aus der Anzahl von ** $ A, B $ entnommen wird, kann die Anzahl von $ A, B $ in einem bestimmten Abschnitt mit $ O (1) $ berechnet werden. Daher können Sie bis zu $ 10 ^ 5 $ Anfragen mit hoher Geschwindigkeit beantworten.
Während des Wettbewerbs habe ich $ 1 für $ A $ in jedem Index und 0 für $ B $ festgelegt. ** Speichern Sie die Informationen von $ S und T $ in BIT **, und wenn eine Abfrage eingeht, beträgt die Summe $ A $. Ich habe nach der Anzahl gesucht, aber die kumulierte Summe ist einfacher und schneller zu implementieren.
(✳︎)… Ich habe es geschafft, während des Wettbewerbs etwas zu tun, aber ich wollte es lösen, nachdem ich es richtig bewiesen hatte.
Einreichung → Link
diff:1831
Ergebnis: AC in ca. einer Stunde (viel Pena spucken)
Erwägung
Es war ein Problem, in dem ich nicht sehr gut war, weil es sich um ein zweidimensionales Koordinatensystem handelte, aber ich habe es gelöst. Ich möchte diese Gelegenheit nutzen, um meine Schwächen zu zerstreuen.
Zeichnen Sie zuerst ein Diagramm und denken Sie darüber nach. Die Zeit, die Sie benötigen, um kosmischen Strahlen zwischen zwei Kreisen ausgesetzt zu werden, ist das Minimum, wenn Sie sich auf der Linie bewegen, die die Zentren verbindet. * ist. Mit anderen Worten, die Zeit, die kosmischen Strahlen ausgesetzt werden muss, wenn sie sich zwischen zwei Kreisen bewegen, beträgt max (0, (Abstand zwischen den Zentren von 2 Kreisen) - (Summe des Radius von 2 Kreisen)). ** Wenn sich die Kreise überlappen oder enthalten sind, ist sie 0 **. Selbst wenn Sie sich zwischen den beiden Kreisen bewegen, sind Sie keinen kosmischen Strahlen ausgesetzt.
Mit anderen Worten kann die minimale Zeit gefunden werden, um zwischen zwei beliebigen Kreisen dem kosmischen Strahl ausgesetzt zu werden. Der Start- und Endpunkt kann auch als Kreis mit einem Radius von 0 betrachtet werden. Daher ist es unter Berücksichtigung der minimalen Expositionszeit gegenüber kosmischen Strahlen als Entfernung ausreichend, das Problem der kürzesten Entfernung ** vom Startpunkt bis zum Endpunkt in der Grafik von ** $ N + 2 $ Eckpunkten zu lösen. Da der Abstand nicht negativ ist, kann er auch mit der Dyxtra-Methode gelöst werden, und der Berechnungsbetrag beträgt $ O (N \ log {N}) $.
Und ** weil der Abstand ein Bruchteil ist, machen Sie ihn doppelt **, daher sind die folgenden Punkte zu beachten.
(1) Achten Sie auf die ** Typspezifikation für ganze Zahlen **, da double als ll typedef ist.
(2) Um die Aktualisierung des Abstands zwischen Brüchen zu minimieren, ** fügen Sie dem größeren Wert einen Wert hinzu, der geringfügig kleiner als die Toleranz (hier $ 10 ^ {-11} $) ist, und treffen Sie ein Urteil **.
(3) Geben Sie an, dass die Ausgabe in $ 10 $ -Ziffern unter dem Bruch erfolgen soll.
(✳︎) Vergessen Sie nicht die ** INF-Initialisierung ** in der Dyxtra-Methode.
Wir werden die Dyxtra-Methode implementieren und dabei die oben genannten Punkte unterdrücken. Ich habe den Code aus [diesem Artikel] verwendet (https://qiita.com/DaikiSuyama/items/663b3e91fd0cf411dd64).
Einreichung → Link
Dritter Tag
AtCoder Hingabe
diff:1987
Ergebnis: Wechselstrom in ca. 40 Minuten
Erwägung
Betrachten Sie zunächst den Fall, in dem der Durchschnitt 0 oder mehr beträgt ($ \ leftrightarrow $ sum ist 0 oder mehr), indem Sie ** jedes Element von $ k $ ** subtrahieren, unter der Bedingung, dass der Durchschnitt $ k $ oder mehr beträgt. * Sie müssen nicht über die Anzahl der Elemente nachdenken **. Setzen Sie daher zunächst alle Elemente auf $ -k $.
Da es sich um einen kontinuierlichen Teilstring handelt, habe ich zuerst über DP nachgedacht, aber es ist schwierig, weil ich gefragt wurde, wie viele. Wenn Sie hier die ** fortlaufende Unterspalte als Intervall ** betrachten, können Sie sie auf ** reduzieren und die Differenz in der kumulierten Summe ** berücksichtigen. Mit anderen Worten, durch Setzen von $ S [i]: = i + 1 Summe auf das
Im Fall des Problems des Musters von $ S [r] = S [l-1] $ wird es unter Verwendung einer Karte verwaltet, diesmal jedoch von BIT mit dem Bild der Berechnung der Anzahl der Stürze ** implementiert. Mit anderen Worten, wenn Sie die Anzahl von $ S [i] $ in BIT in der Reihenfolge des größten $ i $ (✳︎) in einem bestimmten $ i $ aufzeichnen, wird die Nummer jedes Werts des Elements mit einem größeren Index bereits notiert. Es wird gemacht. Da daher die Bedingung ** $ r> l-1 $ erfüllt ist **, kann die Anzahl der Werte, die $ S [i] $ oder mehr sind, basierend darauf berechnet werden, und sie kann durch BIT in logarithmischen Stunden berechnet werden.
Außerdem muss der Wert von $ S [i] $ groß oder negativ sein, also ** Koordinatenkomprimierung ** (Referenz) ) Und Nummer $ 1 → x $. Außerdem kann $ x $ höchstens $ n + 1 $ sein.
(✳︎)… Es ist einfacher, aus dem kleineren zu implementieren, aber es ist nicht das Wesentliche, deshalb werde ich es nicht erklären.
Einreichung → Link
Recommended Posts