対象読者
プログラミング言語Rubyと競プロの初心者に向けた記事です。
Rubyの基本的な文法やメソッド、競プロの基本やヒントについて書いています。
ここで紹介しているのはあくまで僕の書き方・やり方なので、必ずしも最適ではないか点には注意してください。
この記事に書いてあることを理解して、少し練習問題を解いていくと、AtCoderのだいたいのA問題（一番易しい問題）とB問題（二番目に易しい問題）は解けるようになるはずです。
AtCoderについて
AtCoderは、とても有名な競技プログラミングのサイトです。
概要
土日の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問題以降はちゃんとした知識が必要になってくるかな～という印象です。
参考になる記事を見つけたので、問題のレベル感の部分を引用します。
- A 問題: スコア 100 点であることが多い、簡単な文法の確認
- B 問題: スコア 200 点であることが多い、簡単な for 文、if 文を含む処理, Fizz Buzz と同程度
- C 問題: スコア 300 点であることが多い、計算量を意識したコーディングが求められるようになります
- D 問題: スコア 400 点であることが多い、ここから先はアルゴリズムの勉強も必要になってきます
- E 問題: スコア 500 点であることが多い、本格的な難しい問題です
- F 問題: スコア 600 点であることが多い、一気に難しくなります。黄色を目指すなら解きたい問題です
色（レーティング）
コンテストでの回答状況に応じて、各ユーザーにレーティングと、それに応じた色が付きます。
AtCoder社長のchokudaiさんが書かれているこの記事から引用します。
AtCoder（競技プログラミング）の色・ランクと実力評価、問題例
400ごとに色がついていて、赤・橙・黄・青・水・緑・茶・灰・黒、という順番になってます。
誤解を恐れずに超ざっくりとイメージでの評価をするなら、
- 灰色は参加すれば誰でもなれるので意欲以外の保証はなし。
- 学生で茶色なら優秀だがエンジニアとしてはちょっと物足りない。派遣とかで来たエンジニアが茶色あれば一安心。
- 緑あれば大抵の企業でアルゴリズム力は十分。AtCoder的には決して上位ではないが、他社評価サイトなら最高評価。
- 水色だと基礎的なアルゴリズム処理能力については疑いのないレベル。
- 青以上は一部上場のIT企業でも、一人もいないことが結構あるレベルになる。
- 黄色からは化け物。競プロの問題を解く機械だと思っておけば良い。
- 橙はあたまおかしい。
- 赤はもうなんか世界大会とかに招待されたりする。
基本知識
標準入出力
競技プログラミングでは、
与えられた値を受け取って（入力）、
それを加工するなどして、望まれる値を出します（出力）。
これらを標準入出力といいます。
入力と出力のそれぞれのやり方を解説します。
色々なやり方がありますが、ここでは僕のやり方を紹介します。
入力
gets で値を受け取ります。
これで1行分の値を受け取れます。
1行で複数の値が与えられるときは、split を使って受け取ります。
# 入力
# Hello
input = gets
puts input
# 出力
# Hello
# 入力
# Hello World
input = gets.split(" ") # 空白文字で区切って、配列として受け取る
puts input
# 出力
# Hello
# World
出力
出力は上の例のように puts を使います。
値を出力して、改行してくれます。
データ型
gets で受け取った値は、文字列として扱われています。
そのため、数値を受け取りたい場合は、データ型を変換する必要があります。
ここでは数値に変換するので to_i を使います。
# 入力
# 10
input = gets.to_i
puts input + 5
# 出力
# 15
他には、小数にする to_f や文字列に変換する to_s 、配列にする to_a などがあります。
参考
繰り返し
繰り返しには、以下のようなものがあります。
timeseachwhile
それぞれ具体例と一緒に解説します。
times
数値に対するメソッドです。
その数値の大きさ回数、繰り返します。
3.times do
puts "Hello"
end
# 出力
# Hello
# Hello
# Hello
each
複数の値のそれぞれに対して実行します。
["red", "blue", "green"].each do |color|
puts color
end
# 出力
# red
# blue
# green
while
条件式が満たされる間、繰り返し実行します。
条件式に使う値があれば、その更新を忘れないように注意が必要です。
i = 0
while i < 3
puts i
i += 1
end
# 出力
# 0
# 1
# 2
便利なメソッド
文字列の長さ、配列の要素数
length や size は、文字列の長さや配列の要素数を返してくれます。
str = "Hello"
puts str.length
# 出力
# 5
arr = ["red", "blue", "green"]
puts arr.length
# 出力
# 3
どちらも length を size に変えても、同じ結果を返します。
並び替え関連
sort, reverse
sort は、昇順に配列の要素を並び替えてくれます。
reverse は、並び順をひっくり返してくれます。
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"]
最大、最小：max, min
配列の要素の中で、最大や最小の値を返してくれるメソッドがあります。
最大値が max で、最小値が min です。
arr = [4, 5, 1, 3, 2]
puts arr.max
puts arr.min
# 出力
# 5
# 1
最初、最後：first, last
配列の要素の、最初と最後の値を返してくれるメソッドがあります。
最初が first で、最後が last です。
arr = [4, 5, 1, 3, 2]
puts arr.first
puts arr.last
# 出力
# 4
# 2
順列、組み合わせ
permutation で順列、
combination で組み合わせを生成できます。
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]]
たまに使うもの
最大公約数
gcd() というメソッドを、整数に対して使います。
ちなみに、最大公約数は英語で greatest common divisor です。
そのため gcd と略されています。
num = 9
puts num.gcd(6)
# 出力
# 3
最小公倍数
lcm() というメソッドを、整数に対して使います。
ちなみに、最小公倍数は英語で least common multiple です。
そのため lcm と略されています。
num = 9
puts num.lcm(6)
# 出力
# 18
素数
prime というライブラリを使います。
ちなみに、素数は英語で prime number です。
ライブラリを使うために require 'prime' を実行する必要があります。
# 入力
# 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文
num = gets.to_i
if num > 0
puts num
end
if文の書き方といえばこれが基本形かと思いますが、以下のように書くこともできます。
num = gets.to_i
puts num if num > 0
三項演算子
num = gets.to_i
if num > 0
puts num
else
puts 0
end
三項演算子というものを使うと、以下のように書くこともできます。
num = gets.to_i
puts num > 0 ? num : 0
OR
if x == "a" || x == "b" || x == "c"
# 処理
end
これをちょっとカッコよく書きたいと思ったら、以下のように書くこともできます。
if ["a", "b", "c"].include?(x)
# 処理
end
練習問題リンク
まとめ
Rubyと競プロの基本について書いてみました。
ぶっちゃけ、過去問を解きまくって慣れることができれば、茶色になることはそう難しくないと思います。
それでは、最後まで読んでいただき、ありがとうございました。