はじめに
AtCoderでCrystalでのAC数1位の者です (2018-03-21現在。参照:AtCoder Problems) 。
AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ で紹介されている10問をCrystalで解いてみました。
問題内容の説明などは元記事の方を参照してください。
Crystalとは
"Fast as C, slick as Ruby" をスローガンに開発されているプログラミング言語です。
Rubyにそっくりな文法と標準ライブラリを持ちながら、ネイティブコンパイルして実行するので速い、という点が特長です。
Rubyを知ってい(てコンパイルと静的型付けを受け入れることができ)る人ならすぐに書けるようになると思います。静的型付けと言っても、かなりコンパイラが推論するので少なくとも競技プログラミングの範囲では自分で型を書くことはほとんどありません。
競技プログラミングの問題にはLLでは実行時間的に厳しいものも多いですが、CrystalならRubyの書きやすさを保持しつつ実行速度も問題ない、ということで、もうちょっと流行ってもいいんじゃないかと思っています。
利用できるオンラインジャッジとしては、AtCoder や yukicoder があります。
(ただし、現在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#chars
で Array(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
には xxx
と do~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
が入ってしまいます。これを避けるために括弧で囲っています。