プログラミング言語Crystalで競プロをする際のテクニックまとめ

hakatashiです。

昨年夏からCrystalを用いてAtCoderにこつこつと参加し続け、現在Crystalの Languege Ranking の2位にランクインしています。

Crystalとは

プログラミング言語Crystalは、一言で言うと「コンパイル可能なRuby」です。Rubyの文法はそのままに、静的型付けと型推論機を組み込み、Rubyの書きやすさと安全性、速度を改善した言語です。日本での知名度はいまいちなようですが、現在もアクティブに開発が続けられているホットな言語です。

Crystalで競技プログラミングに参加することのメリットに関しては、CrystalのAC数1位のtomerunさんの以下の記事に詳しいです。自分も触発されました。

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

Crystalはかように素晴らしい言語である一方、競プロに用いる際に陥りがちな罠も多く存在します。C++などのメジャーな言語と違ってこれらをまとめた記事はまだ存在しないため、この記事にまとめておきます。

手元に Crystal v0.20.5 の実行環境を用意する

AtCoderにCrystalで参戦する際の大前提です。AtCoderのCrystal実行環境はv0.20.5であり、これは最新版のCrystalと非常に大きく仕様が異なります。手元で通ったのにAtCoderで動かないというイライラを無くすためにも、必ず全く同じバージョンの実行環境を手元に用意しましょう。

• ダウンロード: https://github.com/crystal-lang/crystal/releases/tag/0.20.5
• 言語リファレンス: https://crystal-lang.org/api/0.20.5/index.html

なおAtCoderのCrystal実行環境は近々アップデートされる予定らしいので、以下のような最新バージョンとの違いも把握しておくと良いかもしれません。

• /演算子に対する破壊的変更
  • Rubyと異なりFloat型を返すようになります。Intを返させたい場合 (多分こっちが大半だと思いますが) //を使用します。
• 整数型の型推論の向上
  • Int64型の引数にInt32を渡せるようになります。Array(Int64).new(10, 0)などがエラーにならなくなります。
• 始点なしRange型の実装
  • "hogehoge"[0..3]を"hogehoge"[..3]と書けるようになります。

整数型のオーバーフローに気をつける

Crystalを用いて競プロに参加する際に最も発生しやすいミスが整数型のオーバーフローの見落としです (当社調べ)。なまじ型推論機がすべて推論してくれるだけに、一度コードに32bit整数型が混入すると連鎖的に複数の変数が32bitと推論されエラーとなってしまうことが頻繁にあります。またバージョン0.20.5ではまだオーバーフロー検出機能が実装されていないのでどこでオーバーフローが発生したか検出するのも困難となります。

競プロの問題においてメモリが不足することはほぼ無いはずなので、Int32型やUInt32型を避けて可能な限りすべての場所でInt64型を用いるようにしましょう。Crystalの数値リテラルはデフォルトでInt32型となるので、なるべく 0_i64 のように型アノテーション付きで記述すると吉です。

しかし、常に気をつけていてもInt32型が混入してオーバーフローに繋がる罠がCrystalにはあります。以下に一例を挙げるので、十分に気をつけて使うようにしましょう (自戒)。

暗黙的にInt32を返却するメソッドに気をつける

顕著な例がArray#sizeです。以下のコードでは変数ansはInt32型と型推論されます。

inputs = read_line.split.map(&.to_i64) # Array(Int64)
ans = inputs.size # Int32

Int32#to_i64を用いてInt64型に変換にしてから変数に代入しましょう。

inputs = read_line.split.map(&.to_i64) # Array(Int64)
ans = inputs.size.to_i64 # Int64

演算順序に気をつける

全ての数値リテラルにアノテーションを付けるのは大変なので、インラインの計算ではアノテーションを省略することも多いです。例えば、以下のコードではオーバーフローは発生しません。

a = 10000000000000_i64
ans = a * 2 + 100 # Int64

しかし演算の順序には気をつけてください。数値リテラルを先に持ってくるとオーバーフローが発生します。

a = 10000000000000_i64
ans = 2 * a + 100 # Int32

