# [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

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

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

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

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

### repetition

The iterations include the following:

• `times`
• `each`
• `while`
• `loop`

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.

``````#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
``````