Ich habe ein Problem gefunden, das interessant zu sein scheint, also habe ich versucht, es zu lösen.

Problem

Es gibt $ N $ Karten und $ A_i $ steht auf der $ i $ ten Karte.
Mr. T zieht gleichzeitig $ M $ -Blätter heraus. Wie viele Zahlenpaare sind auf der entfernten Karte geschrieben?
Es wird jedoch nicht zwischen Paaren unterschieden, die gerade getauscht wurden, wie z. B. $ (1,2) $ und $ (2,1) $.

Betrachten Sie beispielsweise den Fall von $ N = 5 $, $ M = 2 $, $ \ {A \} = \ {1,2,2,3,4 \} $. In diesem Fall $ 7 $ von $ (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,4) $ Es gibt ein Paar von.

Ich habe keine Angst mehr vor dem Zählen ~ 35 Auswahlen von Pro-Count-Problemen ~ - Qiita Ich habe einige der Probleme geändert.

Die Person, die diesen Artikel schreibt

Die Person, die diesen Artikel schreibt, hat keine Erfahrung mit wettbewerbsfähiger Programmierung. Ich weiß nicht, wie ich ein wettbewerbsfähiger Profi sein soll, also schauen Sie es sich bitte genau an.

Vorausgesetztes Wissen

Anzahl der Gitterpfade

Betrachten Sie einen solchen gitterartigen Pfad.

Wenn Sie nur nach rechts oder oben gehen können, beträgt die Anzahl der Routen von $ P $ bis $ Q $

{}_{n+m} \mathrm{C} _m

ist.

Berechnen Sie die Anzahl der Routen für jeden Schritt

Aufgrund des oben erwähnten Problems der Anzahl der Gitterrouten beträgt die Anzahl der Routen zu einem bestimmten Punkt $ (p, q) $ $ (p-1, q) $, wobei die horizontale Achse $ p $ und die vertikale Achse $ q $ ist. Und die Anzahl der Routen zu $ (p, q-1) $.

Durch Ausnutzung dieser Eigenschaft wird der Abstand von $ P $ [^ 1] um $ 1 $ erhöht. Wenn Sie das Ende erreicht haben, erhalten Sie den gewünschten Wert. Lassen Sie uns mit dem $ 4 \ times 3 $ -Raster überprüfen.

[^ 1]: Der Abstand hier ist die Länge des nächsten Schnittpunkts vom Schnittpunkt des Gitters als 1.

Es stellt sich heraus, dass die Anzahl der Pfade im $ 4 \ times 3 $ -Raster 35 beträgt. Dieses Ergebnis entspricht $ {} _7 \ mathrm {C} _3 = 35 $.

Verformung des Gitters

Ein solches Raster wird in den folgenden Abschnitten angezeigt. Die Anzahl der Kombinationen ändert sich nicht, nur die vertikale Achse ist geneigt.

Der Hauptthema-Algorithmus

Es gibt $ N $ Karten und $ A_i $ steht auf der $ i $ ten Karte.
Mr. T zieht gleichzeitig $ M $ -Blätter heraus. Wie viele Zahlenpaare sind auf der entfernten Karte geschrieben?
Es wird jedoch nicht zwischen Paaren unterschieden, die gerade getauscht wurden, wie z. B. $ (1,2) $ und $ (2,1) $.

Betrachten Sie den Fall von $ N = 7 $, $ M = 4 $, $ \ {A \} = \ {1,2,2,3,3,3,4 \} $.

Raster erstellen

Erstellen Sie zunächst das folgende Raster.

Schreiben Sie die in $ A $ enthaltenen Zahlen auf die horizontale Achse des Gitters. Wenn dieselbe Nummer enthalten ist, schreiben Sie sie nacheinander. Die durchgezogene schwarze Linie zeigt an, ob die unten angegebenen Zahlen verwendet werden sollen. Nach rechts oben zu gehen bedeutet, diese Nummer zu verwenden, und nach rechts zu gehen bedeutet, diese Nummer nicht zu verwenden.

Zum Beispiel

Die rosa dargestellten Pfade repräsentieren die Auswahl von $ (1, 2, 3, 4) $.

Ähnlich

Bedeutet die Auswahl von $ (2, 2, 3, 3) $.

Doppelte Kombination

auf diese Weise,

Wann

Beide repräsentieren die Auswahl von $ (2, 3, 3, 4) $, und es gibt mehrere Routen für eine Kombination.

Vermeiden Sie doppelte Kombinationen

Ändern Sie die Route so, dass es eine Route für eine Kombination gibt. Wechseln Sie bei der Auswahl einer Nummer zur Route ** Wenn dieselbe Nummer vorhanden ist, wählen Sie alle gleichen Nummern rechts von der ausgewählten Nummer aus **. Auf diese Weise können Sie doppelte Kombinationen entfernen.

Die hellblaue Linie ist die gelöschte Route und die rote Linie ist die hinzugefügte Route. Wenn Sie links $ 2 $ auswählen, wählen Sie auch rechts $ 2 $ aus. Wenn Sie die am weitesten links stehenden $ 3 $ auswählen, wählen Sie die verbleibenden zwei $ 3 $ aus. Wenn Sie die mittleren $ 3 $ auswählen, wählen Sie die rechten $ 3 $ aus.

Folglich sind die einzigen Routen zur Auswahl von $ (2, 3, 3, 4) $ wie folgt.

Anzahl

Zählen Sie nach der erstellten Route.

Durch diese Operation stellt sich heraus, dass die Anzahl der Auswahl von 4 aus $ \ {A \} = \ {1,2,2,3,3,3,4 \} $ $ 11 $ beträgt. Es war.

