Je vais reprendre le mémo de dévotion. Je vais le résumer de manière plus fragile que les articles habituels, et je le passerai en revue dès que je le résoudrai.
diff:1911 Résultat: AC pour un total d'environ 2 heures
Soumission: https://atcoder.jp/contests/agc014/submissions/18039440
Tout d'abord, déplacez → ouvrez → déplacez →…, donc s'il y a une pièce qui n'est pas encore disponible, vous ne pourrez pas accéder à cette pièce, ce qui pose problème. Par conséquent, j'ai pensé qu'il valait mieux gérer ** le nombre de mouvements et le nombre minimum de chambres vacantes , mais ce n'est pas dénombrable et il semble que cela demandera beaucoup de calcul. Ici, s'il s'agit d'un motif de open → move → open →… ( pensez à le laisser tomber dans un cas simple! **), vous pouvez voir qu'il suffit de sélectionner la pièce à l'extrémité la plus proche ($ \ car $ cette pièce). Parce que vous pouvez ouvrir toutes les pièces fermées jusqu'à ce que vous y arriviez).
On voit donc qu'il suffit de considérer ** séparer uniquement le premier mouvement **. En d'autres termes, puisque vous ne pouvez tracer que les pièces qui ne sont pas ouvertes au premier coup, considérez BFS ** qui trace uniquement les pièces qui sont ouvertes et dont la profondeur est inférieure à $ k $. Ensuite, dans le schéma ouvert → déplacer → ouvrir →… après cela, il suffit de trouver le chemin le plus court de la pièce qui peut être tracé par BFS jusqu'à la pièce finale (quatre directions), et ceil (longueur de l'itinéraire le plus court). / k) +1 est la réponse. Par conséquent, la valeur minimale dans la pièce qui remplit les conditions est la réponse.
Ce n'était pas mal de penser qu'il serait bon d'avoir deux informations, ** le nombre de mouvements et le nombre minimum de chambres vacantes **, mais il a fallu du temps pour arriver à l'idée de ** concevoir le mode opératoire **. Ce n'était pas bon d'aller trop loin. Je veux garder à l'esprit l'attitude consistant à examiner les problèmes sous plusieurs angles, ce qui semble indiquer que le nombre de problèmes à résoudre est faible.
diff:2803 Résultat: AC en 30 minutes pour examen + implémentation, 50 minutes pour suppression de bogue Soumission: https://atcoder.jp/contests/agc012/submissions/18040503
** Focus sur des boules de même couleur $ c $ **, la combinaison des deux boules doit être inférieure à $ x $. A ce moment, en ** sélectionnant l'une des deux balles avec la couleur $ c $ et le poids le plus petit **, l'autre balle peut être rendue aussi lourde que possible. De plus, tous les arrangements peuvent être réalisés entre des balles pesant moins de $ x $ avec la plus petite boule de couleur $ c $ ($ \ car $ ** balle de poids minimum). Vous devez toujours sélectionner **). … ①
De même, si vous regardez également ** différentes balles **, vous pouvez sélectionner la balle avec le poids le plus petit parmi toutes les balles colorées ** (la couleur est $ c $) comme l'une des balles. Peut être discuté de la même manière que. Cependant, comme l'autre balle, vous ne pouvez sélectionner qu'une balle dont la couleur est différente de $ c $ **. Par conséquent, on peut voir que pour les balles de couleur $ c $ **, la balle avec le poids le plus petit parmi celles avec une couleur autre que $ c $ doit être sélectionnée. … ②
À partir de ce qui précède, en ** considérant un système d'ensembles de balles dont les positions peuvent être échangées **, les positions peuvent être échangées entre tous les éléments de l'ensemble principal. Par conséquent, l'opération doit être divisée dans l'ordre de ① et ② pour effectuer unite dans l'arborescence Union Find. De plus, lorsqu'il y a un système d'ensembles premiers, la disposition des boules dans un ensemble premier de taille $ l $ est $ l! $. De plus, puisque vous voulez trouver la séquence de couleurs de boule **, vous devez ** diviser les boules de couleurs qui se chevauchent par le degré de chevauchement **. Ici, le degré de duplication est défini comme $ l ^ {'}! $ Si le nombre de boules d'une certaine couleur $ c ^ {'} $ est $ l ^ {'} $.
Pour mettre en œuvre ce qui précède, la structure de données suivante et autres doivent être préparées.
colors[i]:=Index i couleur de la balle
color[i]:=De la balle qui devient couleur je(poids,indice)Ensemble commandé qui stocke
weight:=(poids,indice)Ensemble commandé qui stocke
Dans (1), regardez $ color [i] $ dans l'ordre et regardez les balles qui peuvent être combinées avec le poids minimum dans l'ordre de la balle avec le plus petit poids. Dans (2), regardez $ weight $ dans l'ordre, et regardez les boules qui sont différentes de la plus petite couleur de boule $ c $ de la même manière que dans (1), puis regardez les boules avec une couleur qui devient $ c $ de la même manière que dans (1). Jette un coup d'oeil. Voir le code soumis pour plus de détails.
La discussion a fonctionné, mais je ne savais pas que ** je faisais quelque chose de différent entre la discussion et la mise en œuvre **. C'est un modèle auquel il est facile de devenir accro, donc je veux en être particulièrement conscient lors de la correction de bugs.
Tenka1 Programmer Contest 2017 D - IntegerotS
diff:1794 Résultat: 20 minutes pour examen, 15 minutes pour la mise en œuvre de base, 15 minutes pour la suppression des bogues Soumission: https://atcoder.jp/contests/tenka1-2017/submissions/18043771
Tout d'abord, lors de la sélection d'un certain $ A \ _i $, la sélection de $ A \ _j (= A \ _i) $ n'affecte pas au niveau du bit ou, donc les informations données auront la même valeur $ A \ _i $ En les rassemblant, $ A \ _i $ peut avoir des valeurs différentes. En regardant les conditions de l'énoncé du problème ci-dessous, il semble qu'il puisse être résolu avec une idée proche du chiffre DP car il existe des conditions de ** $ k $ ou moins. De plus, j'ai remarqué que je ne pouvais pas sélectionner un élément avec $ MSB $ supérieur à $ MSB $ ($ m $) de $ k $, alors j'ai décidé de ** séparer les cas par $ MSB $ de chaque valeur **. .. Pour le moment, vous ne pouvez pas choisir $ MSB $ supérieur à $ m $. De plus, si vous sélectionnez uniquement les éléments dont $ MSB $ est inférieur à $ m $, vous savez que le bit au niveau du bit ou est inférieur à $ k $ à ce stade, vous pouvez donc sélectionner de tels éléments. Cependant, si j'ai $ msb $ qui est le même que $ m $, j'ai réalisé qu'il devrait être inférieur à $ k $ dans les chiffres ci-dessous ** $ msb $ **, donc ** dans l'ordre du chiffre supérieur DP * J'ai décidé de prendre une politique proche de *. En d'autres termes, l'ensemble des nombres qui peuvent être sélectionnés en regardant un certain chiffre est $ s $ comme suit. (En passant, il est plus facile et plus rapide à implémenter en gérant si $ s $ est sélectionné ou non avec un tableau booléen)
Lorsque le bit $ i $ est vu, le traitement suivant est effectué, puis le bit $ i-1 $ est traité.
(1) Lorsque ce bit de $ k $ est défini C'est l'une des solutions candidates car bit à bit ou devient inférieure à $ k $ en sélectionnant uniquement le nombre de celles incluses dans $ s $ qui n'ont pas ce bit.
(2) Lorsque ce bit de $ k $ n'est pas défini Si vous choisissez le nombre de bits debout, au niveau du bit ou supérieur à $ k $, alors ** ces nombres sont exclus de $ s $ **, et au niveau du bit ou pas toujours inférieur à $ k $. Il n'y a aucun candidat pour une solution.
La valeur maximale parmi les solutions candidates obtenues en effectuant ce qui précède avec des bits arbitraires peut être obtenue. De plus, dans ce qui précède, seul le traitement de moins de $ k $ est effectué, et le traitement de (1) et (2) lorsque ** $ i = 0 $ peut être effectué comme le traitement de $ k $ ou moins **, donc (1) Dans le cas de, tout élément contenu dans $ s $ peut être sélectionné, et dans le cas de (2), tout nombre contenu dans $ s $ dont le bit ne tient pas peut être sélectionné. Et comme il n'y a pas de msb de ** $ k = 0 $ **, à ce moment, la valeur de l'élément 0 inclus dans $ s $ doit être sortie dans l'état initial.
(✳︎)… Le point à prendre en compte dans le chiffre DP (problème proche de) est que ** il doit être inférieur à un certain chiffre **. Cependant, dans les cas suivants ** Attention uniquement lorsque les valeurs sont égales **.
Je connaissais le type de boîtier d'angle que j'avais vu jusqu'à présent, mais j'ai marché dessus. ** Je veux faire ressortir la partie qui semble être un boîtier d'angle lorsque l'on considère **.
diff:1404 Résultat: Discussion 10 minutes, Implémentation de base 10 minutes, Suppression du bogue → minutes → Vérifiez et confirmez qu'il existe une solution, puis supprimez le bogue AC Soumission: https://atcoder.jp/contests/agc020/submissions/18056229
(Ci-après, $ k $ dans l'énoncé du problème a été remplacé par $ n $, mais ne vous inquiétez pas.)
Premièrement, $ a [n-1] $ doit être égal à 2. À ce stade, je me demande laquelle des valeurs minimales et maximales est la plus facile à trouver. À ce stade, la construction de la valeur minimale doit être faite aussi petite que possible afin qu'elle soit un multiple de ** $ a [i] $ à la fin de chaque tour **, donc je peux y penser immédiatement. En d'autres termes, lorsque $ check [i] $: = (le nombre d'enfants restant après le tour $ i $ est terminé), $ check [i] = \ lceil \ frac {check [i + 1]} {a [ i]} \ rceil \ times a [i] $ est le minimum (il ne tient pas toujours comme vous pouvez le voir dans l'exemple 2).
De plus, pour maximiser le résultat en fonction du minimum, le maximum est de ** $ check [i + 1] + a [i] -1 $ ou moins pour $ check [i] $. Ce devrait être le nombre de $ a [i] $ **, donc $ check [i] = \ lfloor \ frac {check [i + 1] + a [i + 1] -1} {a [i]} \ rfloor \ times a [i] $ est la réponse.
En fait, s'il tient à la valeur minimale, il tient également à la valeur maximale, il aurait donc dû être divisé en ** étapes comme la construction à la valeur minimale → le jugement de savoir si le produit construit est correct → la construction de la valeur maximale **. J'ai fait un bug parce que j'ai fait la construction et le jugement au minimum en même temps. ** Je veux garder à l'esprit que je vais concevoir un programme qui est moins susceptible de provoquer des bogues même si la quantité d'écriture augmente.
De plus, c'était débordé ..., j'ai fait un bug en faisant la construction et le jugement de cas d'angle en même temps, comme ** l'implémentation se fait séparément sans sauter **.
Recommended Posts