[PYTHON] [Competition Pro] Ein Algorithmus, der das Sandwich-Teil umdreht, um es zu erstellen. ● (JSC2019-C Cell Inversion)
Ich habe keine Angst mehr zu zählen ~ 35 Probleme beim Zählen von Wettbewerben ~ - Qiita Eines der in diesem Artikel vorgestellten Probleme schien interessant zu sein, also habe ich es gelöst. Ich versuchte es. Übrigens habe ich es geschrieben, einschließlich des Denkens bei der Lösung des Problems, so dass ich nicht in kürzester Zeit zur Lösung gekommen bin. Wenn Sie die kürzeste und beste Lösung sehen möchten, lesen Sie bitte die Musterantwort, die auf der Seite mit dem Fragensatz verlinkt ist.
Problem
$ 2N $ -Zellen sind links und rechts in einer Reihe angeordnet und erhalten eine Zeichenfolge $ S $ mit der Länge $ 2N $, die die Farbe jeder Zelle darstellt. Die Farbe der $ i $ -ten Zelle von links ist schwarz, wenn der $ i $ -Buchstabe von $ S $ 'B' ist, und weiß, wenn er 'W' ist. Sie wählen verschiedene $ 2 $ -Quadrate aus und drehen die Farben dieser Quadrate und die Quadrate zwischen ihnen genau $ N $ mal um. Invertieren bedeutet hier, die Farbe eines Quadrats weiß zu machen, wenn die Farbe des Quadrats schwarz ist, und es schwarz zu machen, wenn es weiß ist. Sie können jedoch nicht dieselbe Zelle mehr als $ 2 $ durch den Vorgang auswählen. Dies bedeutet, dass jede Zelle genau $ 1 $ mal ausgewählt wird. Finden Sie den Rest, indem Sie $ 10 ^ 9 + 7 $ durch die Anzahl der Möglichkeiten dividieren, mit denen Sie alle Zellen nach $ N $ -Operationen weiß machen können. Hier unterscheidet sich die $ 2 $ -Methode, die die Bedingung erfüllt, von der $ 1 $ zweiten Methode, die für das $ i $ -te Zellenpaar ausgewählt wurde. $ 2 $ Dies bedeutet, dass $ i (1 \ leq i \ leq N) $ mit verschiedenen Paaren von $ 2 $ Quadraten existiert, die mit der zweiten Methode ausgewählt wurden.
Lassen Sie uns ein wenig berühren
B wird durch ● oder schwarz dargestellt und W wird durch ○ oder weiß dargestellt. Das Wort "umdrehen" wird für "Umkehrung" verwendet. Stellen Sie sich Othello vor. Die Problemstellung enthält ein Beispiel für ● ○ ●● ○○○ ● Lassen Sie uns das Problem lösen.
Lassen Sie es uns als Ausgangspunkt entsprechend dem Verfahren umdrehen.
Dies wurde nicht zu ○○○○○○○○○.
Versuchen wir es nochmal.
Dies ist jetzt ○○○○○○○○○.
Beschreiben wir das Verfahren zum Umdrehen, indem wir die Positionen in der Reihenfolge des Umdrehens koppeln. Im obigen Beispiel wären es $ (2,8) (1,4) (6,7) (3,5) $. Nennen wir eine solche Anordnung von Paaren in der Reihenfolge des Umklappens ** Inversionsspalte **.
Die Reihenfolge des Umschlags spielt keine Rolle
Wenn Sie ein paar Dinge ausprobieren, werden Sie feststellen, dass die Flip-Reihenfolge bei gleichen Flip-Paaren nichts mit dem endgültigen Massenmuster zu tun hat.
Zum Beispiel haben $ (2,8) (1,4) (6,7) (3,5) $ und $ (1,4) (2,8) (3,5) (6,7) $ das gleiche Ergebnis. Wird sein.
Im Folgenden wird das quadratische Muster als ** Schwarz-Weiß-Muster ** bezeichnet.
Normalisieren Sie die invertierte Spalte
Selbst wenn die Paare invertierter Spalten ausgetauscht werden, ist das endgültige Muster (Schwarz-Weiß-Muster) dasselbe. Legen Sie daher eine Regel fest, um es eindeutig zu machen. Nennen wir diese Operation ** invertierte Spaltennormalisierung **.
- Schreiben Sie die kleinere Zahl links
- Ordnen Sie die Paare links in aufsteigender Reihenfolge der Zahlen an
Wenn $ (2,8) (1,4) (6,7) (3,5) $ gemäß den obigen Regeln angeordnet ist, ist $ (1,4) (2,8) (3,5) (6 , 7) $.
Nennen wir auch diejenige, die nur die linke Seite der normalisierten Inversionsspalte extrahiert (in diesem Fall $ \ {1,2,3,6 \} $) ** linke Inversionsspalte **.
Denken Sie anders herum
Nun, ich habe immer noch keine Ahnung, wie ich es umdrehen soll, um alles ● ○ ●● ○○○ ● weiß zu machen.
Überprüfen Sie daher, was passiert, wenn alle weißen Quadrate (○○○○○○○○) gemäß dem Verfahren innerhalb des Bereichs umgedreht werden, in dem $ N $ klein ist.
Es besteht eine entgegengesetzte Beziehung zwischen dem Ändern von ● ○ ●● ○○○ ● zu ○○○○○○○○ und dem Ändern von ○○○○○○○ zu ● ○ ●● ○○○. Dies liegt daran, dass, wenn Sie ○○○○○○○○ in ● ○ ●● ○○○ ● ändern und es dann in derselben invertierten Zeile umdrehen, es zu ○○○○○○○○ zurückkehrt.
N=1
Wenn $ N = 1 $ ist, gibt es eine Möglichkeit, es umzudrehen.
N=2
Wenn $ N = 2 $ ist, gibt es drei Möglichkeiten, es umzudrehen, aber es gibt zwei Arten von Schwarz-Weiß-Mustern.
N=3
Wenn $ N = 3 $ ist, gibt es 15 Möglichkeiten, es umzudrehen, und es gibt 5 Schwarz-Weiß-Muster.
Entdeckung von Regeln
Bisher gibt es einige Entdeckungen, also lassen Sie uns sie zusammenfassen.
Letztendlich hängt Weiß oder Schwarz von der Anzahl der Linien ab
Die Anzahl der Zeilen darunter (oder von Ihnen aus) wird umgedreht, sodass die Anzahl der Zeilen letztendlich bestimmt, ob die Zelle weiß oder schwarz ist. Weiß, wenn die Anzahl der Zeilen gerade ist, Schwarz, wenn die Anzahl ungerade ist.
Beide Enden des Schwarz-Weiß-Musters sind schwarz
Beide Enden sind schwarz, da sie bei der Auswahl umgedreht werden und nicht zwischen anderen Quadraten liegen.
Bei der Aufteilung in Cluster sind beide Enden jedes Clusters schwarz
Das Teilen in Cluster bedeutet, dass die Inversion innerhalb eines bestimmten Abschnitts abgeschlossen ist, wie unten gezeigt.
Bei der Aufteilung in Cluster sind beide Enden jedes Clusters schwarz.
In der invertierten Spalte jedes Musters sind die Zahlen in der linken invertierten Spalte üblich
Stellen Sie mit $ N = 3 $ die Swap-Spalten für jedes Schwarzweißmuster zusammen.
Wenn Sie die invertierten Spalten nach Schwarzweißmustern gruppieren, werden Sie feststellen, dass die linke und rechte Seite der invertierten Spalte für jedes Schwarzweißmuster gleich sind. Beispielsweise wird in einer invertierten Spalte, die ○○○○○○ in ● ○○○○ ● ändert, $ \ {1,2,4 \} $ auf der linken Seite des Paares und $ \ {3 auf der rechten Seite angezeigt. 5,6 \} $ wird angezeigt.
Das Ergebnis ist das gleiche, auch wenn die Überlappung (L1, R1) (L2, R2) durch (L1, R2) (L2, R1) ersetzt wird.
Die Schwarz-Weiß-Muster der beiden unteren invertierten Spalten $ (L_1, R_1) (L_2, R_2) $ und $ (L_1, R_2) (L_2, R_1) $ sind gleich. Dies liegt daran, dass sich die Anzahl der Linien unter dem Quadrat nicht ändert.
In jedem Schwarzweißmuster gibt es nur eine umgekehrte Spalte, in der sich die Linien nicht schneiden
Das Überqueren von Linien bezieht sich auf folgende Situationen:
Wenn Sie Paare verbinden, die mit einer Linie umgedreht sind, gibt es nur eine umgekehrte Zeile für jedes Schwarzweißmuster, bei dem sich die Linien nicht schneiden. Wenn $ N = 3 $ ist, ist dies jeweils die invertierte Spalte.
Nennen wir die invertierten Spalten, bei denen sich die Linien nicht schneiden ** nicht schneidende invertierte Spalten **.
In einer sich nicht überschneidenden invertierten Spalte haben die invertierten Paare dieselbe Farbe
In der nicht schneidenden invertierten Zeile haben diejenigen mit verbundenen Linien nach Abschluss des Vorgangs dieselbe Farbe. In einer Swap-Reihe, in der sich die Linien nicht schneiden, ist das Flip-Paar entweder von den anderen Paaren umgeben oder von diesen getrennt, sodass es entweder zur gleichen Zeit oder nicht zur gleichen Zeit kippt.
Finde ein Paar nebeneinander
In einer nicht schneidenden invertierten Spalte gibt es mindestens ein Paar benachbarter Werte. Das Paar hat die gleiche Farbe im Schwarz-Weiß-Muster. Wenn Sie die Quadrate von links betrachten und die Farben unterschiedlich sind, sind sie kein Paar von Nachbarn.
Legen Sie es in den Stapel und finden Sie das Paar
Als ich die Liste der sich nicht überschneidenden invertierten Spalten vage betrachtete, schien sie den Klammern in der Formel zu entsprechen.
Verwenden Sie Stapel, um solche Entsprechungen zu erstellen.
Suchen Sie zuerst ein Paar nebeneinander. Da sie nebeneinander liegen, sind die Werte stetig. Stapeln Sie sie, bis Sie eine Reihe von Farben finden.
Nehmen Sie als Beispiel ● ○ ●● ○○○ ●.
Es ist der Ausgangszustand.
Legen Sie den ersten ● auf den Stapel.
Der zweite Kreis hat eine andere Farbe als der erste. Legen Sie ihn also in den Stapel.
Das dritte ● hat eine andere Farbe als das zweite, also legen Sie es in den Stapel.
Das 4. ● hat die gleiche Farbe wie das obere Ende des Stapels. Nehmen Sie also das obere Ende des Stapels und koppeln Sie es mit dem vierten.
Der 5. Kreis hat dieselbe Farbe wie die Oberseite des Stapels. Nehmen Sie also die Oberseite des Stapels und koppeln Sie ihn mit dem 5. Kreis.
Der 6. Kreis hat eine andere Farbe als die Oberseite des Stapels. Legen Sie ihn also in den Stapel.
Der 7. Kreis hat dieselbe Farbe wie die Oberseite des Stapels. Nehmen Sie also die Oberseite des Stapels und koppeln Sie ihn mit dem 7. Kreis.
Schließlich hat die 8. ● die gleiche Farbe wie die Oberseite des Stapels. Nehmen Sie also die Oberseite des Stapels und koppeln Sie sie mit der 8 ..
Bis zu diesem Punkt ist $ (1,8) (2,5) (3,4) (6,7) $ eine Lösung, um ● ○ ●● ○○○ ● in ○○○○○○○○ zu ändern Es stellte sich heraus. Wenn Sie es tatsächlich überprüfen, wird es sicherlich weiß.
Umgang mit Ausnahmefällen
Das Obige ist der Fall, in dem die invertierte Spalte vorhanden ist, aber schauen wir uns hier die Ausnahme an.
Der Boden des Stapels ist weiß
Wenn nicht beide Enden schwarz sind, können sie nicht alle weiß sein. Mit anderen Worten, wenn Sie es in den Stapel legen, muss der Boden schwarz sein. Bei einer Eingabe mit Weiß am unteren Rand gibt es $ 0 $ Möglichkeiten, alle Zellen weiß zu machen.
Der Stapel ist nicht leer, wenn das Quadrat bis zum Ende gelesen wird
Wenn der Stapel beim Lesen der Zellen bis zum Ende nicht leer ist, gibt es keine Kombination, die das angegebene Muster ergibt. In diesem Fall gibt es $ 0 $ Möglichkeiten, alle Zellen weiß zu machen.
Anzahl der Fälle, in denen (L1, R1) (L2, R2) durch (L1, R2) (L2, R1) ersetzt wird
Das Ersetzen von $ (L_1, R_1) (L_2, R_2) $ durch $ (L_1, R_2) (L_2, R_1) $ ergibt das gleiche Ergebnis. Überlegen Sie, wie viele Muster solcher Ersetzungen für $ (1,8) (2,5) (3,4) (6,7) $ sind.
Setzen Sie $ \ {4, 5, 7, 8 \} $ in den Teil von $ R_1 $ bis $ R_4 $, aber da es eine Einschränkung von $ L_i <R_i $ gibt, beginnen wir mit $ R_4 $. ..
$ R_4 $: $ 7 $ oder $ 8 $ $ R_3 $: Einer von $ 4 $, $ 5 $, $ 7 $, $ 8 $ (jedoch ohne die in $ R_4 $ verwendete Zahl) $ R_2 $: $ 4 $, $ 5 $, $ 7 $, $ 8 $ (jedoch ohne die in $ R_4 $, $ R_3 $ verwendeten Zahlen) $ R_1 $: 1 verbleibende Nummer
Wenn man dies berechnet, ist $ 2 \ mal 3 \ mal 2 = 12 Wege $.
Mit der Anzahl der Flips multiplizieren
Bisher wurden die invertierten Spalten normalisiert, aber wir möchten die Flip-Reihenfolge unterscheiden, also multiplizieren Sie mit $ N! $.
$ 12 \times 4! = 288 $
Teilen Sie durch 10000000007
Teilen Sie schließlich die berechnete Zahl durch $ 10 ^ 9 + 7 $. Teilen Sie bei der eigentlichen Programmierung bei der Berechnung der obigen Kombination diese entsprechend durch $ 10 ^ 9 + 7 $ und legen Sie fest, dass die Ziffern nicht überlaufen.
$ 288 \bmod (10^9+7) = 288$
Die Antwort 288 wurde abgeleitet.
Kann ohne Stapel gelöst werden
Ich habe diesmal einen Stapel verwendet, aber er kann ohne Stapel gelöst werden. Einzelheiten entnehmen Sie bitte der Erklärung der Hauptfamilie.
Quellcode
Ich habe den obigen Algorithmus (verbessert) in Python (Version 3.7) implementiert. (Es wird vor dem Teilen durch $ 10 ^ 9 + 7 $ implementiert, sodass nur der Bereich verarbeitet werden kann, in dem $ N $ klein ist.)
Weitere Herausforderungen
Das Schwarz-Weiß-Muster, das für jedes $ N $ angezeigt wird, ist $ N = 1 $ und $ 1 $ Typ $ N = 2 $ und $ 2 $ Typ $ N = 3 $ und $ 5 $ Typ Ich fand heraus, dass es gibt. Was passiert, wenn Sie die Zahl auf $ N = 6, 7, 8 $ erhöhen?
Nachwort
Ich schrieb es kurz, aber ich brauchte drei Tage, um einen Algorithmus zu entwickeln, nachdem ich ernsthaft über das Problem nachgedacht hatte. (Ich habe die Erklärung gesehen, weil es einen Teil gab, den ich am Ende nicht verstanden habe.) Ich habe ihn viel mehr gelöst als die Erklärung der Oberfamilie, aber ich habe die verschiedenen Entdeckungen genossen. Wenn ich denke, dass die Wettbewerbsteilnehmer ein solches Problem auf einen Blick lösen, bekomme ich nur einen geringen Eindruck, dass es beängstigend ist.
Recommended Posts