AtCoder に登録したら解くべき精選過去問 10 問を Ruby・Crystal の両方で動くコードで解いてみた

はじめに

RubyとCrystalの両方で動くコードで、@drken さんの AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～を解いてみました。

問題が難しくないので、奇妙なことをほぼせず、すんなり解けました。

1つだけコード長が変わっていますが末尾の改行の有無などの違いで、内容は同じです。
かなり速度差があるように見えるのもありますが、Rubyの場合はコードの内容にかかわらず最低50msほどかかるみたいです。

RubyとCrystalの両方で動くコードが使えると何が嬉しいか。
それぞれに長所短所があり、切り替えて使えます。
また、今回のように簡単な問題だと、全く同じコードで2回ACできます!!(自己満足)

Ruby:
難しい問題だと実行時間が厳しくなることもありますが、調べやすくシンプルにスマートに書きやすい。

Crystal:
キャッチフレーズは"Fast as C, Slick as Ruby"。
C言語のように速く、Rubyのように滑らかに・柔軟に書くことが出来ます。
オーバーフローの注意を払う必要があったり、情報にアクセスしにくいこと等が欠点ですが、
Rubyと文法等が非常に似ており、Ruby学習者にとって非常に学習コストが低いです。

▼AtCoderの公式ページでのまとめ
問題 - AtCoder Beginners Selection
問題 - Language Test 202001
こちらで問題を解けますし、他の方のコードはこちらから見れます。

▼先行Ruby記事
AtCoder に登録したら解くべき精選過去問 10 問を Ruby で解いてみた - Qiita
AtCoder に登録したら解くべき精選過去問 10 問を Ruby で解いてみた (しえる版) - Qiita
AtCoder に登録したら解くべき精選過去問 10 問を Ruby のメソッドチェーンで解いてみた - Qiita
Atcoder Beginners SelectionをRubyで解いてみた - Kasasagi’s memorandum
AtCoder に登録したら解くべき精選過去問 10 問を Ruby で解いてリファクタリングする | マッスルテック
色々な方が解いています。この他にも解説記事があるかもしれません。

▼先行Crystal記事
AtCoder に登録したら解くべき精選過去問 10 問を Crystal で解いてみた - Qiita

▼同様の他言語のまとめ記事
百花繚乱！なないろ言語で競技プログラミングをする資料まとめ - Qiita

Ruby, Crystalのそれぞれに同じ問題の解説記事をあげてる方がいるので、詳細な解説などはそちらをご覧ください。

練習：A - Welcome to AtCoder

a   = gets.to_s.to_i
b,c = gets.to_s.chomp.split.map{|t| t.to_i }
s   = gets.to_s.chomp

puts "#{a+b+c} #{s}"

getsは「get string」の略で、一行を入力として受け取り文字列で返します。ただし、もし入力がなければ、nilを返します。競技プログラミングの場合、イレギュラーな入力は通常なく、正しく実装して入力を受け取ればgetsは文字列を返すのでnilを返すことはないです。
しかし、Crystalの場合、もしto_sがないとundefined method 'to_i' for Nil (compile-time type is (String | Nil))と怒られてしまいます。どうもgetsはStringかNilを返す可能性があり、コンパイル時に「nilだったらto_iのメソッドを持たない!」と怒られているようです。そのため、to_sで文字列のみ返すように明示してあげています。
なお、RubyのString#to_sのリファレンスマニュアルにおいて、to_sは文字列やnilを返すメソッドに有効である旨が書かれており、想定の技法のようです。
他にも, 変態ですが同様に"#{gets}"と式展開することで文字列にする方法もあるみたいです。難しい話ですが、式展開された最後に内部でto_sが使われているようです。
また、getsの挙動もRubyとCrystalで微妙に異なっています。Rubyではgetsが1行を読み込んだときに最後に改行があれば受け取りますが、Crystalでは改行を切り捨てます。そのため、Crystalでは文字列のときにchompメソッドをする必要がないといえます。

# それぞれ最後に改行がある"abc"を入力として受け取ったとき
p gets.to_s #=> "abc\n" for Ruby
p gets.to_s #=> "abc"   for Crystal

	Ruby	Crystal
