AtCoder に登録したら解くべき精選過去問 10 問を Crystal で解いてみた

# はじめに

AtCoderでCrystalでのAC数1位の者です (2018-03-21現在。[参照:AtCoder Problems](https://kenkoooo.com/atcoder/?user=tomerun&kind=user#/lang)) 。

[AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067) で紹介されている10問をCrystalで解いてみました。

問題内容の説明などは元記事の方を参照してください。

# Crystalとは

https://crystal-lang.org/

"Fast as C, slick as Ruby" をスローガンに開発されているプログラミング言語です。
Rubyにそっくりな文法と標準ライブラリを持ちながら、ネイティブコンパイルして実行するので速い、という点が特長です。
Rubyを知ってい（てコンパイルと静的型付けを受け入れることができ）る人ならすぐに書けるようになると思います。静的型付けと言っても、かなりコンパイラが推論するので少なくとも競技プログラミングの範囲では自分で型を書くことはほとんどありません。
競技プログラミングの問題にはLLでは実行時間的に厳しいものも多いですが、CrystalならRubyの書きやすさを保持しつつ実行速度も問題ない、ということで、もうちょっと流行ってもいいんじゃないかと思っています。

利用できるオンラインジャッジとしては、[AtCoder](https://atcoder.jp/) や [yukicoder](http://yukicoder.me/) があります。
（ただし、現在AtCoderではコンパイルに最適化オプションがついていないため、そんなに速くなかったりします。次回の言語アップデート時に要望を出す予定）

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

```rb
a, b = read_line.split.map(&.to_i)
puts a * b % 2 == 0 ? "Even" : "Odd"
```
一行にスペース区切りで含まれた複数の整数を受け取る `read_line.split.map(&.to_i)` は、イディオムとして今後もしょっちゅう出てきます。

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

```rb
puts read_line.chars.count('1')
```

`String#chars` で `Array(Char)` が得られます。
`''` で囲った値は `Char` 型のリテラルです。

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

```rb
n = read_line
a = read_line.split.map(&.to_i)
ans = 0
while a.all? { |i| i % 2 == 0 }
  ans += 1
  a.map! { |i| i / 2 }
end
puts ans
```
素直にシミュレーションします。

別の方法：2進数で最後に連続する `'0'` の数を数えます。 `trailing_zero` みたいなメソッドはないので、かわりに文字列化して `'1'` の位置を探しました。

```rb
n = read_line
a = read_line.split.map(&.to_i)
puts a.map { |i| i.to_s(2).reverse.index('1').not_nil! }.min
```

`not_nil!` というメソッドを呼んでいるのは、 `index()` の戻り値が `(Int32｜Nil)` という型であるためです。
そのままだと `a.map{...}` の戻り値の型が `Array(Int32|Nil)` になり、 `min` の呼び出しがコンパイルエラーになります（Nil安全性）。
今回はかならず `'1'` が含まれることがわかっているため、 `not_nil!` で `(Int32|Nil)` を `Int32` にキャストします。もし値が `nil` だった場合は実行時エラーになります。

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

```rb
a = read_line.to_i
b = read_line.to_i
c = read_line.to_i
x = read_line.to_i
ans = 0
0.upto(a) do |i|
  0.upto(b) do |j|
    0.upto(c) do |k|
      ans += 1 if i * 500 + j * 100 + k * 50 == x
    end
  end
end
puts ans
```
3重ループを回します。

別の方法： `Arrays#product` で積集合を作ります。
`ba.product(ca)` の型は `Array(Tuple(Int32, Int32))` になり、`aa.product(ba.product(ca))` の型は `Array(Tuple(Int32, Tuple(Int32, Int32)))` です。

```rb
a = read_line.to_i
b = read_line.to_i
c = read_line.to_i
x = read_line.to_i
aa = 0.upto(a).to_a
ba = 0.upto(b).to_a
ca = 0.upto(c).to_a
puts aa.product(ba.product(ca)).select { |ai, bc| ai * 500 + bc[0] * 100 + bc[1] * 50 == x }.size
```

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

```rb
n, a, b = read_line.split.map(&.to_i)
puts(1.upto(n).select do |i|
  s = i.to_s.chars.map { |c| c.to_i }.sum
  (a..b).includes?(s)
end.sum)
```
`do~end` は結合の優先度が引数の区切りより弱いので、 `puts xxx do ... end` と書くと、 `puts` には `xxx` と `do~end でできるブロック` の2つの引数が渡ってしまいます。
これを避けるために括弧でくくっています。Rubyでも同じですね。

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

```rb
n = read_line
a = read_line.split.map(&.to_i).sort.reverse
puts a.each_slice(2).map { |e| e.size == 1 ? e[0] : e[0] - e[1] }.sum
```

`each_slice(2)` で、要素を2個ずつ受け取ることができます。

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

```rb
n = read_line.to_i
d = Array.new(n) { read_line.to_i }
puts d.uniq.size
```

`Array.new` にブロックを渡すことで、Arrayの初期値を設定できます。

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

```rb
n, y = read_line.split.map(&.to_i)
a, b, c = -1, -1, -1
0.upto(n) do |i|
  0.upto(n - i) do |j|
    if 10000 * i + 5000 * j + 1000 * (n - i - j) == y
      a, b, c = i, j, (n - i - j)
    end
  end
end
puts "#{a} #{b} #{c}"
```

多重代入ができます。
文字列中で `#{}` を使って変数展開できるのもRubyと同じです。


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

```rb
s = read_line
qs = {"dream", "dreamer", "erase", "eraser"}
20000.times do
  qs.each { |q| s = s[0, s.size - q.size] if s.ends_with?(q) }
end
puts s.empty? ? "YES" : "NO"
```
後ろから削っていきます。
`String#rchop` を使おうとしたらAtCoderで動いているバージョンでは使えなかったので `String#[]` で。

`qs` の定義で使っている `{}` は Tuple です。Arrayと比べて、スタック上に取られるのでパフォーマンスが良い場合があります。要素の個数が決まっている場合にはこちら推奨。

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

```rb
n = read_line.to_i
p = Array.new(n) { read_line.split.map(&.to_i) }
p.unshift([0, 0, 0])
ans = ((1..n).all? do |i|
  dt = p[i][0] - p[i - 1][0]
  dx = p[i][1] - p[i - 1][1]
  dy = p[i][2] - p[i - 1][2]
  dx.abs + dy.abs <= dt && (dt + dx + dy) % 2 == 0
end)
puts ans ? "Yes" : "No"
```

第5問で出てきたのと同じように、 `do~end` は代入より結合優先度が低いので、`ans = xxx do ... end` と書くと、 `ans` にはブロックの返す値ではなく `xxx` が入ってしまいます。これを避けるために括弧で囲っています。