これはC++などとは異なる挙動です。Rubyと同じオブジェクト指向の原則に従い上のコードではInt32#*が呼び出されるためです。数値リテラルを先に持ってくる場合は必要な箇所に必ずアノテーションを付与しましょう。

a = 10000000000000_i64
ans = 100_i64 - a * 2 # Int64

Array#maxとArray#minを避ける

Rubyで最大値、最小値を求める方法といえば配列に対するArray#maxとArray#minですが、Crystalでは避けましょう。実行するたびに配列を生成するので非常に重いです。

少なくとも2つの値の最大値を求める場合は三項演算子などで愚直に書くべきです。環境にもよりますが以下のベンチマークでは8倍近い差が生まれます。

max-bench.cr

require "benchmark"

def max1(a, b)
  [a, b].max
end

def max2(a, b)
  a > b ? a : b
end

Benchmark.ips do |x|
  x.report("Array#max") {
    max1(10, 100)
    max1(-10, 100)
    max1(10003, 10002)
    max1(22222, 111111)
    max1(33, 4)
    max1(3003, -3003)
    max1(0, 0)
    max1(100, 20)
    max1(Int32::MIN, Int32::MAX)
    max1(16, 1)
  }
  x.report("Ternary operator") {
    max2(10, 100)
    max2(-10, 100)
    max2(10003, 10002)
    max2(22222, 111111)
    max2(33, 4)
    max2(3003, -3003)
    max2(0, 0)
    max2(100, 20)
    max2(Int32::MIN, Int32::MAX)
    max2(16, 1)
  }
end

$ /usr/local/share/crystal-0.20.5-1/bin/crystal build benchmarks/max-bench.cr -o max-bench
$ ./max-bench
Warning: benchmarking without the `--release` flag won't yield useful results
       Array#max 602.84k (  1.66µs) (±12.09%)  7.94× slower
Ternary operator   4.79M (208.97ns) (± 8.81%)       fastest

多倍長整数を活用する

PythonやRubyと同じく多倍長整数をサクッと扱えることはCrystalの強みです。

64bitを超える巨大な数値を扱えるほか、C++のstd::bitsetの代用としても用いることができます。活用しましょう。多倍長分数もあります。

参考: https://atcoder.jp/contests/abc147/submissions/8876240

競技プログラミングに必要なデータ構造ライブラリを確認する

Crystalの標準ライブラリには競技プログラミングに使えるデータ構造ライブラリが一部含まれています。必ず事前によく確認しておきましょう。

• 動的配列: Array
• キュー (両端キュー): Deque
• ハッシュテーブル: Hash / Set

一方C++を使用することのメリットの一つである優先度付きキューや平衡二分探索木などの複雑なデータ構造のライブラリはCrystalにはありません。事前に書いておくか、以下のような世の中に公開されている競プロ用ライブラリを活用しましょう。

• tomerunさんのライブラリ: MITライセンス
• hakatashiのライブラリ: MITライセンス
• TobiasGSmollett/crystalg: MITライセンス

with_indexの使い方に気をつける

Rubyでは以下のようにして配列のindex付きでArray#max_byを呼び出すことができます。

p [10, 30, 100].max_by.with_index {|a, i| i % 2} #=> 30

Crystalではmax_byなどのメソッドがイテレーターを返却しないため上のコードはエラーになります。

p [10, 30, 100].max_by.with_index {|a, i| i % 2}
#=> Error in with_index.cr:1: 'Array(Int32)#max_by' is expected to be invoked with a block, but no block was given

Crystalでこのようなことをしたい場合、with_indexを先に持ってくる必要があります。

p [10, 30, 100].each.with_index.max_by {|a, i| i % 2} #=> {30, 1}

その他の便利メソッド

その他、競技プログラミングに有効と思われるCrystal (やRuby) 特有の便利メソッドです。

• Indexable#bsearch, Indexable#bsearch_index, Range#bsearch: 二分探索が一発で書けます。
• Int#gcd, Int#lcm: 最大公約数と最小公倍数が一発で書けます。
• Enumerable#max_of, Enumerable#min_of: Rubyに存在しないCrystal独自のメソッドです。便利。
• Array#each_combination, Array#each_permutation, Enumerable#each_cons, Enumerable#each_slice: 順列や組み合わせに対するループが一発で書けます。