[PYTHON] Record de dévotion professionnelle compétitif du 1er au 3e jour (10 / 14,15,17)
Je publierai un article pour enregistrer la critique d'Arimoto (en se concentrant sur le problème de l'article de M. Kencho) et la dévotion d'AtCoder. Je veux faire de mon mieux pendant au moins un mois. Aussi, je vais simplement mettre un lien dans le code, car cela peut mettre beaucoup de problèmes dans un article.
Premier jour
Dévotion d'Arimoto
J'ai également résolu les fléchettes de JOI, AGC033-A, mais je vais l'omettre cette fois car c'est facile.
ARC037B - Test de base
** $ N $ Graphe concaténé sans sommets fermés $ \ leftrightarrow $$ N $ Top Tree $ \ leftrightarrow $$ N $ Graphique avec $ N-1 $ arêtes reliées par des sommets **
J'oublie parfois la paraphrase ci-dessus, alors je vais la garder à l'esprit.
Dans ce problème, tout ce que vous avez à faire est de compter les composants de connexion qui forment un arbre, et il vous suffit de décomposer les composants de connexion les uns dans les autres avec UnionFind et de savoir combien de côtés chacun contient.
Soumission → lien
Dévotion AtCoder
diff:1831
Résultat: AC? Au total environ 1,5 heure (je ne connais pas l'heure exacte car je ne touche pas l'ordinateur depuis longtemps)
Considération
Je veux minimiser l'ordre du dictionnaire, donc tout d'abord, je vais réfléchir à la ** manière optimale de réduire les pics **. Initialement $ i \ in [0, n-1] $ est le plus grand pic et le plus petit élément d'index $ k $. En réduisant progressivement ce pic, ** trouvez le plus petit indice avec le plus grand pic **. Alors, $ i \ in [0, k-1] $ devient l'élément avec le plus grand pic et le plus petit index $ l $. Ceci est ** répété récursivement **, donc en trouvant le maximum cumulé (indexé), vous pouvez trouver quelle montagne sera la plus grande au milieu avec $ O (n) $.
La discussion ci-dessus nous a montré comment déplacer l'index maximum, mais nous devons trouver ** combien de fois chaque index apparaît **. À ce stade, considérez la figure ci-dessous (le cercle rouge est l'emplacement de l'index dans lequel vous vous déplacez).
En d'autres termes, le nombre de fois où l'indice d'une montagne $ i $ apparaît (la somme des hauteurs de chaque montagne réduite à la hauteur de la montagne suivante $ j $), donc (le nombre de montagnes supérieur ou égal à la montagne $ i $) $ \ fois $ (Hauteur de la montagne $ i $ -Hauteur de la montagne $ j $) + $ \ sum_ {k} $ {(Hauteur de la montagne $ k $ inférieure à la montagne $ i $ et supérieure à la montagne $ j $) - ( Mountain $ j $ height)} est la réponse. Cela peut être considéré comme $ O (n) $ en ** organisant les montagnes par ordre croissant et en enregistrant le nombre de montagnes d'une hauteur de $ i $ ou plus **.
Par conséquent, la réponse est d'enregistrer le nombre de fois dans le tableau qui stocke le nombre de fois où chaque index apparaît et enfin de les afficher tous ensemble. De plus, le goulot d'étranglement est le tri et le montant total du calcul est de $ O (n \ log {n}) $.
Soumission → lien
le 2ème jour
Dévotion AtCoder
diff:1740
Résultat: AC en environ 20 minutes (mais Esper)
Considération
Je l'ai résolu par intuition, mais il semble que la réponse était correcte. Cependant, j'ai tendance à frapper avec BIT récemment, donc j'aimerais pouvoir le résoudre avec la solution $ O (N) $.
J'ai remarqué que ** l'opération est réversible ** (✳︎). De plus, comme il est réversible et ne peut être unifié qu'en $ A $ ou $ B $, j'ai décidé de ** unifier n'importe quel caractère en $ B $ ** ici. Ensuite, toute chaîne de caractères peut être transformée en l'un des (chaîne de caractères vide, $ B, BB $). Il est également nécessaire de prouver s'il peut être converti entre ** (chaîne de caractères vide, $ B, BB $) **, soit [éditorial](https://img.atcoder.jp/arc071/editorial. Il ne peut pas être transformé comme indiqué en pdf).
De plus, s'il est unifié à $ B $, lequel de (chaîne de caractères vide, $ B, BB $) sera déterminé par le reste de la division de la longueur de la chaîne de caractères par 3. Autrement dit, ** $ (xs \ fois 2 + xt), où le nombre de $ A et B $ dans la chaîne de caractères continue partielle sélectionnée de $ S et T $ est respectivement $ (xs, ys) et (xt, yt) $. Si % 2 = (ys \ times 2 + yt) % 2 $ tient, la même chaîne ** peut être créée. Par conséquent, si la somme cumulée ** est tirée du nombre de ** $ A, B $, le nombre de $ A, B $ dans une certaine section peut être calculé par $ O (1) $. Par conséquent, vous pouvez répondre à des requêtes jusqu'à 10 $ ^ 5 $ à grande vitesse.
Pendant le concours, j'ai mis 1 $ pour $ A $ dans chaque index et 0 pour $ B $. ** Sauvegardez les informations de $ S et T $ en BIT **, et quand une requête arrive, la somme est $ A $. Je cherchais le nombre de, mais la somme cumulée est plus simple et plus rapide à mettre en œuvre.
(✳︎)… J'ai réussi à faire quelque chose pendant le concours, mais je voulais le résoudre après l'avoir prouvé correctement.
Soumission → lien
diff:1831
Résultat: AC en environ une heure (crachant beaucoup de pena)
Considération
C'était un problème pour lequel je n'étais pas très doué parce que c'était sur un système de coordonnées bidimensionnel, mais je l'ai résolu. Je voudrais profiter de cette occasion pour dissiper mes faiblesses.
Tout d'abord, ** dessinez un diagramme ** et réfléchissez-y ** le temps minimum pour être exposé aux rayons cosmiques entre deux cercles est ** lorsque vous vous déplacez sur la ligne reliant les centres * *est. En d'autres termes, le temps d'exposition aux rayons cosmiques lors d'un déplacement entre deux cercles est max (0, (distance entre les centres de 2 cercles) - (somme des rayons de 2 cercles)). ** Si les cercles se chevauchent ou sont inclus, ce sera 0 **, donc même si vous vous déplacez entre les deux cercles, vous ne serez pas exposé aux rayons cosmiques.
En d'autres termes, le temps minimum pour être exposé au rayon cosmique entre deux cercles peut être trouvé. En outre, le point de départ et le point final peuvent être considérés comme un cercle avec un rayon de 0. Par conséquent, en considérant le temps minimum d'exposition aux rayons cosmiques comme la distance, il suffit de résoudre le problème de distance la plus courte ** du point de départ au point final dans le graphique des sommets ** $ N + 2 $. De plus, comme la distance n'est pas négative, elle peut être résolue en utilisant la méthode Dyxtra, et le montant du calcul est $ O (N \ log {N}) $.
Et ** parce que la distance est une fraction, faites-la doubler **, il y a donc les points suivants à faire attention.
(1) Faites attention à la ** spécification de type pour les entiers ** car double est typedef comme ll.
(2) Pour minimiser la mise à jour de la distance entre les fractions, ** ajoutez une valeur légèrement inférieure à la tolérance (ici, $ 10 ^ {-11} $) à la plus grande et faites un jugement **.
(3) Spécifiez la sortie en chiffres de 10 $ sous la fraction.
(✳︎) N'oubliez pas ** Initialisation INF ** dans la méthode Dyxtra.
Nous implémenterons la méthode Dyxtra tout en supprimant les points ci-dessus à prendre en compte. J'ai utilisé le code de cet article.
Soumission → lien
Troisième jour
Dévotion AtCoder
diff:1987
Résultat: AC en 40 minutes environ
Considération
Tout d'abord, considérons le cas où la moyenne est de 0 ou plus ($ \ leftrightarrow $ sum est de 0 ou plus) en ** soustrayant tout élément avec $ k $ ** à la condition que la moyenne soit de $ k $ ou plus. * * Vous n'avez pas à penser au nombre d'éléments **. Par conséquent, définissez d'abord tous les éléments sur $ -k $.
Aussi, comme il s'agit d'une sous-chaîne continue, j'ai d'abord pensé à DP, mais c'est difficile car on m'a demandé combien. Ici, si vous regardez la ** sous-colonne continue comme l'intervalle **, vous pouvez la réduire à ** considérer la différence dans la somme cumulée **. En d'autres termes, en définissant $ S [i]: = i + 1 somme jusqu'au $ ème élément ($ S [i] = -k $ quand $ i = 0 $), un certain intervalle $ [l, r ] La condition que la somme de $ soit égale ou supérieure à 0 est $ S [r] -S [l-1] \ geqq 0 \ leftrightarrow S [r] \ geqq S [l-1] $.
Dans le cas du problème du motif de $ S [r] = S [l-1] $, il est géré à l'aide de map, mais cette fois il est implémenté par BIT avec l'image du calcul du nombre de chutes **. En d'autres termes, si vous enregistrez le nombre de $ S [i] $ dans BIT dans l'ordre du plus grand $ i $ (✳︎), dans un certain $ i $, le numéro de chaque valeur de l'élément avec un index plus grand est déjà noté. Ça sera fait. Par conséquent, puisque la condition ** $ r> l-1 $ est satisfaite **, le nombre de valeurs $ S [i] $ ou plus peut être calculé par BIT en heures logarithmiques.
De plus, la valeur de $ S [i] $ doit être grande ou négative, donc ** compression de coordonnées ** (reference) ) Et le nombre $ 1 → x $. De plus, $ x $ ne peut être que $ n + 1 $ au maximum.
(✳︎)… Il est plus facile de mettre en œuvre à partir du plus petit, mais comme ce n'est pas essentiel, les explications etc. sont omises.
Soumission → lien
Recommended Posts