gets	末尾に改行があれば含んで返す	末尾の改行は切捨てて返す
nil.to_i	0を返す	nilに定義なく、コンパイル時にエラー

あと、Crystalでよく使われる入力方法にread_lineがありますが、Rubyではreadlineと微妙に名称が異なっています。他のメソッド名と同じように単語の区切りにアンダースコア_を持たせたいと考えたのかもしれません。なお、getsと違いread_lineは入力がなかったときにエラーを返す仕様のため、nilを返すことはないです。

また、ここで注目したいのはmap{|t| t.to_i }です。RubyでもCrystalでも引数を持たないメソッドの場合の略記がありますが、何故か微妙に異なっています。
Rubyならmap(&:to_i)、Crystalならmap(&.to_i)です。

さらに、Rubyにはmapの別名の同機能でcollectが存在しますが、Crystalはmapのみです。map/collectと同じ関係性のものとして 下記のようなものが挙げられます。

Crystalにある	Crystalにない	備考
map	collect
size	length
reduce	inject
select	find_all, filter	Enumerable
find	detect
index	find_index
push	append	appendは Ruby v2.5-
unshift	prepend	prependは Ruby v2.5-
first	take	Array#first, Enumerable#take
reject!	delete_if
each	each_pair	Hash
select!	keep_if, filter!
has_key?	key?, include? member?
has_value?	value?
merge!	update

Crystalではエイリアス(別名)を持たせない方針・慣習のため、後者のメソッドが定義されていないです。
例外はあるものの、結果的にはその多くが短い名称のものが採用されいる印象です。

第 1 問: ABC 086 A - Product (100 点)

a, b = gets.to_s.chomp.split.map{|t| t.to_i }

puts ( a * b ).odd? ? "Odd" : "Even"

C言語などを知っている人であればわかりやすいですが、Crystalには文字と文字列があります。
Rubyの場合、\nなどの特殊文字や式展開#{``}を使用したいときはダブルクォート、したくないときはシングルクォートで文字列を囲み、関係ない場合はどちらを使っても問題なかったと思います。
しかし、Crystalは、ダブルクォートは文字列、シングルクォートは(1文字の)文字と決まっています。もし、"Odd"を'Odd'と書くとunterminated char literal, use double quotes for strings(文字列にはダブルクォートを使え!)と怒られてしまいます。
2文字以上のものにダブルクォートを使うようにし、文字か文字列か意識するようにすると良いです。

	Ruby	Crystal
シングルクォート'~'	文字列。特殊文字や式展開が使えない。	1文字の文字。文字列とは異なる
ダブルクォート "~"	文字列。特殊文字や式展開が使える。	文字列

第 2 問: ABC 081 A - Placing Marbles (100 点)

s = gets.to_s.chomp

puts s.count("1")

色々方法がありますが、与えられた文字列の1を数えるだけです。
Crystalには文字と文字列の区別がありますが、今回は1文字なので'1'でも"1"でもどちらでも大丈夫です。
ちなみに、Rubyでは1文字の文字列は?1と変わった書き方ができますが、Crystalにはありません。

ところで、数えるのではなく、含むかどうか、を返してもらいたいときは以下です。

"101".include?("1")  # Ruby
"101".includes?("1") # Crystal

Crystalでは、メソッド名が三人称単数形に変わっています。
きっと欧米圏の人から見て三人称単数形の方が自然ということでしょう。
他にもRubyのstart_with?/end_with?などのメソッドが、Crystalでは三人称単数形のstarts_with?/ends_with?になっています。
また、RubyのHashにhas_key?, has_value?という要素を持つか調べて返す三人称単数形のメソッドがあり原形に統一しきれておらず、Crystal側ではメソッド名の統一感がでていると思います。
ただ、変数名がelementsのような複数形だとelements.includes?(x)はやはり誤りとなってしまうようです。

第 3 問: ABC 081 B - Shift Only (200 点)

n = gets.to_s.to_i
a = gets.to_s.chomp.split.map{|t| t.to_i }

ans = 0
while a.all?{|t| t.even? }
  a = a.map{|t| (t/2).to_i }
  ans += 1
end

puts ans

