[Ruby] [At Coder] Introducing competitive professionals with Ruby

10 minute read

My name is Yuya and I am a 4th year university student (as of July 2020). I play competitive programming (AtCoder) as a hobby. I became a brown coder and wanted to output something, so I decided to write this article.

Target audience

This article is for beginners in the programming language Ruby and competition professionals. I write about the basic grammar and methods of Ruby, the basics and tips of competitive professionals.

Please note that this is just my writing style, so it may not be the best choice.

After understanding what is written in this article and solving some exercises, you should be able to solve AtCoder’s problems A (the easiest problem) and B (the second easiest problem). ..

About At Coder

AtCoder is the most famous competition programming site in Japan. I’m telling you, but I think it maybe definitely.

Overview

From 21:00 on Saturdays and Sundays, competition programming contests are held every week. Issues from past contests are always available.

There are three major types of contests.

  • AtCoder Beginner Contest (ABC)
  • AtCoder Regular Contest (ARC)
  • AtCoder Grand Contest (AGC)

The lower you go, the more difficult it becomes. Basically, ABC is often held.

In addition, there are times when a contest sponsored by a company or the like is held with one of the above difficulty levels. There are also things that you can get prize money by becoming higher. (!)

Problem Difficulty

Basically, about 6 questions will be asked in each contest. They are named A, B, C, D, E, F respectively. The later it gets harder.

By the way, if I’m a brown coder, I can solve problems A and B almost every time. It seems that the C problem is sometimes unsolvable and the D problem is never solved.

The impression is that after the C problem, things like the tips of competitive professionals are needed, and after the D problem, proper knowledge is needed.

Now that I have found a helpful article, I will quote the level of the problem.

Tips about AtCoder Contest

-A Problem: Simple grammar check, often with a score of 100 -B problem: Simple for statement, if statement, often 200 score, similar to Fizz Buzz -C Problem: You will be required to do coding that is computationally intensive, often with a score of 300 -D Problem: Scores are often 400, and beyond this you will also need to study algorithms -E problem: A real hard problem, often with a score of 500 -F Problem: Scores of 600 are often difficult, all at once. If you aim for yellow, it is a problem you want to solve

Color (rating)

Depending on the response status of the contest, each user will be given a rating and a corresponding color. I quote from this article written by Mr. chokudai, President of AtCoder.

AtCoder (Competitive Programming) Color/Rank and Ability Evaluation, Example of Problem

Every 400 has a color, in the order red, orange, yellow, blue, water, green, brown, gray, black.

If you don’t fear misunderstandings

-Gray can be anyone by participating, so there is no guarantee other than willingness. -If you’re a student and brown, you’re good, but as an engineer, it’s a bit unsatisfactory. It would be a relief if the engineer who came to dispatch was brown. -Almost all companies have sufficient algorithm power if they are green. AtCoder is by no means a high ranking, but it is the highest rating if it is another company’s evaluation site. -Light blue, no doubt about basic algorithmic processing ability. -Blue is a level where some listed IT companies do not have any. -Yellow to monsters. Think of it as a machine that solves the problems of competitive professionals. -Orange is funny. -Red is already invited to the world competition.

Basic knowledge

Standard input/output

In competitive programming, Receiving the given value (input), Output the desired value by processing it (output). These are called standard input/output.

I will explain each method of input and output. There are various methods, but here I will introduce my method.

Input

Receive the value with gets. This will receive the value for one line. When multiple values are given on 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 white space
puts input

# Output
# Hello
# World

output

The output uses puts as in the example above. It outputs the value and returns a line.

Data type

The value received by gets is treated as a string. Therefore, if you want to receive a number, you need to convert the data type. Here we use to_i because we are going to convert it to a number.

# Input
# Ten

input = gets.to_i
puts input + 5

# Output
# 15

Other options include to_f for decimals, to_s for string conversion, and to_a for arrays.

Reference

repeat

The iterations include:

  • times
  • each
  • while
  • loop

Each will be explained along with concrete examples.

times

A method for numbers. Repeat that number of times.

