J'ai trouvé un problème qui semble intéressant, alors j'ai essayé de le résoudre.

problème

Il y a des cartes $ N $ et $ A_i $ est écrit sur la carte $ i $ th.
M. T en sort des feuilles de M $ en même temps. Combien de paires de nombres sont inscrites sur la carte retirée?
Cependant, il ne fait pas la distinction entre les paires qui sont juste échangées, telles que $ (1,2) $ et $ (2,1) $.

Par exemple, considérons le cas de $ N = 5 $, $ M = 2 $, $ \ {A \} = \ {1,2,2,3,4 \} $. Dans ce cas, 7 $ de $ (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,4) $ Il y a une paire de.

Je n'ai plus peur de compter ~ 35 sélections de problèmes de comptage de compétition pro ~ --Qiita J'ai partiellement modifié le problème.

La personne qui écrit cet article

La personne qui écrit cet article n'a aucune expérience en programmation compétitive. Je ne sais pas comment être un professionnel compétitif, alors jetez-y un œil.

Connaissances préalables

Nombre de chemins de grille

Considérez un tel chemin en forme de grille.

Si vous ne pouvez aller que vers la droite ou vers le haut, le nombre d'itinéraires de $ P $ à $ Q $ est

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

est.

Calculez le nombre d'itinéraires pour chaque étape

En raison du problème du nombre de chemins de grille mentionné ci-dessus, le nombre de routes vers un certain point $ (p, q) $ est $ (p-1, q) $, où l'axe horizontal est $ p $ et l'axe vertical est $ q $. Et le nombre de routes vers $ (p, q-1) $.

En profitant de cette propriété, la distance de $ P $ [^ 1] est augmentée de $ 1 $. Lorsque vous atteignez la fin, vous obtiendrez la valeur souhaitée. Vérifions avec la grille $ 4 \ times 3 $.

[^ 1]: La distance ici est la longueur de l'intersection la plus proche de l'intersection de la grille comme 1.

Il s'avère que le nombre de chemins dans la grille $ 4 \ times 3 $ est de 35. Ce résultat correspond à $ {} _7 \ mathrm {C} _3 = 35 $.

Déformation du réseau

Une telle grille apparaîtra dans les sections suivantes. Le nombre de combinaisons ne change pas, seul l'axe vertical est incliné.

L'algorithme du sujet principal

Il y a des cartes $ N $ et $ A_i $ est écrit sur la carte $ i $ th.
M. T en sort des feuilles de M $ en même temps. Combien de paires de nombres sont inscrites sur la carte retirée?
Cependant, il ne fait pas la distinction entre les paires qui sont juste échangées, telles que $ (1,2) $ et $ (2,1) $.

Prenons le cas de $ N = 7 $, $ M = 4 $, $ \ {A \} = \ {1,2,2,3,3,3,4 \} $.

Créer une grille

Commencez par créer la grille suivante.

Écrivez les nombres contenus dans $ A $ sur l'axe horizontal de la grille. Si le même nombre est inclus, écrivez-le consécutivement. La ligne noire continue indique s'il faut utiliser les nombres écrits ci-dessous. Aller en haut à droite signifie utiliser ce numéro, et aller sur le côté droit signifie ne pas utiliser ce numéro.

Par exemple

Les chemins indiqués en rose représentent la sélection de $ (1, 2, 3, 4) $.

De même

Signifie de sélectionner $ (2, 2, 3, 3) $.

Combinaison en double

de cette façon,

Quand

Les deux représentent la sélection de $ (2, 3, 3, 4) $, et il existe plusieurs itinéraires pour une combinaison.

Évitez les combinaisons en double

Modifiez l'itinéraire pour qu'il y ait un itinéraire pour une combinaison. Lors de la sélection d'un numéro, passez à l'itinéraire ** S'il y a le même numéro, sélectionnez tous les mêmes numéros à droite du numéro sélectionné **. Cela vous permet d'éliminer les combinaisons en double.

La ligne bleu clair est la route supprimée et la ligne rouge est la route ajoutée. Si vous sélectionnez 2 $ sur la gauche, sélectionnez également 2 $ sur la droite. De même, si vous sélectionnez les 3 $ les plus à gauche, sélectionnez les deux $ 3 $ restants, et si vous sélectionnez les 3 $ du milieu, sélectionnez les 3 $ de droite.

En conséquence, les seuls itinéraires pour sélectionner $ (2, 3, 3, 4) $ sont les suivants.

Compter

