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

# はじめに

RubyとCrystalの両方で動くコードで、@drken さんの [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067#5-%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-10-%E5%95%8F)を解いてみました。

問題が難しくないので、奇妙なことをほぼせず、すんなり解けました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211503/34e354ba-3648-db90-e592-dc3567974faf.png)
1つだけコード長が変わっていますが末尾の改行の有無などの違いで、内容は同じです。
かなり速度差があるように見えるのもありますが、Rubyの場合はコードの内容にかかわらず最低50msほどかかるみたいです。

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

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

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

▼AtCoderの公式ページでのまとめ
[問題 - AtCoder Beginners Selection](https://atcoder.jp/contests/abs/tasks)
[問題 - Language Test 202001](https://atcoder.jp/contests/language-test-202001/tasks)
こちらで問題を解けますし、他の方のコードはこちらから見れます。

▼先行Ruby記事
[AtCoder に登録したら解くべき精選過去問 10 問を Ruby で解いてみた \- Qiita](https://qiita.com/d_nishiyama85/items/f79e034f6dcd4175cdc1)
[AtCoder に登録したら解くべき精選過去問 10 問を Ruby で解いてみた \(しえる版\) \- Qiita](https://qiita.com/cielavenir/items/c0a45b6b87c411b60b93)
[AtCoder に登録したら解くべき精選過去問 10 問を Ruby のメソッドチェーンで解いてみた \- Qiita](https://qiita.com/phocom/items/c94a0fba2c04f9e7a8f8)
[Atcoder Beginners SelectionをRubyで解いてみた \- Kasasagi’s memorandum](http://yh9092.hatenablog.com/entry/2018/03/22/165608)
[AtCoder に登録したら解くべき精選過去問 10 問を Ruby で解いてリファクタリングする \| マッスルテック](https://muscletech.tokyo/atcoder-%E3%81%AB%E7%99%BB%E9%8C%B2%E3%81%97%E3%81%9F%E3%82%89%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E7%B2%BE%E9%81%B8%E9%81%8E%E5%8E%BB%E5%95%8F-10-%E5%95%8F%E3%82%92-ruby-%E3%81%A7%E8%A7%A3%E3%81%84/)
色々な方が解いています。この他にも解説記事があるかもしれません。

▼先行Crystal記事
[AtCoder に登録したら解くべき精選過去問 10 問を Crystal で解いてみた \- Qiita](https://qiita.com/tomerun/items/23ce2a2ed6ead291d222)

▼同様の他言語のまとめ記事
[百花繚乱！なないろ言語で競技プログラミングをする資料まとめ - Qiita](https://qiita.com/drken/items/6edb1c0542d4c3b7179c)

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

# 練習：[A - Welcome to AtCoder](https://atcoder.jp/contests/practice/tasks/practice_1)

```Crystal
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のリファレンスマニュアル](https://docs.ruby-lang.org/ja/latest/method/String/i/to_s.html)において、`to_s`は文字列や`nil`を返すメソッドに有効である旨が書かれており、想定の技法のようです。
他にも, 変態ですが同様に`"#{gets}"`と式展開することで文字列にする方法もあるみたいです。難しい話ですが、式展開された最後に内部でto_sが使われているようです。
また、`gets`の挙動もRubyとCrystalで微妙に異なっています。Rubyではgetsが1行を読み込んだときに最後に改行があれば受け取りますが、Crystalでは改行を切り捨てます。そのため、Crystalでは文字列のときに`chomp`メソッドをする必要がないといえます。

```Ruby
# それぞれ最後に改行がある"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](https://atcoder.jp/contests/abc086/tasks/abc086_a) (100 点)

```Crystal
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](https://atcoder.jp/contests/abc081/tasks/abc081_a) (100 点)

```Crystal
s = gets.to_s.chomp

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

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

```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](https://atcoder.jp/contests/abc081/tasks/abc081_b) (200 点)

```Crystal
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`を使っても同じ整数値が返るだけで、問題はありません。

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

# 第 4 問: [ABC 087 B - Coins](https://atcoder.jp/contests/abc087/tasks/abc087_b) (200 点)

```Crystal
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](https://atcoder.jp/contests/abc083/tasks/abc083_b) (200 点)

```Crystal
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`がある|`&&`, &#124;&#124; , ! のみ|
| 条件式|`between?`メソッドあり |`a <= s <= b`と書ける|


# 第 6 問: [ABC 088 B - Card Game for Two](https://atcoder.jp/contests/abc088/tasks/abc088_b) (200 点)

```Crystal
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](https://atcoder.jp/contests/abc085/tasks/abc085_b)(200 点)

```Crystal
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](https://atcoder.jp/contests/abc085/tasks/abc085_c) (300 点)
```Crystal
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](https://atcoder.jp/contests/abc049/tasks/arc065_a) (300 点)
```Crystal
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](https://atcoder.jp/contests/abc086/tasks/arc089_a) (300 点)

```Crystal
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整数だろうと判断してくれるので、それを用いると良いと思います。

```Crystal
p z64 = 9876543210 - 9876543210 # 0_i64
p e64 = z64 + 1                 # 1_i64
```
あくまで遊びの範囲でこんな方法がありますよ、ってことで。