[At Coder] Introducing Competitive Pro with Ruby

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.

Target audience

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. ..

About AtCoder

AtCoder is the most famous competitive programming site in Japan. I'm saying it, but I think it's ** probably **.

Overview

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. (!)

Difficulty of the problem

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.

Tips about AtCoder Contest

--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.

Color (rating)

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.

Basic knowledge

Standard input / output

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.

input

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

output

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

Data type

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.

reference

-How to receive value from Ruby standard input -[Ruby] Summary of standard input and output

repetition

The iterations include the following:

I 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

Convenient method

String length, 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
# 5
arr = ["red", "blue", "green"]
puts arr.length

#output
# 3

Both return the same result when changing length to size.

Sort related

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"]

Maximum, minimum: max, min

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

First, last: first, last

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

Permutations, combinations

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]]

Things to use occasionally

Greatest common divisor

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

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 number

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?

Common mistakes

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.

Misunderstand the problem

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.

Whether to include 0

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).

Serpentine

It's okay if you don't know it, but here are three things that are just a little more 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"
    #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

Exercise link

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)

Summary

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

[At Coder] Introducing Competitive Pro with Ruby
[At Coder] Solve the ABC182 D problem with Ruby
Introducing Rspec with Ruby on Rails x Docker
[Competition Pro] Solve the knapsack problem with Ruby
Install Ruby 3.0.0 with asdf
Getting Started with Ruby
Studying at CodeWar (ruby) ②
11th, Classification with Ruby
Evolve Eevee with Ruby