Je m'appelle Yuya et je suis étudiant en 4e année à l'université (à partir de juillet 2020). Je fais de la programmation compétitive (AtCoder) comme passe-temps. Je voulais devenir un codeur marron et produire quelque chose, j'ai donc décidé d'écrire cet article.
Cet article s'adresse aux débutants du langage de programmation Ruby et aux professionnels de la concurrence. J'écris sur la grammaire et les méthodes de base de Ruby, ainsi que sur les bases et les astuces des professionnels de la compétition.
Veuillez noter que ce n'est que mon style et ma méthode d'écriture, donc ce n'est pas toujours optimal.
Si vous comprenez ce qui est écrit dans cet article et résolvez certains exercices, vous devriez être en mesure de résoudre la plupart des problèmes A (problème le plus simple) et B (deuxième problème le plus simple) d'AtCoder. ..
AtCoder est le site de programmation de concours le plus connu au Japon. Je le dis, mais je pense que c'est ** probablement **.
Un concours de programmation a lieu chaque semaine à partir de 21h00 les samedis et dimanches. Les questions des concours précédents sont toujours disponibles.
Il existe trois principaux types de concours.
Plus vous descendez, plus cela devient difficile. Fondamentalement, ABC est souvent tenu.
De plus, un concours équivalent à l'un des niveaux de difficulté ci-dessus peut être organisé par une entreprise ou autre. Il y en a que vous pouvez obtenir un prix en devenant plus élevé. (!)
En gros, environ 6 questions seront posées dans chaque concours. Ils sont appelés respectivement A, B, C, D, E, F. Plus ça arrive tard, plus ça devient difficile.
Au fait, si je suis un codeur brun, je peux résoudre les problèmes A et B presque à chaque fois. Parfois, le problème C ne peut pas être résolu et le problème D n'a jamais été résolu.
J'ai l'impression qu'après le problème C, vous avez besoin de quelque chose comme les conseils d'un professionnel compétitif, et après le problème D, vous aurez besoin de connaissances appropriées.
J'ai trouvé un article utile, je vais donc citer le niveau du problème.
Conseils sur le concours AtCoder
--Un problème: confirmation grammaticale simple, souvent avec un score de 100 --B Problème: Simple pour la déclaration, le traitement y compris la déclaration if, a souvent marqué 200 points, similaire à Fizz Buzz --C Problème: Vous devrez coder avec beaucoup de calcul, qui est souvent un score de 300 points. --D Problème: Le score est souvent de 400 points, et à partir de ce moment, il sera nécessaire d'étudier l'algorithme. --E Problème: Il s'agit d'un problème grave et difficile qui a souvent un score de 500 points. --F Problème: Le score est souvent de 600 points, ce qui rend la tâche difficile à la fois. Si vous visez le jaune, c’est un problème que vous voulez résoudre.
Chaque utilisateur recevra une note et une couleur correspondante, en fonction de sa réponse au concours. Je cite cet article écrit par M. chokudai, le président d'AtCoder.
Tous les 400 sont colorés, dans l'ordre du rouge, orange, jaune, bleu, eau, vert, marron, gris et noir.
Si vous souhaitez faire une évaluation très grossière sans crainte de malentendu,
- Le gris peut être n'importe qui si vous participez, il n'y a donc aucune garantie autre que la motivation. --Si vous êtes étudiant et marron, c'est excellent, mais en tant qu'ingénieur, c'est un peu insatisfaisant. C'est un soulagement si l'ingénieur qui est venu par dépêche est brun. --Le vert est suffisant pour la plupart des entreprises. Bien qu'il ne soit pas classé haut en termes d'AtCoder, il s'agit de la note la plus élevée sur les sites d'évaluation d'autres entreprises. --Il n'y a aucun doute sur la puissance de traitement de l'algorithme de base lorsqu'il est bleu clair. --Blue et au-dessus sont à un niveau où même certaines sociétés informatiques cotées n'en ont pas. --Un monstre jaune. Pensez-y comme une machine qui résout les problèmes des professionnels compétitifs.
- L'orange est étrange. --Red a déjà été invité à des compétitions mondiales.
En programmation compétitive Recevoir (saisir) la valeur donnée, Traitez-le pour obtenir la valeur souhaitée (sortie). Ceux-ci sont appelés ** entrée / sortie standard **.
Je vais expliquer chaque méthode d'entrée et de sortie. Il existe différentes méthodes, mais ici je vais vous présenter ma méthode.
Recevez la valeur avec gets.
Vous recevrez maintenant une ligne de valeur.
Si plusieurs valeurs sont données sur une seule ligne, utilisez split pour les recevoir.
#contribution
# Hello
input = gets
puts input
#production
# Hello
#contribution
# Hello World
input = gets.split(" ") #Recevoir sous forme de tableau, séparé par un espace blanc
puts input
#production
# Hello
# World
La sortie utilise «met» comme dans l'exemple ci-dessus. Il sort la valeur et coupe la ligne.
Les valeurs reçues par gets sont traitées comme des chaînes.
Donc, si vous souhaitez recevoir un numéro, vous devez convertir le type de données.
Ici, nous utilisons to_i car il est converti en valeur numérique.
#contribution
# 10
input = gets.to_i
puts input + 5
#production
# 15
D'autres incluent to_f pour les nombres fractionnaires, to_s pour la conversion en chaînes et to_a pour la conversion en tableaux.
Les itérations incluent les éléments suivants:
timeseachwhileloopJe vais expliquer chacun avec des exemples concrets.
times
Une méthode pour les nombres. Répétez le nombre de fois ce nombre.
3.times do
puts "Hello"
end
#production
# Hello
# Hello
# Hello
each
Exécutez pour chacune des valeurs multiples.
["red", "blue", "green"].each do |color|
puts color
end
#production
# red
# blue
# green
while
Répétez tant que l'expression conditionnelle est satisfaite. Si vous avez une valeur à utiliser dans une expression conditionnelle, veillez à ne pas oublier de la mettre à jour.
i = 0
while i < 3
puts i
i += 1
end
#production
# 0
# 1
# 2
loop
Je pense qu'il vaut mieux ne pas l'utiliser (** si c'est **, ne l'écrivez pas **). La raison en est que si vous ne le laissez pas s'échapper, vous vous retrouverez dans une boucle infinie. Il peut être utilisé en se terminant de force par «break».
(Une addition) Toute autre boucle, pas seulement «loop», peut tomber dans une boucle infinie. Il est nécessaire d'écrire un processus pour sortir correctement de la boucle et de définir les conditions avec soin.
i = 0
loop do
if i >= 3
break
end
puts i
i += 1
end
#production
# 0
# 1
# 2
length et size renvoient la longueur de la chaîne et le nombre d'éléments dans le tableau.
str = "Hello"
puts str.length
#production
# 5
arr = ["red", "blue", "green"]
puts arr.length
#production
# 3
Les deux renvoient le même résultat lors du changement de «longueur» en «taille».
sort, reverse
sort trie les éléments du tableau dans l'ordre croissant.
«reverse» inverse l'ordre.
arr = [3, 1, 2]
arr.sort
# [1, 2, 3]
arr = [3, 1, 2]
arr.sort.reverse
# [3, 2, 1]
arr = ["red", "blue", "green"]
arr.sort
# ["blue", "green", "red"]
Il existe des méthodes qui renvoient les valeurs maximale et minimale des éléments du tableau. La valeur maximale est «max» et la valeur minimale est «min».
arr = [4, 5, 1, 3, 2]
puts arr.max
puts arr.min
#production
# 5
# 1
Il existe une méthode qui renvoie la première et la dernière valeur des éléments du tableau. Le premier est «premier» et le dernier est «dernier».
arr = [4, 5, 1, 3, 2]
puts arr.first
puts arr.last
#production
# 4
# 2
Commande avec permutation,
Vous pouvez générer des combinaisons avec «combinaison».
Nous utilisons également une méthode qui crée un tableau appelé to_a.
arr = [1, 2, 3]
arr.permutation.to_a
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
a = [1, 2, 3, 4]
a.combination(1).to_a
# [[1],[2],[3],[4]]
a.combination(2).to_a
# [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
a.combination(3).to_a
# [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
a.combination(4).to_a
# [[1,2,3,4]]
Utilisez la méthode «gcd ()» pour les entiers. À propos, l'engagement maximal est «le plus grand diviseur commun» en anglais. Par conséquent, il est abrégé en «pgcd».
num = 9
puts num.gcd(6)
#production
# 3
Utilisez la méthode «lcm ()» pour les entiers. À propos, le multiple commun minimum est «le multiple le moins commun» en anglais. Par conséquent, il est abrégé en «lcm».
num = 9
puts num.lcm(6)
#production
# 18
Utilisez un module appelé «prime». Au fait, le nombre premier est «nombre premier» en anglais.
Vous devez exécuter require'prime' pour utiliser le module.
(Une addition) C'était une erreur de "bibliothèque" au lieu de "module".
#contribution
# 7
require 'prime'
num = gets.to_i
if Prime.prime?(num)
puts "#{num}Est un nombre premier."
else
puts "#{num}N'est pas un nombre premier."
end
#production
#7 est un nombre premier.
(Une addition) La manière d'écrire l'instruction if était une expression longue. Il vaut mieux écrire comme suit.
if num.prime?
TLE
Lorsque je commence tout juste à concourir, je pense que cela se produira rapidement. Lol «TLE» est une abréviation de «Time Limit Exceeded».
Chez les pros de la compétition, il est important de calculer efficacement. Les calculs inutiles doivent être évités.
Cependant, à ce sujet, après l'avoir fait dans une certaine mesure, j'arriverai à comprendre "** Ce ne sera pas TLE ... **". Et vous pourrez comprendre dans une certaine mesure comment l'éviter.
J'étudie toujours, mais je pense que je n'ai pas d'autre choix que de lire l'explication du problème qui est devenu TLE et d'apprendre progressivement à calculer efficacement.
Quoi qu'il en soit, il est important de prendre l'habitude de vous revoir pour voir si vous faites des calculs inutiles.
Les questions A et B sont relativement peu difficiles, donc au fur et à mesure que vous vous y habituez, vous pouvez sauter les phrases de questions. (moi même) Si vous le faites, vous pourriez être accro au marais en raison d'un léger malentendu.
J'ai entendu à plusieurs reprises au cours de la période d'examen que ** les textes de mathématiques sont plus importants à lire que les calculs **, mais il en va de même pour les professionnels de la compétition. Si vous ne comprenez pas correctement l'énoncé du problème, vous ne pouvez pas résoudre le problème, quel que soit le nombre d'algorithmes rapides que vous connaissez.
Plus vite vous résolvez le problème, meilleures sont les performances, vous serez donc impatient, mais il est important de lire correctement l'énoncé du problème et de comprendre correctement les conditions avant de commencer à résoudre le problème.
C'est un écueil courant. ** Combien de fois avez-vous été pris dans ce piège ... **
Comme mentionné ci-dessus, il est important de lire correctement l'énoncé du problème et de comprendre correctement les conditions. Ce qui est souvent négligé, c'est de savoir si ce «0» est inclus ou non.
Cela peut être la raison pour laquelle le calcul est terminé à temps par tous les moyens, et même s'il n'y a pas de problème d'assemblage de la logique, cela devient «WA (mauvaise réponse)».
Ce n'est pas grave si vous ne le savez pas, mais voici trois choses qui sont juste un peu plus efficaces (?)
num = gets.to_i
if num > 0
puts num
end
En parlant de comment écrire une instruction if, je pense que c'est la forme de base, mais vous pouvez également l'écrire comme suit.
num = gets.to_i
puts num if num > 0
num = gets.to_i
if num > 0
puts num
else
puts 0
end
En utilisant un opérateur ternaire, vous pouvez également écrire:
num = gets.to_i
puts num > 0 ? num : 0
OR
if x == "a" || x == "b" || x == "c"
#En traitement
end
Si vous voulez écrire ceci un peu plus cool, vous pouvez également l'écrire comme suit.
if ["a", "b", "c"].include?(x)
#En traitement
end
Je vais mettre quelques liens ici. Le top «10 questions passées» a été résolu lorsque je commençais à peine.
J'ai écrit sur les bases de Ruby et des pros de la compétition. Je ne pense pas qu'il soit si difficile de devenir brun si vous pouvez vous y habituer en résolvant des questions passées.
En ce moment, je travaille dur pour le mettre au vert, mais mon impression honnête est qu'il est temps d'étudier les algorithmes et les structures de données. Je veux devenir vert pendant que je suis étudiant.
Recommended Posts