So wählen Sie doppelte Nummern aus

Achten Sie nun auf den rot dargestellten Teil.

Diese Zahl ist die Summe der orangefarbenen Teile.

In ähnlicher Weise ist der in der folgenden Abbildung rot dargestellte Teil die Summe der von Orange umgebenen Teile.

In einem normalen Raster ist die Anzahl der Routen zum Punkt $ (p, q) $ die Summe aus der Anzahl der Routen zum $ (p-1, q) $ und der Anzahl der Routen zum $ (p, q-1) $. tat.

Wenn es zwei identische Zahlen gibt, beträgt die Anzahl der Routen zu $ (p, q) $ $ (p-2, q) $, $ (p-1, q-1) $, $ (p, q). -2) $ Dies ist die Summe der Anzahl der Routen.

Wenn es drei identische Zahlen gibt, beträgt die Anzahl der Routen zu $ (p, q) $ $ (p-3, q) $, $ (p-2, q-1) $, $ (p-1). , p-2) $, $ (p, q-3) $ Die Anzahl der Routen wird hinzugefügt.

Sie können sehen, dass die Routenkarte wie folgt umgeschrieben werden kann.

Zähle (wieder)

Zählen Sie erneut mit der umgeschriebenen Route.

Bisher haben wir ein konkretes Beispiel für einen Algorithmus gesehen, der $ M $ -Karten aus $ N $ -Karten auswählt, die doppelte Zahlen enthalten.

Algorithmus

Verallgemeinern Sie den obigen Algorithmus.

$ A $ steht für einen Kartensatz
Die Anzahl der Routen zum $ point (p, q) $ wird durch $ route (p, q) $ dargestellt. $ route (0, 0) = 1 $
Die Entfernung vom Ursprung wird durch $ step $ dargestellt. Der Anfangswert von Schritt ist $ 0 $

Wiederholen Sie die folgenden Schritte, bis $ A $ leer ist
Extrahieren Sie alle Arten von Zahlen $ a $ aus $ A $ und löschen Sie sie aus $ A $. Sei $ c $, wie viele $ a $ sind
Fügen Sie $ c $ zu $ step $ hinzu
Für eine ganze Zahl $ (p, q) $, die $ p + q = Schritt \ (0 \ leqq p \ leqq N-M, 0 \ leqq q \ leqq M) $ erfüllt $ route (p, q) = Route (p - c, q) + Route (p - c + 1, q - 1) + Route (p - c + 2, q - 2) + ... + Route (p) -1, q- (c -1)) + Route (p, q - c) $
$ route (N-M, M) $ ist die gewünschte Nummer.

Algorithmusmodifikation

Der obige Algorithmus ist $ M $, wie $ N = 7 $, $ M = 2 $, $ \ {A \} = \ {1,2,2,3,3,3,4 \} $ Es funktioniert nicht, wenn Sie Zahlen mit höherer Überlappung haben (diesmal gibt es 3 $ 3 $). Wenn mehr als $ M $ doppelte Zahlen vorhanden sind, müssen Sie den Grad der Duplizierung im Voraus auf $ M $ reduzieren.

Algorithmusverbesserungen

Sortieren Sie nach dem Grad der Duplizierung von Zahlen

Ordnen Sie die Zahlen nach Duplizierungsgrad. Schreiben Sie die Nummer, die nur einmal ganz links erscheint.

Die Zahl, wenn sie nur einmal erscheint, kann berechnet werden.

(Aus diesem Grund beginnt $ step $ im verknüpften Programm nicht bei $ 0 $.)

Bei einem einfachen Gitter erscheint der Koeffizient, wenn $ (x + y) ^ n $ erweitert wird, auf der diagonalen Linie (Pascals Dreieck / Binomial-Theorem).

Ebenso gibt es Regelmäßigkeit, wenn zwei identische Zahlen erscheinen, aber ich habe sie noch nicht gut verallgemeinert (I). Die Anzahl von zwei erscheint hängt mit dem Koeffizienten von $ (x ^ 2 + x + 1) ^ n $ zusammen. Diese Eigenschaft kann verwendet werden, um den Algorithmus weiter zu verbessern.

Code

Ich habe den obigen Algorithmus in Python (Version 3.7) implementiert. combination.count_uniq_combination_lattice

Ich überprüfe, ob das Programm korrekt ist, indem ich überprüfe, ob es mit dieser einfachen Antwort übereinstimmt. combination. count_uniq_combination_simple

Referenzlink

[Elementary Integer Theory / Pascals Triangle-Wikibooks](https://ja.wikibooks.org/wiki/%E5%88%9D%E7%AD%89%E6%95%B4%E6%95%B0% E8% AB% 96 /% E3% 83% 91% E3% 82% B9% E3% 82% AB% E3% 83% AB% E3% 81% AE% E4% B8% 89% E8% A7% 92% E5 % BD% A2)

Nachwort

Als ich das Problem zum ersten Mal sah, dachte ich: "Ich weiß nicht, wo ich anfangen soll ..." Nachdem ich den Kommentarartikel geschrieben habe, beginne ich zu denken: "Oh, das ist überraschend einfach und in der wettbewerbsorientierten Berufswelt allgemein bekannt." Vielleicht gibt es bereits einen ähnlichen Kommentarartikel, aber ich werde ihn veröffentlichen, weil er gut für meine eigene Organisation war.

[PYTHON] [Competition Pro] Löse die Anzahl der M Karten, die aus N Karten entnommen wurden, mithilfe einer Route [Erklärung in der Abbildung]