[PYTHON] Record de dévotion professionnelle compétitif Jour 4-6 (10 / 18,22,23)
C'est une continuation du record de dévotion. J'étais si tard que je n'ai pas pu passer en revue certains des problèmes. Après tout, en raison de ma personnalité, je devrais le revoir immédiatement ...
Jour 4
Dévotion AtCoder
ARC079E - Decrease (Judge ver.)
diff:1791
Résultat: environ 30 minutes
Considération
J'ai été surpris de trouver la solution que je voulais proposer pour le moment. (Bien qu'il y ait eu une intuition que cela diminuerait de façon exponentielle **.)
Répétez en soustrayant $ N $ de la valeur maximale et en incrémentant les autres de 1. Supposons maintenant que vous sélectionniez ** $ a \ _i $ seulement $ b \ _i $ fois **. À ce stade, si le nombre total de sélections est $ s $, alors $ [\ frac {a \ _i + (s-b \ _i)} {N}] = b \ _i $ est valable. J'ai pensé à transformer cette équation et à la résoudre analytiquement.
Cependant, c'est difficile comme cela est, donc considérant ** au moins le nombre de fois requis **, au moins $ [\ frac {a \ _ i} {N}] $ fois d'opérations pour tout $ a \ _i $ J'ai réalisé que j'avais besoin. J'ai calculé cela pour n'importe quel élément et j'ai pensé qu'il serait insensé de mettre à jour $ a \ _i $, alors je l'ai soumis et AC. Quand je l'ai vérifié, il semble que d'autres personnes qui l'ont résolu ne l'ont pas prouvé, donc je sens qu'il n'y a pas d'autre solution que de le résoudre avec cette intuition. C'est un problème de mauvaise humeur.
Soumission → lien
diff:1831
Résultat: AC en environ 20 minutes (1WA avec un format de sortie incorrect)
Considération
C'est un problème de construction, alors je vais penser à le faire ** commodément. Je sens que le pouvoir ici était attaché par le bacha de Kodofo.
Tout d'abord, considérons un sous-ensemble qui remplit deux conditions (la concentration est $ k $). À ce stade, à partir de la condition 1, le nombre ** d'autres sous-ensembles est au plus de $ k $ **. De plus, s'il existe un ensemble ** dont la densité n'est pas $ k
Par conséquent, la concentration de tout ensemble est $ k $. De plus, les éléments contenus dans l'ensemble de sous-ensembles ont des éléments appariés, de sorte que le nombre de sous-ensembles est $ k + 1 $. Par conséquent, à partir de la condition 1, puisque le nombre total d'éléments inclus dans l'ensemble des sous-ensembles est de 2n $, il est nécessaire de satisfaire ** $ k (k + 1) = 2n $ **.
$ K $ qui satisfait $ k (k + 1) = 2n $ vérifie toutes les fractions de $ 2n $. Et, si vous pensez à la méthode de construction, en pensant que ** elle tient toujours lorsque cette condition est remplie, la condition est remplie dans les cas suivants. Si vous expérimentez en faisant attention à la ** symétrie **, vous y penserez.
En d'autres termes, vous pouvez décider en partant de la composante diagonale (comme) puis en étendant dans l'ordre. En outre, si ce qui précède satisfait toujours la condition de construction peut être montré en considérant les nombres communs entre 1 et 2 à 4, entre 2 et 3 à 4 et entre 3 et 4 dans l'ordre. .. Par conséquent, cela peut être facilement obtenu en mettant simplement en œuvre le fait que les composantes diagonales sont étendues dans l'ordre. C'est un peu lourd à mettre en œuvre, mais consultez le lien de soumission ci-dessous pour plus d'informations.
(✳︎)… Ce domaine peut être compris par intuition lorsqu'on considère la symétrie, mais s'il est verbalisé dans une certaine mesure, il peut y avoir moins d'anxiété.
Soumission → lien
Jour 5
Dévotion AtCoder
diff:1896
Résultat: AC en 20 minutes environ
Considération
** Je suis content d'avoir pu le résoudre tout en maintenant une validité suffisante.
Répétez l'opération pour faire $ A = B $. Tozan réduira $ A $, Gezan réduira $ B $, le premier vise à maximiser le nombre d'opérations, et le second vise à le minimiser. (Cependant, la réponse est 0 lorsque $ A \ _i = B \ _i $ depuis le début.)
Ici, il est important que ** le total de $ A et B $ ne change pas lorsque les deux opérations sont terminées ** (✳︎). Autrement dit, pour $ A \ neq B $, il y a au moins un $ i $ différent qui est $ A \ _i > B \ _i $ et $ A \ _i \ <B \ _i $. Par conséquent, les ** actions optimales à prendre par les deux parties ** sont les suivantes.
Tozan ... Réduisez $ A \ _i $ qui devient $ A \ _i \ leqq B \ _i $ Gezan ... Réduisez $ B \ _i $ qui devient $ A \ _i \ <B \ _i $
De plus, puisque Tozan est le premier joueur, vous pouvez réduire à 0 tout $ A \ _i $ qui devient $ A \ _i \ leqq B \ _i $. ** Gezan devrait réduire $ B \ _i $ en conséquence **. Cependant, même si Tozan fait cela, Gezan ne peut pas définir de $ B \ _i $ pour lequel $ A \ _i \ leqq B \ _i $ vaut 0 ($ \ car $ (✳︎)). Par conséquent, si $ A \ _i $ qui contient $ A \ _i > B \ _i $ peut être réduit à $ A \ _i \ leqq B \ _i $, $ A \ _i $ peut être réduit à 0. $ B \ _i $ doit également être égal à 0. En répétant ceci, ** il reste un ensemble de $ A \ _i, B \ _i $ **, et de (✳︎), $ A \ _i = B \ _i $. Par conséquent, cela peut être le plus petit $ B \ _i $ ** dans lequel ** $ A \ _i > B \ _i $ tient, jusqu'à ce que seul ce $ A \ _i = B \ _i $ reste. Le nombre d'opérations est la réponse que vous souhaitez.
(Diverses preuves sont omises ci-dessus, mais elles peuvent être prouvées en tirant parti de la condition (✳︎).)
Soumission → lien
Jour 6
Dévotion AtCoder
ARC098E - Range Minimum Queries
diff:1978
Résultat: 2WA en 45 minutes (j'ai failli abandonner, mais je suis content d'être coincé)
Considération
Le plus simple est ** de compter $ q $ à partir du plus petit **, mais il existe d'autres cas où il peut être le plus petit. Cette valise d'angle est facile à réaliser.
De plus, comme les éléments à supprimer changent en fonction de l'ordre dans lequel la sous-chaîne continue de longueur $ k $ est sélectionnée, ** il est difficile de se concentrer sur l'opération et de la considérer , j'ai donc essayé de fixer l'une des valeurs minimum et maximum. J'ai pensé ( Le client principal est tombé en faisant attention aux éléments! **). De plus, comme les valeurs minimales sont supprimées dans l'ordre, j'ai pensé à ** fixer les valeurs minimales **.
Par conséquent, je me suis demandé si la valeur minimale serait de $ x $ ou plus. De plus, sous cet élément, il n'est pas possible de sélectionner une sous-colonne continue de longueur $ k $ contenant des éléments inférieurs à $ x $ **, donc si l'index des éléments inférieurs à $ x $ est $ i, j $, alors $ 0 $ Vous ne pouvez sélectionner que des sous-colonnes continues de longueur $ k $ dans ~ $ i-1 $, $ i + 1 $ ~ $ j-1 $, $ j + 1 $ ~ $ n-1 $. De même, lorsqu'il y a plus de $ q $ de sous-colonnes continues pouvant être sélectionnées, les éléments à supprimer par l'opération peuvent être $ q $ du plus petit des éléments sélectionnables. À ce stade, la valeur minimale est $ x $. La valeur maximale ci-dessus est minimisée **.
Par conséquent, appliquez $ x $ dans l'ordre à partir du plus petit élément contenu dans $ a $ (maximum $ N $), et divisez ** $ a $ par des éléments égaux à $ x $ ** pour minimiser la valeur. Vous avez juste à chercher. De plus, le nombre d'opérations pouvant être effectuées diminue de manière monotone car la longueur de la sous-chaîne continue qui peut être sélectionnée est raccourcie en effectuant une division. Donc, si vous ne pouvez pas faire plus de $ q $ opérations, vous n'avez plus à penser à $ x $ et vous cassez (la réponse ne change pas si vous ne cassez pas).
Soumission → lien
diff:1747
Résultat: 5WA sur 1 heure (fait différent en considération et mise en œuvre)
Considération
Ci-dessous, la discussion est indexée 1, mais l'implémentation est indexée 0.
Malgré la recherche d'un bon moyen dans le processus de considération **, l'implémentation était différente et le débogage a été ruiné **.
Puisqu'il s'agit d'un problème de construction, recherchez un étui pratique. De plus, comme vous pouvez facilement le voir (à partir de l'exemple), $ s [n] = 0, s [n-1] = s [1] = 1 $ et tout $ i $ pour $ s [i] = s [ni ] S'il est nécessaire de satisfaire $ et même un n'est pas satisfait, -1 est affiché. Pensez également à construire pour ** montrer que cela est également suffisant **.
Tout d'abord, je pensais au graphe quand $ i = 1,2,3,… $ et $ s [i] = 1 $ dans l'ordre, mais c'était une mauvaise méthode sans atteindre l'abstraction. Ensuite, j'ai pensé que les sommets seraient déterminés en fonction des informations de $ s [i] $ dans l'ordre croissant de ** $ i $ **. Ensuite, j'ai trouvé qu'il semble qu'un graphique satisfaisant le sujet puisse être généré en faisant la figure ci-dessous. (Honnêtement, je pense que c'est ** la seule façon de faire les choses correctement **.)
En d'autres termes, ** si vous voulez verbaliser la figure ci-dessus ** (← n'a pas été fait lors de la résolution ...), en supposant que le dernier 1 de $ S $ est ignoré, ** côté est précédé de chaque caractère Correspond à **, et quand 1 vient, passez au suivant et branchez tandis que 0 vient. De plus, si vous ** enregistrez la source de la branche sous le nom $ now $ **, vous n'avez qu'à connecter ce sommet à partir de $ now $ lorsque vous connectez le sommet suivant. Cependant, lorsque ** 1 arrive, la source de la branche passera au sommet actuellement connecté **, vous devez donc vous rappeler de la mettre à jour.
Soumission → lien
(Re) Soumission → Lien
Recommended Posts