【AtCoder】Rubyで競プロに入門する

# 対象読者

プログラミング言語Rubyと競プロの初心者に向けた記事です。
Rubyの基本的な文法やメソッド、競プロの基本やヒントについて書いています。

ここで紹介しているのはあくまで僕の書き方・やり方なので、必ずしも最適ではないか点には注意してください。

この記事に書いてあることを理解して、少し練習問題を解いていくと、AtCoderのだいたいのA問題（一番易しい問題）とB問題（二番目に易しい問題）は解けるようになるはずです。

# AtCoderについて

[AtCoder](https://atcoder.jp/)は、とても有名な競技プログラミングのサイトです。

## 概要

土日の21時から、毎週のように競技プログラミングのコンテストが開催されています。
過去のコンテストの問題はいつでも閲覧可能になっています。

コンテストの種類は、大きく次の3つがあります。

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

下にいけばいくほど難易度が上がります。
基本的にはABCが開催されることが多いです。

また、企業などが主催で、上記いずれかの難易度相当のコンテストが開催されることもあります。
上位になることで、賞金が貰えるものもあります。（！）

## 問題の難易度

基本的には、それぞれのコンテストで6問ほど出題されます。
A, B, C, D, E, Fとそれぞれ名前が付いています。
後になればなるほど難しくなります。

ちなみに、茶色コーダーの僕だと、A, B問題はだいたい毎回解けます。
C問題がたまに解けないことがあり、D問題は解けたことがない、という感じです。

C問題以降は競プロのコツのようなものが必要で、D問題以降はちゃんとした知識が必要になってくるかな～という印象です。

参考になる記事を見つけたので、問題のレベル感の部分を引用します。

[AtCoder コンテストについての tips](https://qiita.com/drken/items/8a6f139158cde8a61dce)

> - A 問題: スコア 100 点であることが多い、簡単な文法の確認
> - B 問題: スコア 200 点であることが多い、簡単な for 文、if 文を含む処理, Fizz Buzz と同程度
> - C 問題: スコア 300 点であることが多い、計算量を意識したコーディングが求められるようになります
> - D 問題: スコア 400 点であることが多い、ここから先はアルゴリズムの勉強も必要になってきます
> - E 問題: スコア 500 点であることが多い、本格的な難しい問題です
> - F 問題: スコア 600 点であることが多い、一気に難しくなります。黄色を目指すなら解きたい問題です

## 色（レーティング）

コンテストでの回答状況に応じて、各ユーザーにレーティングと、それに応じた色が付きます。
AtCoder社長のchokudaiさんが書かれているこの記事から引用します。

[AtCoder（競技プログラミング）の色・ランクと実力評価、問題例](http://chokudai.hatenablog.com/entry/2019/02/11/155904)

> 400ごとに色がついていて、赤・橙・黄・青・水・緑・茶・灰・黒、という順番になってます。
>
> 誤解を恐れずに超ざっくりとイメージでの評価をするなら、
>
> - 灰色は参加すれば誰でもなれるので意欲以外の保証はなし。
> - 学生で茶色なら優秀だがエンジニアとしてはちょっと物足りない。派遣とかで来たエンジニアが茶色あれば一安心。
> - 緑あれば大抵の企業でアルゴリズム力は十分。AtCoder的には決して上位ではないが、他社評価サイトなら最高評価。
> - 水色だと基礎的なアルゴリズム処理能力については疑いのないレベル。
> - 青以上は一部上場のIT企業でも、一人もいないことが結構あるレベルになる。
> - 黄色からは化け物。競プロの問題を解く機械だと思っておけば良い。
> - 橙はあたまおかしい。
> - 赤はもうなんか世界大会とかに招待されたりする。

# 基本知識

## 標準入出力

競技プログラミングでは、
与えられた値を受け取って（入力）、
それを加工するなどして、望まれる値を出します（出力）。
これらを**標準入出力**といいます。

入力と出力のそれぞれのやり方を解説します。
色々なやり方がありますが、ここでは僕のやり方を紹介します。

### 入力

`gets` で値を受け取ります。
これで1行分の値を受け取れます。
1行で複数の値が与えられるときは、`split` を使って受け取ります。

```ruby
# 入力
# Hello

input = gets
puts input

# 出力
# Hello
```

```ruby
# 入力
# Hello World

input = gets.split(" ") # 空白文字で区切って、配列として受け取る
puts input

# 出力
# Hello
# World
```

### 出力

出力は上の例のように `puts` を使います。
値を出力して、改行してくれます。

## データ型

`gets` で受け取った値は、文字列として扱われています。
そのため、数値を受け取りたい場合は、データ型を変換する必要があります。
ここでは数値に変換するので `to_i` を使います。

```ruby
# 入力
# 10

input = gets.to_i
puts input + 5

# 出力
# 15
```

他には、小数にする `to_f` や文字列に変換する `to_s` 、配列にする `to_a` などがあります。

### 参考

- [Ruby　標準入力から値を受け取る方法](https://qiita.com/Hayate_0807/items/2e9705091b181a104621)
- [【Ruby】標準入力と出力のまとめ](https://qiita.com/Sobue-Yuki/items/93638169e8a8a0c4b3d5)

## 繰り返し

繰り返しには、以下のようなものがあります。

- `times`
- `each`
- `while`

それぞれ具体例と一緒に解説します。

### times

数値に対するメソッドです。
その数値の大きさ回数、繰り返します。

```ruby
3.times do
    puts "Hello"
end

# 出力
# Hello
# Hello
# Hello
```

### each

複数の値のそれぞれに対して実行します。


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

# 出力
# red
# blue
# green
```

### while

条件式が満たされる間、繰り返し実行します。
条件式に使う値があれば、その更新を忘れないように注意が必要です。

```ruby
i = 0
while i < 3
    puts i
    i += 1
end

# 出力
# 0
# 1
# 2
```

# 便利なメソッド

## 文字列の長さ、配列の要素数

`length` や `size` は、文字列の長さや配列の要素数を返してくれます。

```ruby
str = "Hello"
puts str.length

# 出力
# 5
```

```ruby
arr = ["red", "blue", "green"]
puts arr.length

# 出力
# 3
```

どちらも `length` を `size` に変えても、同じ結果を返します。

## 並び替え関連

### sort, reverse

`sort` は、昇順に配列の要素を並び替えてくれます。
`reverse` は、並び順をひっくり返してくれます。

```ruby
arr = [3, 1, 2]
arr.sort
# [1, 2, 3]
```

```ruby
arr = [3, 1, 2]
arr.sort.reverse
# [3, 2, 1]
```

```ruby
arr = ["red", "blue", "green"]
arr.sort
# ["blue", "green", "red"]
```

### 最大、最小：max, min

配列の要素の中で、最大や最小の値を返してくれるメソッドがあります。
最大値が `max` で、最小値が `min` です。

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

# 出力
# 5
# 1
```

### 最初、最後：first, last

配列の要素の、最初と最後の値を返してくれるメソッドがあります。
最初が `first` で、最後が `last` です。

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

# 出力
# 4
# 2
```

## 順列、組み合わせ

`permutation` で順列、
`combination` で組み合わせを生成できます。
`to_a` という配列を生成するメソッドも使います。

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

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

# たまに使うもの

## 最大公約数

`gcd()` というメソッドを、整数に対して使います。
ちなみに、最大公約数は英語で `greatest common divisor` です。
そのため `gcd` と略されています。

```ruby
num = 9
puts num.gcd(6)

# 出力
# 3
```

## 最小公倍数

`lcm()` というメソッドを、整数に対して使います。
ちなみに、最小公倍数は英語で `least common multiple` です。
そのため `lcm` と略されています。

```ruby
num = 9
puts num.lcm(6)

# 出力
# 18
```

## 素数

`prime` というライブラリを使います。
ちなみに、素数は英語で `prime number` です。

ライブラリを使うために `require 'prime'` を実行する必要があります。

```ruby
# 入力
# 7

require 'prime'
num = gets.to_i
if num.prime?
  puts "#{num}は素数です。"
else
  puts "#{num}は素数ではありません。"
end

# 出力
# 7は素数です。
```

# よくあるミス

## TLE

競プロをやり始めたばかりのときは、これが連発するかと思います。笑
`TLE` とは `Time Limit Exceeded` の略です。

競プロでは、いかに効率良く計算するかが大切です。
不要な計算は避ける必要があります。

ただしこれに関しては、ある程度やっているうちに「**これだとTLEになるな…**」というのが肌感で分かってくるようになります。
そして、どうやったら避けられるかというのも、ある程度は分かるようになってきます。

不要な計算をしていないか、自分なりに見直す癖をつけることが大切です。

## 問題を誤解してしまう

A問題やB問題は比較的難易度が低いため、慣れてくると問題文を飛ばし読みしてしまうことがあります。
そうすると、ちょっとした勘違いがあったりして、沼にハマってしまうということが起きてしまいます。

**数学の文章題は計算よりも読解が大切**というのを大学受験期に何度も聞きましたが、競プロでもそれは同様です。
問題文を正しく理解できていないと、どんなに高速なアルゴリズムをたくさん知っていたとしても問題を解くことはできません。

解くスピードが早ければ早いほどパフォーマンスも上がるため、ついつい焦ってしまいますが、問題文をきちんと読んで、条件も正しく理解したうえで問題を解き始めることが大切です。

## 0 を含むか否か

よくある落とし穴として、これが挙げられます。

上述した通り、問題文をきちんと読んで条件を正しく理解することが大切です。
見落としがちなのが、この `0` を含むか否かというところです。

どう見ても時間内に計算が終わるし、ロジックの組み立てにも問題が見当たらないのに `WA (Wrong Answer)` となってしまうのは、これが原因かもしれません。

# 蛇足

知らなくても全く問題ありませんが、ほんの少しだけ時間効率が上がる（？）ものを3つほど紹介します。

## 1行でif文

```ruby
num = gets.to_i
if num > 0
    puts num
end
```

if文の書き方といえばこれが基本形かと思いますが、以下のように書くこともできます。

```ruby
num = gets.to_i
puts num if num > 0
```

## 三項演算子

```ruby
num = gets.to_i
if num > 0
    puts num
else
    puts 0
end
```

三項演算子というものを使うと、以下のように書くこともできます。

```ruby
num = gets.to_i
puts num > 0 ? num : 0
```

## OR

```ruby
if x == "a" || x == "b" || x == "c"
    # 処理
end
```

これをちょっとカッコよく書きたいと思ったら、以下のように書くこともできます。

```ruby
if ["a", "b", "c"].include?(x)
    # 処理
end
```

# 練習問題リンク

- [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067)
- [AtCoder 版！蟻本 (初級編)](https://qiita.com/drken/items/e77685614f3c6bf86f44)
- [AtCoder Problems](https://kenkoooo.com/atcoder/#/table/)

# まとめ

Rubyと競プロの基本について書いてみました。
ぶっちゃけ、過去問を解きまくって慣れることができれば、茶色になることはそう難しくないと思います。

それでは、最後まで読んでいただき、ありがとうございました。