Rubyではじめる競技プログラミング入門 ~ 入出力編 ~
「フィヨルドブートキャンプ Part 2 Advent Calendar 2023」5日目の記事です。
Part1 はこちらです。
この記事はフィヨルドブートキャンプの受講生が少しでも競技プログラミングに親しめるように、最初の難関である入出力に関してまとめた記事になります。言語はRubyです。Rubyを使用している競技プログラマーは少ないので仲間を増やしたいという思いもあります。また、フィヨルドブートキャンプ受講生といいましたが、Rubyを知っていてまだ競技プログラミングをしたことがないような人にとってはためになるはずなので、zennというオープンなプラットフォームに書いています。
タイトルには競技プログラミングと書いていますが、競技プログラミングにはTopcoder, Codefacesなど様々なものがあります。ここではAtCoderという日本の競技プログラミングに絞って説明していきます。
本記事の活用方法
AtCoderの問題を解いたことがない人は、AtCoder Beginners Selectionにある問題を解くことををおすすめします。その中で入出力の方法で困ったら適宜参照してもらうのが良いでしょう。
ある程度問題を解いたことがある方は、「まとめ」を読んで知らないものがあれば都度該当する項を参照するのがおすすめです。
問題を解く流れ
まず、問題を解く流れを紹介します。
AtCoderなどの競技プログラミングでは入力が与えられ、アルゴリズムの利用などにより題意に沿った出力をするプログラミンを提出することで問題を解いていきます。
この中の最初と最後のプロセスが入力と出力です。この部分でつまずいてしまうとロジックを考えるという本質部分まで到達することなく挫折してしまうので今回記事にしました。
「書いてあること」と「書かないこと」
- 🙆♂️入力の受け取り方
- 🙆♂️出力の方法
上記に付け加えて、入出力と言っても様々ありますがAtCoderでよく使うという文脈に絞って紹介します。以下の内容は書いてありません。
- 🙅♂️Ruby以外の言語に関する入出力(I/O)
- 🙅♂️AtCoderに関すること全般(登録のしかたや、問題の解き方)
- 🙅♂️計算量について
入力について
1行の入力を受け取る
標準入力から1行分の入力を受け取るにはgetsメソッドを使用します。
# 標準入力
atcoder
# ruby script
p gets
#=> "atcoder\n"
AtCoderでは入力の各行の末尾に改行文字が入っています。改行文字を扱いたい場面は少なく、このままでは使い勝手が悪いので実際にはchompメソッドを使って改行コードを削除することが多いです。gets.chompまでをセットで覚えておくことをおすすめします。
# 改行コードが取り除かれる
str = gets.chomp
# => "atcoder"
入力を数値(整数、小数、有理数など)として扱いたい場合はgetsメソッドだけではうまくいきません。getsメソッドは文字列として受け取るメソッドなのでこのまま数値との計算を行うとTypeErrorになります。また、同じようにして受け取った入力同士を足し合わせると文字列の結合となります。
# 標準入力
42
43
# ruby script
num1 = gets.chomp
num2 = gets.chomp
num1 + 43
#=> `+': no implicit conversion of Integer into String (TypeError)
num1 + num2 #=> "4243" ("42" + "42")←文字列の結合
数値として受け取りたい場合はto_iメソッドなどをチェーンして整数(Integer)に変換する必要があります。
# 標準入力
42
# ruby script
num = gets.to_i
p num # => 42 ←integer
もちろん小数点などはto_f、有理数ならto_rをメソッドチェーンして入力を受け取ります。
float_num = gets.to_f
p float_num #=> 42.0
rational_num = gets.to_r
p rational_num #=> (42/1)
筆者は、入力が小数で与えられているのにto_iしてコードを提出してしまい、WA(wrong answerの略)するやらかしを何度もしてしまったので、どの型に変換するのかしっかり問題文を読みましょう。以下、to_iを基本としてコードを提示しますが、問題文に応じて適切に変換してください。
複数行の入力を受け取る
与えられた入力が複数行あるときはどうすれば良いでしょうか？
あらかじめ行数が固定されているなら、行数分getsメソッドを呼び出すのが一番簡単です。
以下は、3行の標準入力を受け取る場合です。
# 標準入力
guitar
piano
tambourine
# ruby script
str1 = gets.chomp #=> "guitar"
str2 = gets.chomp #=> "piano"
str3 = gets.chomp #=> "tambourine"
しかし、ほとんどの問題は与えられる入力の行数が入力ケース毎に変わります。その場合の方法は後述します。(配列を受け取る(複数行)を参照してください)
配列で受け取る
意味のあるまとまった複数の値はひとまとめにして配列として受け取ることがあります。
以下の入力例のように1行で複数の値が与えられるときは配列の出番です。各値の区切りとして半角スペースが使われることが多く、この場合はsplitメソッドを使います。splitメソッドはデフォルトでスペース(や改行コード)で文字列を区切ってくれます。
# 標準入力
12 32 77 64
#ruby script
scores = gets.split.map(&:to_i) #=> [12, 32, 77, 64]
数値で受け取る場合は配列の各要素に対してto_iメソッドを呼び出したいのでmap(&:to_i)としています。&と:method_nameを使った短縮系（という呼び方で良いのか？）で呼び出していますが、map{ |value| value.to_i }と同じです。詳しくはRubyの入門書などを参照ください。
もちろん、配列の各要素を文字列として受け取りたい場合はmapによる型の変換は必要ないです。その代わりchompを忘れずに!
# 標準入力
aaa bbb ccc ddd
# ruby script
strs = gets.chomp.split #=> ["aaa", "bbb", "ccc", "ddd"]
splitの引数を指定すると区切り文字(セパレータ)を指定できます。
# 標準入力
aaa:bbb:ccc:ddd
# ruby script
strs = gets.chomp.split(':').map(&:to_i) #=> ["aaa", "bbb", "ccc", "ddd"]
splitメソッドは色々面白いメソッドなので気になった方はリファレンスマニュアルを参照してください。
複数行のまとまった値も同じようにして配列で受け取ると便利なことが多いです。
たとえば、
どの入力ケースでもgetsメソッドで受け取ります。(文字列のところの説明と同じです)
# 標準入力
42
18
79
# ruby script
score1 = gets.to_i
score2 = gets.to_i
score3 = gets.to_i
scores = [score1, score2, score3] #=> [42, 18, 79]
しかし、入力ケースによって
先ほどのやり方では入力ケース毎に行数変わる問題を解決できません。getsメソッドをいくつ書いて良いかわからないからです。
# 行数がわからないのでいくつ書けば良いのか、、、
gets.to_i
gets.to_i
gets.to_i
gets.to_i
...
...
gets.to_i
問題によるのですが、入力の最初に
# 標準入力
5 # 人数N(行数)が与えられる
11 # ←以下試験の点数
28
98
32
64
# ruby script
# 行数はまず取得しておく
n = gets.to_i #=> 5
# 標準入力の2行目以降を配列で受け取る
scores = Array.new(n) { gets.to_i } #=> [11, 28, 98, 32, 64]
Array.newの引数で要素数を指定します。ブロックを渡して実行すると配列の各要素の値をブロックの評価結果として設定します。
timesメソッドとmapメソッドを用いて以下のように書いても同じように配列が取得できます。
n = gets.to_i
scores = n.times.map do
gets.to_i
end
#=> [11, 28, 98, 32, 64]
# ワンラインで書くと
n = gets.to_i
scores = n.times.map { gets.to_i }
#=> [11, 28, 98, 32, 64]
数値や文字列を1文字ずつ分割したい
多少、番外編になります。
たとえば、abcという文字列をa, b, cと1文字ずつ分割したかったり、123という数値を1, 2, 3と桁毎に分割したい場合があります。そのような場合は以下のようにします。
# 標準入力
abcde
12345
# ruby script
#文字列を1文字ずつ分割
characters = gets.chomp.chars #=> ["a", "b", "c", "d", "e"]
# 数値を1文字ずつ分割
digits = gets.chomp.chars.map(&:to_i) #=> [1, 2, 3, 4, 5]
# もしくは
digits = gets.to_i.digits #=> [5, 4, 3, 2, 1]
文字列を分割するにはcharsメソッドが便利です。
数値を分割するには主に2パターンあって、文字列を分割してから各要素を数値にするパターンと、Integer#digitsメソッドを使うパターンがあります。
digitsメソッドは一の位、十の位、百の位、、、という並び順になることに注意してください。
ここに挙げたのは一例ですので他の方法も考えてみてください！
出力
入力と比べて出力については非常に簡単です。基本的にはputsメソッドを使えば大丈夫です。
# 標準出力(こんな感じで出力したい)
42
# ruby script
answer = 42
puts answer
#=> 42
複数の値を1行で出力したい場合は配列に対してjoinメソッドを呼び出します。[1]
# 標準出力（こんな感じで出力したい)
12 34 56
aaa bbb ccc
# ruby script
answer = [1, 2, 3, 4]
answer2 = ["aaa", "bbb", "ccc"]
puts answer.join(' ')
#=> 12 34 56
puts answer2.join(' ')
#=> aaa bbb ccc
数値に限ってはpメソッドでも大丈夫ですが、文字列に対してpメソッドで出力するとリテラルの"(クォート)などが残ってしまいテストケースが通らないので気をつけてください。(僕は何度もやらかしました😇)
他にも必要に応じて文字列の中で式展開したり、rjustメソッドやstrfメソッドなどでフォーマットを整える場面があるかもしれないですが、これは文字列特有の問題なので割愛します。
出力に関しては以上です。
応用編
ここからは応用編です。基本的には上で紹介した方法で困ることはないのですが、特殊な入力や簡潔な方法が他にもあるので紹介しておきます。簡潔だが簡単ではないので、、、
2次元配列で受け取る
その場合は2次元配列で入力を受け取ると便利です。
# 標準入力
4 5 # 4行 5列という情報
oooxx
xoxox
ooooo
xxxxx
# ruby script
# 配列を多重代入によってh, wに代入している
h,w = gets.split.map(&:to_i) #=> [4, 5]
grid = Array.new(h) { gets.split.map(&:to_i) }
#=> [["o", "o", "o", "x", "x"], ["x", "o", "x", "o", "x"], ["o", "o", "o", "o", "o"], ["x", "x", "x", "x", "x"]]
多重代入というテクニックを使って配列を分割して代入しています。多重代入に関しは以下の記事を参考にしてください。
Array.newの部分はtimes.mapで置き換え可能です。
ARGFによる標準入力の受け取り
ここら少しマニアックになってきます。
複数行(2行)にわたる入力を一括で取りたいときは以下のようにARGFを使ったテクニックがあります。
# 標準入力
5
12 32 67 89 100
# ruby script
n, *a = ARVF.read.split.map(&:to_i) #=> [5, 12, 32, 67, 89, 100]
p n #=> 5
p a #=> [12, 32, 67, 89, 100]
ポイントは2つあります。1つ目は*aの部分。これは、変数の前にアスタリスクをつけることで配列として受け取ることができます。 n, *aとなっているので1つ目の要素はnに代入され、残りは全てaに代入されます。
2つ目はARGFです。ARGFの説明はややこしいので飛ばしたいですが、簡単に説明します。
ARGFはARGVに入っている要素をファイル名と見なして、ファイル同士を連結して作った仮想ファイルを表すオブジェクトです。
じゃあARGVはなんだっていう話ですが、ARGVはスクリプトに引数で渡した値が格納されています。
$ ruby sample.rb aaa bbb ccc
rubyコマンドでスクリプトを実行した場合aaa, bbb, cccが引数としてみなされARGVという特殊な配列に格納されます。
ARGFはこれを連結して1つの仮想ファイルとしてみなすわけです。
ここまでの説明は実はどうでもよくてARGFはARGVの中身が空の場合標準入力を受け取るという決まりがあるのでその特性を利用しています。
# 引数なしの場合 ARGVは空になる→ARGFは標準入力から入力を受け取る
$ ruby sample.rb
そしてここからが本題です。
ARGFは$<という組み込み変数（特殊変数ともいう）が存在してるのでARGFを$<で置き換えることができます。
n, *a = $<.read.split.map(&:to_i)
筆者は便利なのでこの形をよく使います。コンテストに参加するといかに早く解くかというのがスコアに大きく影響する[2]ので出来るだけタイプ数を減らしたいからです。(コードゴルフや早く解くという目的がない場合は無理に使う必要はありません。)
複数行を一括で処理するという方法は他にもありますので是非研究してください。
ddコマンドによる入力の受け取り
最後にちょっとトリッキーな方法を紹介します。
Unixのコマンドにddというのがあります。RubyからUnixコマンドを呼び出す方法はいくつかありますが、その1つにバッククォーとで囲むという方法があります。
# バッククォーとで囲むとコマンドが実行される
puts `ls -a ./`
# => 自分の環境のディレクトリ配下のファイル名が出力される
応用してddコマンドで入力を取るのは以下ようにします。入力れいはARGFの時と同じ
n, *a = `dd`.split.map(&:to_i)
p n #=> 5
p a #=> [12, 32, 67, 89, 100]
筆者はなんだかRubyの力っぽくないという変なこだわりでこれは使ってません、笑
まとめ
最後に入出力についてまとめておきます。
# 1行の入力を受け取る
str = gets.chomp # 文字列
num = gets.to_i # 整数
# 複数行の入力を受け取る（文字列)
str1 = gets.chomp
str2 = gets.chomp
str3 = gets.chomp
# 1行に複数ある値を配列に詰めて受け取る
numbers = gets.split.map(&:to_i)
strings = gets.chomp.split
# 複数の値を個別に受け取る(多重代入)
a, b = gets.split.map(&:to_i)
# n行の入力を受け取る
numbers = Array.new(n) { gets.to_i }
strings = Array.new(n) { gets.chomp }
# 1文字、1桁ずつ区切って配列にする
characters = gets.chomp.chars
digits1 = gets.chomp.chars.map(&:to_i)
digits2 = gets.digits
応用編
# 二次元配列として受け取る(h行w列)各要素は整数を想定
grid = Array.new(h) { gets.split.map(&:to_i) }
# 複数行をまとめて受け取る
n, *a = $<.read.split.map(&:to_i)
n, *a = `dd`.split.map(&:to_i)
出力
# 出力
num = 42
puts num
p num
str = 'atcoder'
puts str
puts ary.join(' ')
参考
この記事では参照していませんが、おすすめのものを紹介します。
過去問が載っています。
パフォーマンスを意識したい人はこの記事がわかりやすいです。
Discussion