Edited at

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


はじめに

AtCoderでCrystalでのAC数1位の者です (2018-03-21現在。参照:AtCoder Problems) 。

AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ で紹介されている10問をCrystalで解いてみました。

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


Crystalとは

https://crystal-lang.org/

"Fast as C, slick as Ruby" をスローガンに開発されているプログラミング言語です。

Rubyにそっくりな文法と標準ライブラリを持ちながら、ネイティブコンパイルして実行するので速い、という点が特長です。

Rubyを知ってい(てコンパイルと静的型付けを受け入れることができ)る人ならすぐに書けるようになると思います。静的型付けと言っても、かなりコンパイラが推論するので少なくとも競技プログラミングの範囲では自分で型を書くことはほとんどありません。

競技プログラミングの問題にはLLでは実行時間的に厳しいものも多いですが、CrystalならRubyの書きやすさを保持しつつ実行速度も問題ない、ということで、もうちょっと流行ってもいいんじゃないかと思っています。

利用できるオンラインジャッジとしては、AtCoderyukicoder があります。

(ただし、現在AtCoderではコンパイルに最適化オプションがついていないため、そんなに速くなかったりします。次回の言語アップデート時に要望を出す予定)


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

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 点)

puts read_line.chars.count('1')

String#charsArray(Char) が得られます。

'' で囲った値は Char 型のリテラルです。


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

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' の位置を探しました。

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 点)

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))) です。

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 点)

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 には xxxdo~end でできるブロック の2つの引数が渡ってしまいます。

これを避けるために括弧でくくっています。Rubyでも同じですね。


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

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 点)

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 点)

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 点)

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 点)

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 が入ってしまいます。これを避けるために括弧で囲っています。