[PYTHON] [Competition Pro] Un algorithme qui retourne la partie en sandwich pour la rendre ● ○ ●● ○○○ ● → ○○○○○○○○ (Inversion de cellule JSC2019-C) [Explication sur la figure]
Je n'ai plus peur de compter ~ 35 problèmes de comptage de pro de la concurrence ~ --Qiita Un des problèmes présentés dans l'article semblait intéressant, donc je l'ai résolu. Je l'ai essayé. En passant, je l'ai écrit en pensant tout en résolvant le problème, donc je ne suis pas arrivé à la solution dans les plus brefs délais. Si vous souhaitez voir la solution la plus courte et la meilleure, veuillez consulter la réponse modèle liée à la page de phrase de question.
problème
Les cellules $ 2N $ sont alignées sur une ligne à gauche et à droite, et reçoivent une chaîne $ S $ de longueur $ 2N $ qui représente la couleur de chaque cellule. La couleur de la $ i $ ème cellule à partir de la gauche est noire lorsque la lettre $ i $ de $ S $ est "B" et blanche lorsqu'elle est "W". Vous choisissez différents carrés de 2 $ et effectuez l'opération de retournement des couleurs de ces carrés et des carrés entre eux exactement $ N $ fois. Ici, inverser la couleur d'un carré signifie le rendre blanc si la couleur du carré est noir, et le rendre noir s'il est blanc. Cependant, vous ne pouvez pas sélectionner la même cellule plus de 2 $ par opération. Cela signifie que chaque cellule sera choisie exactement $ 1 $. Trouvez le reste en divisant 10 $ ^ 9 + 7 $ par le nombre de façons dont vous pouvez rendre toutes les cellules blanches après des opérations $ N $. Ici, la différence entre les méthodes $ 2 $ qui remplissent les conditions est que la méthode $ 1 $ second est la paire $ 2 $ de cellules sélectionnées de la $ i $ ème manière. $ 2 $ Cela signifie qu'il existe $ i (1 \ leq i \ leq N) $ avec différentes paires de carrés $ 2 $ sélectionnées par la deuxième méthode.
Touchons un peu
B est représenté par ● ou noir, et W est représenté par ○ ou blanc. Le mot «rotation» est utilisé pour «renversement». Imaginez Othello. Il y a un exemple de ● ○ ●● ○○○ ● dans l'énoncé du problème, résolvons-le.
Pour commencer, retournons selon la procédure.
Cela n'est pas devenu ○○○○○○○○.
Essayons à nouveau.
C'est maintenant ○○○○○○○○.
Décrivons la procédure de retournement, en associant les positions dans l'ordre du retournement. Dans l'exemple ci-dessus, ce serait $ (2,8) (1,4) (6,7) (3,5) $. Appelons un tel arrangement de paires dans l'ordre de retournement ** colonne d'inversion **.
L'ordre de retournement n'a pas d'importance
Si vous essayez plusieurs choses, vous constaterez que si les paires de retournement sont les mêmes, l'ordre de retournement n'a rien à voir avec le modèle de masse final.
Par exemple, $ (2,8) (1,4) (6,7) (3,5) $ et $ (1,4) (2,8) (3,5) (6,7) $ ont le même résultat. Sera.
Dans ce qui suit, le motif carré est appelé ** motif noir et blanc **.
Normaliser la colonne inversée
Même si les paires de colonnes inversées sont échangées, le motif final (motif noir et blanc) est le même, définissez donc une règle pour le rendre unique. Appelons cette opération ** normalisation de colonne inversée **.
- Écrivez le plus petit nombre à gauche
- Disposez les paires dans l'ordre croissant des nombres sur la gauche
Si $ (2,8) (1,4) (6,7) (3,5) $ est arrangé selon les règles ci-dessus, $ (1,4) (2,8) (3,5) (6 , 7) $.
Aussi, appelons celui qui extrait uniquement le côté gauche de la colonne d'inversion normalisée ($ \ {1,2,3,6 \} $ dans ce cas) ** colonne d'inversion gauche **.
Pensez à l'inverse
Eh bien, je ne sais toujours pas comment le retourner pour que tout ● ○ ●● ○○○ ● soit blanc.
Par conséquent, vérifiez ce qui se passe lorsque tous les carrés blancs (○○○○○○○○) sont retournés selon la procédure, dans la plage où $ N $ est petit.
Il existe une relation opposée entre changer ● ○ ●● ○○○ ● en ○○○○○○○○○ et changer ○○○○○○○○ en ● ○ ●● ○○○ ●. En effet, si vous remplacez ○○○○○○○○ par ● ○ ●● ○○○ ● et que vous le retournez dans la même ligne inversée, il reviendra à ○○○○○○○○.
N=1
Lorsque $ N = 1 $, il y a une façon de le retourner.
N=2
Lorsque $ N = 2 $, il existe 3 façons de le retourner, mais il existe 2 types de motifs en noir et blanc.
N=3
Lorsque $ N = 3 $, il existe 15 façons de le retourner, et il existe 5 types de motifs en noir et blanc.
Découverte des règles
Il y a quelques découvertes jusqu'à présent, alors résumons-les.
En fin de compte, le blanc ou le noir dépend du nombre de lignes tracées
Le nombre de lignes en dessous (ou s'étendant de vous-même) est inversé, de sorte que le nombre de lignes déterminera en fin de compte si la cellule sera blanche ou noire. Blanc lorsque le nombre de lignes est pair, noir lorsque le nombre est impair.
Les deux extrémités du motif noir et blanc sont noires
Les deux extrémités sont noires parce qu'elles sont retournées lorsque vous vous sélectionnez et ne sont pas prises en sandwich entre d'autres carrés.
Lorsqu'il est divisé en grappes, les deux extrémités de chaque grappe sont noires
La division en groupes signifie que l'inversion est terminée dans une certaine section, comme indiqué ci-dessous.
Lorsqu'ils sont divisés en groupes, les deux extrémités de chaque groupe sont noires.
En regardant la colonne inversée de chaque modèle, les nombres dans la colonne inversée de gauche sont communs
Avec $ N = 3 $, rassemblez les colonnes de swap pour chaque motif noir et blanc.
Si vous regroupez les colonnes inversées pour chaque motif noir et blanc, vous remarquerez que les côtés gauche et droit de la colonne inversée sont les mêmes pour chaque motif noir et blanc. Par exemple, dans une colonne inversée qui change ○○○○○○ en ● ○○○○ ●, $ \ {1,2,4 \} $ apparaît sur le côté gauche de la paire et $ \ {3, sur le côté droit. 5,6 \} $ apparaîtra.
Le résultat est le même même si le chevauchement (L1, R1) (L2, R2) est remplacé par (L1, R2) (L2, R1).
Les motifs noir et blanc des deux colonnes inversées du bas $ (L_1, R_1) (L_2, R_2) $ et $ (L_1, R_2) (L_2, R_1) $ sont identiques. En effet, le nombre de lignes sous le carré ne change pas.
Il n'y a qu'une seule colonne inversée dans chaque motif noir et blanc où les lignes ne se croisent pas
Les lignes croisées font référence aux situations suivantes:
Lors de la connexion de paires retournées avec une ligne, il n'y a qu'une seule colonne inversée pour chaque motif noir et blanc où les lignes ne se croisent pas. Si $ N = 3 $, il s'agit de la colonne inversée respectivement.
Appelons les colonnes inversées où les lignes ne se croisent pas ** colonnes inversées sans intersection **.
Dans une colonne d'inversion sans intersection, les paires d'inversion ont la même couleur
Dans la ligne inversée sans intersection, celles avec des lignes connectées auront la même couleur une fois l'opération terminée. Dans une rangée de permutation où les lignes ne se coupent pas, la paire inversée est soit entourée ou séparée des autres paires, de sorte qu'elle se retourne en même temps ou ne se retourne pas en même temps.
Trouvez une paire l'une à côté de l'autre
Dans une colonne inversée sans intersection, il existe au moins une paire de valeurs adjacentes. La paire a la même couleur dans le motif noir et blanc. En regardant les carrés de la gauche, si les couleurs sont différentes, ce ne sont pas une paire de voisins.
Mettez-le dans la pile et trouvez la paire
Lorsque je regardais vaguement la liste des colonnes inversées qui ne se croisaient pas, cela semblait correspondre aux parenthèses de la formule.
Utilisez des piles pour créer de telles correspondances.
Tout d'abord, trouvez une paire l'une à côté de l'autre. Puisqu'ils sont côte à côte, les valeurs sont continues. Empilez-les jusqu'à ce que vous trouviez une série de couleurs.
Prenons l'exemple de ● ○ ●● ○○○ ●.
C'est l'état initial.
Mettez le premier ● sur la pile.
Le deuxième cercle est d'une couleur différente du premier, alors mettez-le dans la pile.
La troisième ● est d'une couleur différente de la seconde, alors mettez-la dans la pile.
Le 4ème ● est de la même couleur que le haut de la pile, alors prenez le haut de la pile et associez-le au 4ème.
Le 5ème cercle est de la même couleur que le haut de la pile, alors prenez le haut de la pile et associez-le au 5ème.
Le 6ème cercle est d'une couleur différente de celle du haut de la pile, alors mettez-le dans la pile.
Le 7ème cercle est de la même couleur que le haut de la pile, alors prenez le haut de la pile et associez-le au 7ème.
Enfin, le 8e ● est de la même couleur que le haut de la pile, alors prenez le haut de la pile et associez-le au 8e.
Jusqu'ici, $ (1,8) (2,5) (3,4) (6,7) $ est une solution pour changer ● ○ ●● ○○○ ● en ○○○○○○○○ Il s'est avéré être. Lorsque vous le vérifiez, il devient sûrement blanc.
Traiter les cas d'exception
Ce qui précède est le cas où la colonne inversée existe, mais regardons l'exception ici.
Le bas de la pile est blanc
À moins que les deux extrémités ne soient noires, elles ne peuvent pas toutes être blanches. En d'autres termes, lorsque vous le mettez dans la pile, le fond doit être noir. Étant donné une entrée avec du blanc en bas, il existe $ 0 $ façons de rendre toutes les cellules blanches.
La pile n'est pas vide lors de la lecture du carré jusqu'à la fin
Si la pile n'est pas vide lorsque vous lisez les cellules jusqu'à la fin, il n'y a aucune combinaison qui donne le modèle donné. Dans ce cas, il existe des moyens $ 0 $ pour rendre toutes les cellules blanches.
Nombre de cas où (L1, R1) (L2, R2) est remplacé par (L1, R2) (L2, R1)
Le remplacement de $ (L_1, R_1) (L_2, R_2) $ par $ (L_1, R_2) (L_2, R_1) $ donne le même résultat. Considérez le nombre de modèles de tels remplacements pour $ (1,8) (2,5) (3,4) (6,7) $.
Mettez $ \ {4, 5, 7, 8 \} $ dans la partie de $ R_1 $ à $ R_4 $, mais comme il y a une restriction de $ L_i <R_i $, commençons par $ R_4 $. ..
$ R_4 $: 7 $ ou 8 $ $ $ R_3 $: Un de 4 $, 5 $, 7 $, 8 $ (mais sans compter le nombre utilisé dans $ R_4 $) $ R_2 $: $ 4 $, $ 5 $, $ 7 $, $ 8 $ (mais sans compter les nombres utilisés dans $ R_4 $, $ R_3 $) $ R_1 $: 1 numéro restant
En calculant cela, $ 2 \ fois 3 \ fois 2 = 12 voies $.
Multipliez par le nombre de flips
Jusqu'à présent, les colonnes inversées ont été normalisées, mais nous voulons distinguer l'ordre d'inversion, donc multipliez par $ N! $.
$ 12 \times 4! = 288 $
Diviser par 10000000007
Enfin, divisez le nombre calculé par 10 $ ^ 9 + 7 $. Dans la programmation réelle, dans le processus de calcul de la combinaison ci-dessus, divisez-la de manière appropriée par 10 $ ^ 9 + 7 $ et faites en sorte que les chiffres ne débordent pas.
$ 288 \bmod (10^9+7) = 288$
La réponse 288 a été dérivée.
Peut être résolu sans pile
J'ai utilisé une pile cette fois, mais elle peut être résolue sans pile. Pour plus de détails, veuillez consulter l'explication du chef de famille.
Code source
J'ai implémenté l'algorithme ci-dessus (amélioré) en Python (version 3.7). (Il est implémenté avant de diviser par 10 $ ^ 9 + 7 $, donc il ne peut gérer que la plage où $ N $ est petit)
Autres défis
Le motif noir et blanc qui apparaît pour chaque $ N $ est $ N = 1 $ et type $ 1 $ $ N = type 2 $ et $ 2 $ $ N = 3 $ et type $ 5 $ J'ai découvert qu'il y en avait. Que se passe-t-il si vous augmentez le nombre à $ N = 6, 7, 8 $?
Épilogue
Je l'ai écrit brièvement, mais il m'a fallu trois jours pour trouver un algorithme après avoir commencé à réfléchir sérieusement au problème. (J'ai vu l'explication car il y avait une partie que je ne comprenais pas à la fin.) Je l'ai résolue beaucoup plus que l'explication du chef de famille, mais j'ai apprécié les différentes découvertes. Quand je pense que les participants au concours résolvent un tel problème en un coup d'œil, je n'ai qu'une impression superficielle que c'est effrayant.
Recommended Posts