My name is Yuya and I am a 4th year university student (as of July 2020). I am doing competitive programming (AtCoder) as a hobby. I wanted to become a brown coder and output something, so I decided to write this article.
This article is for beginners of programming language Ruby and competition professionals. I write about the basic grammar and methods of Ruby, and the basics and tips of competition pros.
Please note that this is just my writing style and method, so it may not always be optimal.
If you understand what is written in this article and solve some exercises, you should be able to solve most of AtCoder's A (easiest) and B (second easiest) problems. ..
AtCoder is the most famous competitive programming site in Japan. I'm saying it, but I think it's ** probably **.
Competitive programming contests are held every week from 21:00 on Saturdays and Sundays. Questions from past contests are always available.
There are three main types of contests.
The lower you go, the more difficult it becomes. Basically, ABC is often held.
In addition, a contest equivalent to one of the above difficulty levels may be held by a company or the like. There are some that you can get a prize by getting higher. (!)
Basically, about 6 questions will be asked in each contest. They are named A, B, C, D, E, F respectively. The later it gets, the harder it gets.
By the way, as a brown coder, I can solve problems A and B almost every time. Sometimes the C problem cannot be solved, and the D problem has never been solved.
I have the impression that after the C problem, you need something like the tips of a competitive professional, and after the D problem, you will need proper knowledge.
I found a helpful article, so I will quote the level of the problem.
--A Problem: Simple grammar check, often with a score of 100 --B Problem: A simple for statement, often with a score of 200, including if statements, similar to Fizz Buzz --C Problem: Computational complexity coding is now required, often with a score of 300 --D Problem: The score is often 400 points, and from this point onward, it will be necessary to study algorithms. --E Question: This is a serious and difficult question, often with a score of 500 points. --F Problem: The score is often 600 points, which makes it difficult at once. If you aim for yellow, it ’s a problem you want to solve.
Each user will be given a rating and a corresponding color, depending on how well they responded to the contest. I quote from this article written by Mr. chokudai, the president of AtCoder.
AtCoder (competitive programming) color / rank and ability evaluation, problem example
Every 400 is colored, in the order of red, orange, yellow, blue, water, green, brown, gray, and black.
If you want to make a very rough evaluation without fear of misunderstanding,
--Gray can be anyone if you participate, so there is no guarantee other than motivation. --If you are a student and brown, it is excellent, but as an engineer, it is a little unsatisfactory. It's a relief if the engineer who came by dispatch is brown. --Green is enough algorithm power for most companies. Although it is not ranked high in terms of AtCoder, it is the highest rating on other companies' evaluation sites. --There is no doubt about the basic algorithm processing power when it is light blue. --Blue and above are at a level where even some listed IT companies do not have any. --A monster from yellow. Think of it as a machine that solves the problems of competitive professionals. --Orange is strange. --Red has already been invited to world competitions.
In competitive programming Receive (input) the given value, Process it to get the desired value (output). These are called ** standard I / O **.
I will explain each method of input and output. There are various methods, but here I will introduce my method.
Receive the value with gets.
You will now receive one line of value.
If multiple values are given in one line, use split to receive them.
#input
# Hello
input = gets
puts input
#output
# Hello
#input
# Hello World
input = gets.split(" ") #Receive as an array, separated by whitespace
puts input
#output
# Hello
# World
The output uses puts as in the example above.
It outputs the value and starts a new line.
The value received by gets is treated as a string.
So if you want to receive a number, you need to convert the data type.
Here, we will use to_i because it will be converted to a number.
#input
# 10
input = gets.to_i
puts input + 5
#output
# 15
Others include to_f to decimal, to_s to convert to a string, and to_a to convert to an array.
-How to receive value from Ruby standard input -[Ruby] Summary of standard input and output
The iterations include the following:
timeseachwhileloopI will explain each with concrete examples.
times
A method for numbers. Repeat the number of times that number.
3.times do
puts "Hello"
end
#output
# Hello
# Hello
# Hello
each
Run for each of multiple values.
["red", "blue", "green"].each do |color|
puts color
end
#output
# red
# blue
# green
while
Repeats as long as the conditional expression is satisfied. If there is a value to use in the conditional expression, be careful not to forget to update it.
i = 0
while i < 3
puts i
i += 1
end
#output
# 0
# 1
# 2
loop
I think it's best not to use this (** if it's **, don't write it **).
The reason is that if you do not let it escape, you will end up in an infinite loop.
It may be used by forcibly terminating with break.
(Addition)
Any other loop, not just loop, can fall into an infinite loop.
It is necessary to write a process to get out of the loop properly, and to set the conditions carefully.
i = 0
loop do
if i >= 3
break
end
puts i
i += 1
end
#output
# 0
# 1
# 2
length and size return the length of the string and the number of elements in the array.
str = "Hello"
puts str.length
#output
# 5
arr = ["red", "blue", "green"]
puts arr.length
#output
# 3
Both return the same result when changing length to size.
sort, reverse
sort sorts the elements of the array in ascending order.
reverse reverses the order.
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"]
Among the elements of the array, there are methods that return the maximum and minimum values.
The maximum value is max and the minimum value is min.
arr = [4, 5, 1, 3, 2]
puts arr.max
puts arr.min
#output
# 5
# 1
There are methods that return the first and last values of the elements of the array.
The first is first and the last is last.
arr = [4, 5, 1, 3, 2]
puts arr.first
puts arr.last
#output
# 4
# 2
Permutation with permutation,
You can generate combinations with combination.
We also use a method that creates an array called 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]]
Use the method gcd () for integers.
By the way, the greatest common divisor is greatest common divisor in English.
Therefore, it is abbreviated as gcd.
num = 9
puts num.gcd(6)
#output
# 3
Use the method lcm () for integers.
By the way, the least common multiple is least common multiple in English.
Therefore, it is abbreviated as lcm.
num = 9
puts num.lcm(6)
#output
# 18
Use a module called prime.
By the way, the prime number is prime number in English.
You need to run require'prime' to use the module.
(Addition) It was a mistake of "library" instead of "module".
#input
# 7
require 'prime'
num = gets.to_i
if Prime.prime?(num)
puts "#{num}Is a prime number."
else
puts "#{num}Is not a prime number."
end
#output
#7 is a prime number.
(Addition) The way to write the if statement was a long expression. It is better to write as follows.
if num.prime?
TLE
If you're just starting out as a competitive pro, I think this will happen in rapid succession. Lol
TLE is an abbreviation for Time Limit Exceeded.
In competition pros, it is important to calculate efficiently. Unnecessary calculations should be avoided.
However, with regard to this, after doing it to some extent, I will come to understand with my skin that "** This will not be a TLE ... **". And you will be able to understand to some extent how to avoid it.
I'm still studying, but I think I have to read the explanation of the problem that has become TLE and gradually learn how to calculate efficiently.
Anyway, it is important to get into the habit of reviewing yourself to see if you are doing unnecessary calculations.
Questions A and B are relatively low in difficulty, so as you get used to them, you may skip the question sentences. (myself) If you do so, you may be addicted to the swamp due to a slight misunderstanding.
I've heard many times during the exam that reading comprehension is more important than calculation for mathematical word problems, but the same is true for competition pros. If you don't understand the problem statement correctly, you can't solve the problem, no matter how many fast algorithms you know.
The faster you solve the problem, the better the performance will be, so you will be impatient, but it is important to read the problem statement properly and understand the conditions correctly before you start solving the problem.
This is a common pitfall. ** How many times have you been caught in this trap ... **
As mentioned above, it is important to read the problem statement properly and understand the conditions correctly.
One thing that is often overlooked is whether or not this 0 is included.
This may be the reason why the calculation is completed in time by all means, and even though there is no problem in assembling the logic, it becomes WA (Wrong Answer).
It's okay if you don't know it, but here are three things that are just a little more time efficient (?).
num = gets.to_i
if num > 0
puts num
end
Speaking of how to write an if statement, I think this is the basic form, but you can also write it as follows.
num = gets.to_i
puts num if num > 0
num = gets.to_i
if num > 0
puts num
else
puts 0
end
Using the ternary operator, you can also write:
num = gets.to_i
puts num > 0 ? num : 0
OR
if x == "a" || x == "b" || x == "c"
#processing
end
If you want to write this a little cooler, you can also write it as follows.
if ["a", "b", "c"].include?(x)
#processing
end
I'll put some links here. The top "10 past questions" was solved when I was just starting out.
―― What to do next after registering with AtCoder ~ You can fight enough if you solve this much! Past questions selected 10 questions ~ -AtCoder version! Ant book (beginner)
I wrote about the basics of Ruby and competition pros. I think it's not so difficult to turn brown if you can get used to it by solving past questions.
Right now, I'm working hard to turn it green, but my honest impression is that it's time to study algorithms and data structures. I want to turn green while I'm a college student.
Recommended Posts