Mémo de dévotion AtCoder (11/12)
C'est un mémo de dévotion dans AtCoder. Je suis désolé qu'il y ait un mélange de tons et de tons.
AGC008B - Contiguous Repainting
diff:1821 Résultat: 20 minutes pour examen, 10 minutes pour l'implémentation de base, ∞ minutes pour la suppression du bogue → L'expression lambda de la fonction d'accumulation était incorrecte
Soumission: https://atcoder.jp/contests/agc008/submissions/18058051
Considération
Tout d'abord, considérez ** peindre autant que possible de manière pratique ** (noir pour $ a \ _i \ geqq 0 $, blanc pour $ a \ _i \ <0 $). À ce moment, il semblait que l'humour serait clair même si je l'appliquais correctement, alors j'ai pensé à ** peindre dans l'ordre du bord **. À ce stade, vous pouvez facilement peindre tous les carrés sauf les $ k $ sur les bords, et tous les carrés $ k $ sur les bords peuvent être peints en noir ou en blanc. Par conséquent, j'ai pensé qu'il serait préférable de peindre les carrés $ k $ à l'extrémité gauche de manière pratique et les carrés $ k $ à l'extrémité droite, mais comme dans l'exemple 2, le $ entre ** ** peut être optimal si seuls les k $ carrés ne peuvent pas être peints convenablement. Par conséquent, j'ai pensé que si celles-ci étaient ** généralisées **, les cellules $ k $ continues pourraient être peintes en une seule couleur avec du blanc ou du noir, et les autres parties pourraient être peintes de manière pratique. À ce stade, je l'ai résolu en ne montrant que la suffisance, mais si je me calme, en écrasant à la fin, des cellules continues $ k $ d'une couleur apparaîtront, donc je peux également montrer ** la nécessité **. Par conséquent, si vous implémentez simplement cela en utilisant la somme cumulée, ce sera comme suit si vous l'écrivez dans un diagramme.
À ce stade, je viens de l'implémenter, mais j'ai fait une erreur ** car j'ai utilisé une expression lambda pour la fonction transmise à la fonction ** accumulate. Je voudrais ** passer des itérables prétraités à la fonction d'accumulation **.
En outre, il semble être une idée typique d'inverser l'opération ** dans le problème de l'écrasement. C'est vrai, et l'écrasement est une opération destructrice, alors qu'elle peut être rendue non destructive en l'inversant **, ce qui est pratique. Je pense que cela est similaire au fait qu'il est pratique de le considérer comme l'ordre inverse lorsque l'on tranchant dans un problème de type Union Find.
Réflexion
** J'ai fait une erreur parce que j'essayais de garder le code concis **, comme dans le numéro précédent ** Ne sautez pas l'implémentation ** (apprendre ...)
DDPC2020 Qualifying D --Digit Sum Replace
diff:1650 Résultat: discussion: environ 25 minutes, mise en œuvre: aucune, AC Soumission: https://atcoder.jp/contests/ddcc2020-qual/submissions/18059365
Considération
Au début, je me demandais ce qu'il adviendrait de la combinaison de nombres qui serait le minimum après avoir mené une expérience, mais je pensais que ce serait difficile à simuler honnêtement car le nombre est grand.
Ensuite, en me concentrant sur les opérations, j'ai remarqué qu'elles peuvent être divisées en ** (1) opérations qui réduisent le nombre de chiffres et (2) opérations qui ne réduisent pas le nombre de chiffres **. A ce moment, j'ai remarqué que dans le cas de (1), le nombre de chiffres est seulement réduit et la somme des nombres ne change pas **, et dans le cas de (2), le nombre de chiffres n'est pas réduit mais la somme des nombres est uniformément réduite de 9.
Ici, en d'autres termes, la condition finale doit être reformulée pour correspondre aux opérations de ① et ②, et on peut voir que le nombre de chiffres doit être un chiffre et la somme des nombres doit être de 9 ou moins. J'ai également remarqué que les opérations ** ① et ② sont indépendantes l'une de l'autre et n'interfèrent pas l'une avec l'autre **, de sorte que le nombre de fois est ** uniquement déterminé à partir du nombre original de chiffres et de la somme des nombres originaux, respectivement. Ici, le premier peut être facilement obtenu par (le nombre de chiffres d'origine) -1, mais le second ne l'est pas (le quotient de la somme d'origine des nombres divisée par 9), et lorsque le reste après la division par 9 est égal à 0, c'est à partir de cette valeur. Il faut -1. Par conséquent, le nombre maximum de tours est la somme du nombre d'opérations (1) et (2).
✳︎ Somme des nombres… Nombre total de chaque chiffre
Réflexion
Il m'a fallu un certain temps pour remarquer le bâillon, et pendant un moment quand je l'ai remarqué, ce type est difficile, mais ** dois-je faire attention à la quantité de changement en fonctionnement **?
diff:1564 Résultat: discussion + mise en œuvre: 15 minutes, 15 minutes pour fixer la solution de mensonge, AC Soumission: https://atcoder.jp/contests/agc002/submissions/18058456
Considération
Tout d'abord, plus vous coupez, plus la corde est courte, donc ** je veux laisser une corde aussi longue que possible dans le dos **. De plus, couper le nœud intérieur ne le rend pas pratique, alors ** coupez le nœud final **.
En d'autres termes, je pensais que cela pouvait être fait par la méthode gourmande de couper la plus courte des deux cordes à la fin, mais c'est la corde à couper quand ** les longueurs des cordes sont les mêmes ** La réponse change avec cette méthode, ce qui est difficile. Par exemple, les cas suivants existent en tant que cas d'angle. (J'ai remarqué plus tard que cette méthode laisse la corde la plus longue d'un côté, mais ce n'est pas la meilleure façon de la couper si le côté de la corde est court ...)
Cependant, en réfléchissant à cette considération, ** couper à partir de l'extrémité ne laisse que deux cordes , et si la longueur de cette corde est de $ L $ ou plus, c'est avant cela. J'ai également remarqué que la longueur de la corde est toujours supérieure à $ L $. De plus, les deux cordes qui restent à la fin sont côte à côte même dans l'état initial, donc si vous recherchez toutes les paires de cordes adjacentes (rue $ N-1 $) pour voir s'il y a plus de $ L $ Est bon. ( Faites attention à l'état final! **)
Réflexion
Impressions: je l'ai implémentée parce que je pensais que ce serait une méthode de solution de mensonge, mais quand j'ai approfondi ma réflexion, j'ai pu AC, ** Il est important de penser complètement sans le jeter **!
Recommended Posts