3.times do
    puts "Hello"
end

# Output
# Hello
# Hello
# Hello

each

Do this for each of multiple values.

["red", "blue", "green"].each do |color|
    puts color
end

# Output
# red
# blue
# green

while

Executes repeatedly while the conditional expression is satisfied. If there is a value to be used 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 don’t think you should use this (*** don’t write **). Because if you don’t let it get out, you end up in an infinite loop. It may be used by forcibly ending with break.

(Additional) Any other loop, not just loop, can fall into an infinite loop. It is necessary to write a process that properly exits the loop and carefully set the conditions.

i = 0
loop do
    if i >= 3
        break
    end
    puts i
    i += 1
end

# Output
# 0
# 1
# 2

Useful methods

Length of string, number of array elements

length and size return the length of the string and the number of elements in the array.

str = "Hello"
puts str.length

# Output
# Five
arr = ["red", "blue", "green"]
puts arr.length

# Output
# 3

Both will return the same result even if you change length to size.

sort, reverse

sort sorts the elements of the array in ascending order. reverse flips the order.

arr = [3, 1, 2]
arr.sort
# [one two Three]
arr = [3, 1, 2]
arr.sort.reverse
# [3, 2, 1]
arr = ["red", "blue", "green"]
arr.sort
# ["blue", "green", "red"]

Maximum, minimum: max, min

There is a method that returns the maximum or minimum value of the array elements. The maximum value is max and the minimum value is min.

arr = [4, 5, 1, 3, 2]
puts arr.max
puts arr.min

# Output
# Five
# 1

First, last: first, last

There are methods that return the first and last values of the array elements. The first is first and the last is last.

arr = [4, 5, 1, 3, 2]
puts arr.first
puts arr.last

# Output
# Four
# 2

Permutations, combinations

permutation with permutation, You can generate a combination 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]]

Sometimes used

greatest common divisor

Use the method gcd() on 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

least common multiple

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

prime

Use the module called prime. By the way, the prime number is prime number in English.

You need to run require'prime' to use the module.

(Additional) It was an error in “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.

(Additional) The if statement was written in a long way. It is better to write it as follows.

if num.prime?

Common mistakes

TLE

If you are just starting a competitive professional, I think this will continue to occur. Lol TLE is an abbreviation for Time Limit Exceeded.

In competitive professionals, it is important to calculate efficiently. You should avoid unnecessary calculations.

However, with regard to this, it will become clear to the skin that “** This will not be TLE…**” while doing it to some extent. And, to some extent, we can understand how to avoid it.

I myself am still studying, but I think that I have to read the explanation of the problem that became TLE and learn little by little how to calculate efficiently.

Anyway, it is important to make a habit of reviewing your own or not doing unnecessary calculations.

Misunderstand the problem

The A and B problems are relatively difficult, so when you get used to them, you may skip the problem sentences and read them. (myself) If you do so, you may have a little misunderstanding, and you may end up in a swamp.

I’ve heard many times during the examination period that reading comprehension is more important than mathematics for mathematics, but the same applies to competitive professionals. If you do not understand the problem sentence correctly, you cannot solve the problem even if you know many fast algorithms.

The faster you solve it, the better your 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.

Whether to include ### 0

This is a common pitfall. How many times did you get this trap…

As mentioned above, it is important to read the problem statement properly and understand the conditions correctly. What I often overlook is whether or not this 0 is included.

This may be the reason why WA (Wrong Answer) is calculated even though the calculation is completed in time and no problem is found in the logic assembly.

Stagger

There is no problem if you don’t know, but here are three things that are slightly time-efficient (?).

if statement in one line

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

Ternary operator

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"
# Process
end

If you want to write this a little cooler, you can also write it like this:

if ["a", "b", "c"].include?(x)
# Process
end

Here are some links. I solved the top 10 past questions carefully when I was just starting out.

Summary

I wrote about the basics of Ruby and competitive professionals. 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 trying hard to get it green, but my honest impression is that it’s about time to study algorithms and data structures. I want to be green while I’m a college student.