Apprentissage de Ruby avec AtCoder 14 [3rd Algorithm Practical Test Sprinkler] Création de hachage, ajout de clé / valeur

introduction

Participer à une programmation compétitive dans le cadre de l'apprentissage de Ruby et des algorithmes. Ici, nous sortons ce que nous avons appris pendant l'apprentissage.

Cette fois à propos du hasch. La raison pour laquelle cet article a été rédigé était le 3e test pratique de l'algorithme, question 5 "Sprinkler".

Ce problème était un problème auquel on pouvait facilement répondre en utilisant le hachage. J'avais peu de compréhension du hachage et je n'ai pas pu répondre à cette question pendant le test ...

Alors cette fois,

① Répondez à cette question en utilisant un hachage ② Réfléchissez à la façon d'utiliser le hachage en fonction de la réponse

Avec ce genre de flux, je voudrais le résumer à ma manière.

problème

Un graphe non orienté composé de N sommets numérotés 1,2,3, ..., N et M côtés non orientés numérotés 1,2,3, ..., M Donné. Le côté i relie les sommets ui et vi dans les deux sens.

Chaque sommet peut être coloré, initialement le sommet i est peint avec la couleur ci. (Dans ce problème, la couleur est représentée par un entier supérieur ou égal à 1 et inférieur ou égal à 10 ** 5).

Des sprinkleurs sont installés à chaque sommet. Lorsque vous démarrez l'arroseur au sommet i, Les couleurs de tous les sommets adjacents au sommet i sont repeintes avec la couleur du sommet i lorsque l'arroseur est activé.

Traitez les requêtes Q s1, s2,…, sQ données dans le format suivant dans l'ordre. : Affiche la couleur actuelle du sommet x. Ensuite, lancez l'arroseur au sommet x. Donné sous la forme 1 x. : Affiche la couleur actuelle du sommet x. Remplacez ensuite la couleur du sommet x par y. Donné sous la forme 2 x y.

** Contraintes ** --Toutes les entrées données sont des entiers

• 1≤N,Q≤200
• 0≤M≤N(N−1)/2
• 1≤ui,vi≤N
• 1≤ci≤10**5 --i est une chaîne de caractères dans l'un des formats suivants
  • '1 x'(1≤x≤N)
  • '2 x y' (1≤x≤N,1≤y≤10**5) --Il n'y a pas plusieurs côtés ou auto-boucles dans un graphique donné

L'entrée est donnée sous la forme suivante.

N M Q
u1 v1
⋮
uM vM
c1 c2 ⋯ cN
s1
⋮
sQ

Exemple d'entrée
3 2 3
1 2
2 3
5 10 15
1 2
2 1 20
1 1

Exemple de sortie
10
10
20

L'image du problème ressemble à ceci:

répondre

Cette fois, j'ai fait une réponse en me référant aux réponses d'autres personnes.

N, M, Q = gets.split(" ").map(&:to_i)

H = Hash.new{|hash, key| hash[key] = []}　#① Créez un hachage vide

M.times do
  u, v = gets.split(" ").map(&:to_i) 
  H[u].push(v) #② Ajout au hachage
  H[v].push(u) #② Ajout au hachage
end

C = gets.split(" ").map(&:to_i)
C.insert(0, nil)

Q.times do 
  x,y,z = gets.split(" ").map(&:to_i)
  puts C[y]
  if x == 1
    H[y].each{|i| C[i]=C[y] }
  else
    C[y] = z
  end
end

À propos de cette réponse À propos de la création d'un hachage et de l'ajout de clés et de valeurs au hachage Je vais essayer de le résumer afin de pouvoir saisir l'image à utiliser dans la réponse suivante.

① Créez un hachage vide

Dans la solution ci-dessus, un hachage vide est préparé en donnant un bloc {} à la nouvelle méthode de la classe Hash.

H = Hash.new{|hash, key| hash[key] = []}

Chaque fois que vous ajoutez une clé et une valeur au hachage, le bloc est évalué et un objet est créé. Dans le code ci-dessus, un tableau vide est la valeur par défaut de la valeur. En effet, la question à laquelle il faut répondre cette fois est une question dans laquelle plusieurs valeurs peuvent exister pour une clé. (La clé contient un sommet et la valeur contient le sommet adjacent à ce sommet (connecté par un côté))

② Ajout au hachage

L'objet reçu de l'entrée standard est ajouté au hachage en tant que clé et valeur. Dans cette réponse, la valeur est ajoutée en tant qu'élément au tableau défini comme valeur par défaut.

u, v = gets.split(" ").map(&:to_i) 
H[u].push(v) #u comme clé et v comme valeur
#Puisqu'il s'agit d'un ajout au tableau, "<<Vous pouvez également utiliser le symbole "".
H[u] << v

Jusqu'à présent, j'ai essayé de résumer les images à ma manière.

C'est un peu encombré, mais j'ai l'impression d'avoir enfin saisi l'image.

Lorsque vous souhaitez utiliser le hachage (1) Définissez la relation entre la clé et la valeur dans le bloc. (2) Chaque fois qu'une clé est ajoutée au hachage, une valeur est préparée selon (1). (3) Lors de l'ajout ou de la modification de la valeur, suivez la forme de la valeur par défaut.

Pour le moment, j'ai trouvé que je pouvais aborder ce problème de cette manière.

finalement

Jusqu'à présent, j'ai résumé à ma manière la création de hachages et l'ajout de clés et de valeurs. Je veux utiliser de plus en plus le hash et me l'approprier.

J'ai l'intention de le résumer en lisant la référence etc. Si vous avez des erreurs, je vous serais reconnaissant de bien vouloir les signaler.