AtCoderにて、ついに2023年の言語アップデートが行われます。
Crystal言語もその恩恵を受け、0.33.0 から 1.9.1 へと大幅な更新が行われました。
本記事では競技プログラミングで特に有用なアップデート内容をご紹介します。
ac-library.crの追加
AtCoder LibraryのCrystal実装がライブラリとして追加されました。
使用方法は簡単で require 文を書くだけです。
require "atcoder"
require "atcoder/fenwick_tree" # 個別にロードしたい場合
ModInt1000000007.new(-1) # => 1000000006
全ての機能の移植が行われているわけではないのですが、dsu や mod_int などの使用頻度が高いライブラリは実装が完了しています。
また、ac-library.cr では本家ACLに加えて優先度付きキューなどの実装もあります。
毎回ヒープのためだけに長いライブラリを貼っていたのが、require "atcoder/priority_queue" で済むわけですからとても便利ですね。
機能の全てを知りたい場合はドキュメントページを参考にすると良いです。
自分の環境にインストールする場合のやり方を2つ紹介します。
shards を使ってインストール
競プロ用のディレクトリ構造に特にこだわりのない人向けです。
まず、競プロ用のディレクトリを生成します。
$ mkdir compe
$ cd compe
$ crystal init app .
生成された shard.yml を次のように置き換えます。
name: compe
version: 0.1.0
authors:
- your-name-here <your-email-here>
targets:
a:
main: src/a.cr
b:
main: src/b.cr
c:
main: src/c.cr
d:
main: src/d.cr
e:
main: src/e.cr
f:
main: src/f.cr
g:
main: src/g.cr
h:
main: src/h.cr
crystal: 1.7.2
license: MIT
dependencies:
atcoder:
github: google/ac-library.cr
branch: master
次に、src/ の中に a.cr から h.cr まで作成してください。
$ for ch in {a..h}; do touch "src/${ch}.cr"; done
これで準備完了です。例えば、
$ shards run a
とすれば src/a.cr に書いた解答コードが実行されます。なお、crystal run src/a.cr でも実行できます。
最小限のインストールで済ませる
すでにこだわりの競プロ環境がある人向けです。
結局のところ、crystal build するディレクトリに lib/atcoder が存在すれば正常にビルドできます。
Makefile を作ったり、vscode の tasks.json を設定したり、色々自分好みのやり方を探してみると良いと思います。
例
自分の場合は以下のようなディレクトリ構造で、毎回 cd abc/abc288/a/ をしてそのディレクトリで作業をします。
abc
┣━━━ abc287
┃ ┣━━━ a
┃ ┃ ┗━━━ main.cr
┃ ┣━━━ b
┃ ┃ ┗━━━ main.cr
┃ ┗━━━ c
┃ ┗━━━ main.cr
┗━━━ abc288
┣━━━ a
┃ ┗━━━ main.cr
┣━━━ b
┃ ┗━━━ main.cr
┗━━━ c
┗━━━ main.cr
各ディレクトリに lib/ をシンボリックで貼るのが一番簡単そうですが、少々冗長なような気がします。
そこで、次のような関数を .zshrc に書いておくことにします。
# COMPE には `lib/atcoder` を置いておく
export COMPE=/Users/ngng628/Documents/competitive-programming/
function cr() {
(cd ${COMPE} && crystal build "${cur}/$1" -o "${cur}/a.out")
}
これで cr main.cr でビルドできるようになりました。
コンパイルオプションの追加
コンパイルオプションに -Donline_judge が追加されました。
puts {{ flag?(:online_judge) }} で確認することができます。
素朴な使用例として以下を挙げておきます。
macro dbg(value)
{% unless flag?(:online_judge) %}
pp! {{ value }}
{% end %}
end
dbg "debug mode" # AtCoder 提出時にはこの行がまるごと消える
Crystal本体の更新
Crystal言語そのものも進化しています。
パフォーマンスの向上
諸々パフォーマンスが向上し、高速化されています。
スプラット展開が緩和
これまでスプラット展開は関数やマクロに対してしか使えませんでしたが、配列やタプルなど Indexable なクラスに対しても使えるようになります。
AtCoderでは、例えばクエリ問題で種別 $t$ によって長さの異なるクエリ列を受け取るときに便利そうです。
3.times do
a, b, *c = read_line.split.map(&.to_i)
puts a
puts b
puts c
end
1 2 3 3
2 4
1
1
2
[3, 3]
2
4
[]
Failed to raise an exception
また、Range のスプラッタ変換を利用して、次のようなコードも書けるようになります。
[0...5].to_a # => [0, 1, 2, 3, 4] (0.33.0)
[*(0...5)] # => [0, 1, 2, 3, 4] (1.8.3 )
各種メソッドの追加
Math.isqrt(x)
$\lfloor \sqrt{x} \rfloor$ を返します。
Math.isqrt(2) # => 1
Math.isqrt(3) # => 1
Math.isqrt(4) # => 2
Math.isqrt(5) # => 2
Number#digits
数字を桁ごとに区切った配列を返します。
12345.digits # => [1, 2, 3, 4, 5]
12345.digits.sum # => 15
String#to_i128
以前までは #to_i64 などを経由する必要がありましたが、直接変換できるようになりました。
各種 bit 演算
高速なbit演算が実装されました。
0b10010 # => 18
0b10010.bit(0) # => 0
0b10010.bit(1) # => 1
0b10010.bit_length # => 5
0b10010.popcount # => 2
0b10010.trailing_zeros_count # => 1
（よく見ると bit_length しか追加されてなかった…）
Number#positive? / Number#negative?
正負を判定するメソッドが追加されました。
2.positive? # => true
-2.positive? # => false
[1, -2, 3, -4, 5].select(&.negative?) # => [-2, -4]
not_nil! の省略
次のメソッドで not_nil! を書かなくても良くなりました。
-
#index(n).not_nil!=>#index!(n) -
#rindex(n).not_nil!=>#rindex!(n) -
#find { |x| x > n }.not_nil!=>#find! { |x| x > n }
Int#lcm のオーバーフロー対策
最大公倍数を (self * other).abs // gcd(other) で計算していたのでオーバーフローする危険がありました。
1.8.2 では (self // gcd(other) * other).abs で計算しているので最大公倍数がオーバーフローしないなら途中計算でオーバーフローすることはありません。
step.sum の計算量改善
$a$ から $b$ までを $s$ 飛ばしで列挙した数列の総和が $O(1)$ で求められます。
（Range#sum は言語アップデート以前から $O(1)$ でした）
1_i64.step(to: 10_i64 ** 9, by: 2).sum # => 250000000000000000 in O(1)
型の自動キャスト
参考: https://crystal-lang.org/reference/1.8/syntax_and_semantics/autocasting.html
次のようなコードでエラーが出なくなりました。
def f(n : Int64)
puts "#{n.class} #{n**2}"
end
n = 4_i64
m = 4
f(n) # => Int64 16
f(m) # => Int64 16 (いままではCompile Error)
安全にキャストできる場合に限って、制限が緩くなっているようです。
AtCoderに提出してCEになってしまうときの8割はこのエラーだったので助かります。
一方で、次のようにダウンキャスト的（？）な場合はコンパイルエラーとなります。競プロ的には、面倒ではあるものの嬉しい仕様だと思います。
def f(n : Int32)
puts "#{n.class} #{n**2}"
end
n = 4_i64
m = 4_u32
f(n) # => Compile Error!
f(m) # => Compile Error!
f(4294967295_u32) # => Compile Error! (Int32 を確実にオーバーフローする)
f(4_i64) # => Int32 16
f(4_u32) # => Int32 16
最後に
CrystalはRubyのような書き味を残しながら、Cのように高速に動作する言語です。
競プロのためにあるんじゃないかと思えるほど競プロ向きの良い言語なので、ぜひこれを機会に皆さんお試しください。