問題文通りにシミュレーションしています。

ここで注目しておきたいのはwhile文です。
Rubyではwhile文の条件のあとにdoがあってもなくても動きますが、Crystalにはあってはいけません。もしdoを書くと、unexpected token: do(予期せぬdoだ!)と怒られます。
反対のuntil文のdoも同様です。メソッド名のエイリアスもそうですが、良くも悪くも多様な書き方が認められていない感じは、Pythonみたいですね(?)
話が逸れますが、while/untilは予約語であるのに対し、loopはメソッドでありRubyでもCrystalでもブロックを作るためにdoを書く必要があります。

次に、割り算について。
Crystalのバージョンが0.24の頃は整数同士の割り算n/mは、小数部分が切り捨てられた整数が返ってきていました。しかし、v0.33の今は、n/mだと小数付きで返り、n//mで整数が返ります。Python2からPython3で変更になったのと全く同じ流れですね。他に、Nim, Haskell, Perlなどもこの仕様らしいです。
Rubyと異なるところなので、気をつけましょう。割り算をしたあとにto_iメソッドを用いることで、Crystalででた小数部分を切り捨て整数値を返しています。Rubyは整数値にto_iを使っても同じ整数値が返るだけで、問題はありません。

p 1 / 3 # => 0                  # Ruby, Crystal v0.24
p 1 / 3 # => 0.3333333333333333 # Crystal v0.31

第 4 問: ABC 087 B - Coins (200 点)

a = gets.to_s.to_i
b = gets.to_s.to_i
c = gets.to_s.to_i
x = gets.to_s.to_i

ans = 0
(a+1).times do |i|
  (b+1).times do |j|
    (c+1).times do |k|
      ans += 1 if x == 500 * i + 100 * j + 50 * k
    end
  end
end

puts ans

素朴なコードですね。
三重ループで全探索をして答えを見つけています。

他の言語でループといえば、for文がよく使われます。
しかし、Rubyでは好まれて書かれない印象です。
また、Crystalには、そもそもfor文はなさそうです。
回したりループさせたいときは、while文/until文や、times, upto, downto, each, each_with_index, step, loopなどのメソッドを駆使しましょう。ただ、stepは、Crystalだとキーワード引数にしないといけなかったような気がします。

第 5 問: ABC 083 B - Some Sums (200 点)

n, a, b = gets.to_s.chomp.split.map{|t| t.to_i }
 
ans = 0
(1..n).each do |i|
  s = i.to_s.chars.map{|t| t.to_i }.sum
  ans += i if a <= s && s <= b
end
 
puts ans

以前のAtCoderのRubyのバージョンは2.3と古かったため配列のsumメソッドが使えなかったのですが、今はv2.7でsumメソッドが使え簡単に合計を取ることが出来ます。
ちなみに、Rubyでsumメソッドが使えなかった頃はinject(:+)かreduce(:+)と書くのが普通でしたが、Crystalにはinjectという名称がなくreduceのみです。さらにreduce(:+)という記法がないため、両者で動くコードを書くにはreduce(0){|s,t|s+t}などの書き方が必要でした。ちなみに、Rubyではdo~endではなく{~}を使ったときは引数をいれる()を省略するとエラーになるのですが、Crystalだと動くみたいです。つまり、reduce 0 {|s,t|s+t}はRubyでは動かないけれど、Crystalでは動きます。

そして、Rubyには優先順位が最も低いand/orがありますが、Crystalにはないみたいです。
&&/||を使いましょう。
なお、Rubyはs.between?(a,b)、Crystalはa <= s <= bという別の書き方が出来ます。Crystalの方は嬉しいですね。一方、Rubyのbetween?メソッドは、あまり使われているところを見たことがないですね。境界に引数を含むことを知っておく必要があり少し煩わしそうです。

	Ruby	Crystal
論理	and, or, notがある	&&, || , ! のみ
条件式	between?メソッドあり	a <= s <= bと書ける

第 6 問: ABC 088 B - Card Game for Two (200 点)

n = gets.to_s.to_i
a = gets.to_s.chomp.split.map{|t| t.to_i }.sort.reverse

ans = 0
a.each_with_index{|t,i| ans += i.even? ? t : -t }