Comptez par l'itinéraire créé.

Par cette opération, il s'avère que le nombre de sélection de 4 parmi $ \ {A \} = \ {1,2,2,3,3,3,4 \} $ est de 11 $. C'était.

Comment sélectionner des numéros en double

Maintenant, faites attention à la partie représentée en rouge.

Ce nombre est la somme des parties encadrées en orange.

De même, la partie représentée en rouge dans la figure ci-dessous est la somme des parties entourées d'orange.

Dans une grille normale, le nombre de routes vers le point $ (p, q) $ est la somme du nombre de routes vers $ (p-1, q) $ et le nombre de routes vers $ (p, q-1) $. fait.

De même, s'il y a deux nombres identiques, le nombre de routes vers $ (p, q) $ est $ (p-2, q) $, $ (p-1, q-1) $, $ (p, q). -2) $ C'est la somme du nombre de routes.

De même, s'il y a trois nombres identiques, le nombre de routes vers $ (p, q) $ est $ (p-3, q) $, $ (p-2, q-1) $, $ (p-1). , p-2) $, $ (p, q-3) $ Le nombre de routes est ajouté.

Vous pouvez voir que la carte d'itinéraire peut être réécrite comme suit.

Recompter)

Comptez à nouveau avec l'itinéraire réécrit.

Jusqu'à présent, nous avons vu un exemple concret d'algorithme qui sélectionne des cartes $ M $ à partir de cartes $ N $ contenant des nombres en double.

algorithme

Généraliser l'algorithme ci-dessus.

$ A $ représente un jeu de cartes
Le nombre de routes vers le $ point (p, q) $ est représenté par $ route (p, q) $. $ route (0, 0) = 1 $ --La distance depuis l'origine est représentée par $ step $. La valeur initiale de l'étape est 0 $ $

Répétez ce qui suit jusqu'à ce que $ A $ soit vide
Extrayez tout un type de nombre $ a $ de $ A $ et supprimez-le de $ A $. Soit $ c $ le nombre de $ a $
Ajoutez $ c $ à $ step $
Pour un entier $ (p, q) $ qui satisfait $ p + q = step \ (0 \ leqq p \ leqq N-M, 0 \ leqq q \ leqq M) $ $ 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) $ est le numéro souhaité.

Modification d'algorithme

L'algorithme ci-dessus est $ M $, tel que $ N = 7 $, $ M = 2 $, $ \ {A \} = \ {1,2,2,3,3,3,4 \} $ Cela ne fonctionne pas si vous avez des numéros avec un chevauchement plus élevé (cette fois, il y a 3 $ 3 $). S'il y a plus de $ M $ de numéros en double, vous devez réduire le degré de duplication à $ M $ à l'avance.

Améliorations de l'algorithme

Trier par degré de duplication des nombres

Organisez les nombres par degré de duplication. Écrivez le numéro qui n'apparaît qu'une seule fois à l'extrême gauche.

Le nombre lorsqu'il n'apparaît qu'une seule fois peut être calculé.

(C'est pourquoi $ step $ ne commence pas à $ 0 $ dans le programme lié.)

Dans le cas d'un treillis simple, le coefficient lorsque $ (x + y) ^ n $ est développé apparaît sur la ligne diagonale (triangle de Pascal / théorème binomial).

De même, il y a régularité lorsque deux nombres identiques apparaissent, mais je ne les ai pas encore bien généralisés (I). Le nombre de deux apparaissant est lié au coefficient de $ (x ^ 2 + x + 1) ^ n $. Cette propriété peut être utilisée pour améliorer encore l'algorithme.

code

J'ai implémenté l'algorithme ci-dessus en Python (version 3.7). combination.count_uniq_combination_lattice

Je vérifie si le programme est correct en vérifiant s'il correspond à cette réponse simple. combination. count_uniq_combination_simple

Lien de référence

[Théorie élémentaire des nombres entiers / Triangle de Pascal-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)

Épilogue

Quand j'ai vu le problème pour la première fois, j'ai pensé: "Je ne sais pas par où commencer ..." Maintenant que j'ai écrit l'article de commentaire, je commence à penser: "Oh, c'est étonnamment simple, et cela peut être de notoriété publique dans le monde professionnel compétitif." Il existe peut-être déjà un article de commentaire similaire, mais je le publierai car c'était bon pour ma propre organisation.

[PYTHON] [Compétition Pro] Résolvez le nombre de M cartes extraites de N cartes en utilisant un itinéraire [Explication sur la figure]