puts ans

特筆すべきことはないですね。
ふつうRubyで競プロする場合、getsがnilを返すことは想定されないため、getsの後にto_sを挟みはしないですが。

sortで昇順に並び替えて、reverseでひっくり返し逆順にして、大きい順に並び替えています。
2人の得点の差異をだしたいため、Aliceのは加算して、Bobのは減算しています。

第 7 問: ABC 085 B - Kagami Mochi(200 点)

n = gets.to_s.to_i
a = Array.new(n){ gets.to_s.to_i }

puts a.uniq.size

縦にn行の入力について、Rubyではn.times.map{ gets.to_s.to_i }という書き方をよく目にしますが、Crystalでは動きません。両方で動く書き方はArray.new(n){ gets.to_s.to_i }とします。

最後の配列の長さを返しているsizeについて。Rubyではlengthという同機能の別名が定義されていますが、Crystalにはありません。
他に、Rubyの配列の長さは引数なしのcountメソッドでも一応返りますが、Crystalにはありません。

第 8 問: ABC 085 C - Otoshidama (300 点)

n,y = gets.to_s.split.map{|t| t.to_i }

y = ( y / 1000 ).to_i

(0..(y/5).to_i).each do |j|
  (0..(y/10).to_i).each do |i|
    c = y - (10 * i + 5 * j )
    break if c < 0
    if i + j + c == n
      puts "#{i} #{j} #{c}"
      exit
    end
  end
end

puts "-1 -1 -1"

整数どうしの割り算はn/mは、Rubyでは整数が返り、いまのCrystalでは浮動小数点数で返ります。
(Crystalがv0.24の頃の同じ挙動でしたが、v0.31になったあたりで変わって異なったようです)
そのため、両方で動くコードを書くときは、割った後にto_iを忘れないようにしましょう。

Ruby 317ms、Crystal 18ms
10倍以上差がでています。Rubyは二重ループや二次元配列周りが遅い印象を受けます。

それから、後置でない普通のif文について、Rubyでは条件式のあとにthenを書いても書かなくても動きますが、Crystalでは書いてしまうと動かないです。while文/until文のdoと同じですね。

第 9 問: ABC 049 C - Daydream (300 点)

s = gets.to_s.chomp

%w(eraser erase dreamer dream).each{ |w| s = s.gsub(w," ") }
s = s.gsub(" ","")

puts s == "" ? "YES" : "NO"

Crystalの文字列は1度代入すると変更できません。そのため、Rubyの破壊的メソッドであるgsub!がないようで、gsubで返り値をだして代入し直しています。なお、同じように、参照するString#[]はありますが、変更するためのString#[]=はCrystalにありません。

	Ruby	Crystal
文字列	変更できる	変更できない

第 10 問: ABC 086 C - Traveling (300 点)

n = gets.to_s.to_i
 
flag = true
ot = ox = oy = 0
n.times do |i|
    
    t,x,y = gets.to_s.split.map{|t| t.to_i}
    dt = t - ot
    dx = (x-ox).abs
    dy = (y-oy).abs
    
    r = dt - dx - dy
    if r < 0 || r.odd?
        flag = false
        break
    end
    
    ot, ox, oy = t, x, y
end
 
puts flag ? "Yes" : "No"

特筆すべきところはないですね。
余談ですが、大文字始まりはどちらも定数ですが、Crystalの場合に定数に多重代入しようとするとエラーがでます。

さいごに

今回の問題は簡単だったので、入力周りを変更するだけでRubyでもCrystalでも動くような問題も多かったです。

しかし、Crystalでは標準的なInt32という32bit整数で収まらない問題の場合、Int64bitの整数型を指定する必要があり、0ではなく、0_i64や0i64などのように書きまくる必要があるケースもあります。もし、どうしてもRubyでもCrystalでも動かせるコードを作りたければ、32bitで収まらない整数値を与えてあげると、Crystal側で64bit整数だろうと判断してくれるので、それを用いると良いと思います。

p z64 = 9876543210 - 9876543210 # 0_i64
p e64 = z64 + 1                 # 1_i64

あくまで遊びの範囲でこんな方法がありますよ、ってことで。