【Crystal】AtCoderの言語アップデートで嬉しいことまとめ！


AtCoderにて、ついに2023年の言語アップデートが行われます。

Crystal言語もその恩恵を受け、`0.33.0` から `1.9.1` へと大幅な更新が行われました。

本記事では競技プログラミングで特に有用なアップデート内容をご紹介します。


## ac-library.crの追加

[AtCoder Library](https://atcoder.github.io/ac-library/production/document_ja/)のCrystal実装がライブラリとして追加されました。

 - https://github.com/google/ac-library.cr

使用方法は簡単で `require` 文を書くだけです。

```crystal
require "atcoder"
require "atcoder/fenwick_tree"  # 個別にロードしたい場合

ModInt1000000007.new(-1) # => 1000000006
```

全ての機能の移植が行われているわけではないのですが、`dsu` や `mod_int` などの使用頻度が高いライブラリは実装が完了しています。

また、ac-library.cr では本家ACLに加えて優先度付きキューなどの実装もあります。

毎回ヒープのためだけに長いライブラリを貼っていたのが、`require "atcoder/priority_queue"` で済むわけですからとても便利ですね。

機能の全てを知りたい場合はドキュメントページを参考にすると良いです。
 - https://google.github.io/ac-library.cr/api/

自分の環境にインストールする場合のやり方を2つ紹介します。

### shards を使ってインストール

競プロ用のディレクトリ構造に特にこだわりのない人向けです。

まず、競プロ用のディレクトリを生成します。

```zsh
$ mkdir compe
$ cd compe
$ crystal init app .
```

生成された `shard.yml` を次のように置き換えます。

```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` まで作成してください。

```shell
$ for ch in {a..h}; do touch "src/${ch}.cr"; done
```

これで準備完了です。例えば、

```shell
$ shards run a
```

とすれば `src/a.cr` に書いた解答コードが実行されます。なお、`crystal run src/a.cr` でも実行できます。

### 最小限のインストールで済ませる

すでにこだわりの競プロ環境がある人向けです。

結局のところ、`crystal build` するディレクトリに `lib/atcoder` が存在すれば正常にビルドできます。

`Makefile` を作ったり、vscode の `tasks.json` を設定したり、色々自分好みのやり方を探してみると良いと思います。


#### 例

自分の場合は以下のようなディレクトリ構造で、毎回 `cd abc/abc288/a/` をしてそのディレクトリで作業をします。

```ディレクトリ構造.txt
abc
 ┣━━━ abc287
 ┃     ┣━━━ a
 ┃     ┃    ┗━━━ main.cr
 ┃     ┣━━━ b
 ┃     ┃    ┗━━━ main.cr
 ┃     ┗━━━ c
 ┃          ┗━━━ main.cr
 ┗━━━ abc288
       ┣━━━ a
       ┃    ┗━━━ main.cr
       ┣━━━ b
       ┃    ┗━━━ main.cr
       ┗━━━ c
            ┗━━━ main.cr
```

各ディレクトリに `lib/` をシンボリックで貼るのが一番簡単そうですが、少々冗長なような気がします。

そこで、次のような関数を `.zshrc` に書いておくことにします。

```~/.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) }}` で確認することができます。

素朴な使用例として以下を挙げておきます。

```cr
macro dbg(value)
  {% unless flag?(:online_judge) %}
    pp! {{ value }}
  {% end %}
end

dbg "debug mode"  # AtCoder 提出時にはこの行がまるごと消える
```

## Crystal本体の更新

Crystal言語そのものも進化しています。

### パフォーマンスの向上

諸々パフォーマンスが向上し、高速化されています。

### スプラット展開が緩和

これまでスプラット展開は関数やマクロに対してしか使えませんでしたが、配列やタプルなど `Indexable` なクラスに対しても使えるようになります。

AtCoderでは、例えばクエリ問題で種別 $t$ によって長さの異なるクエリ列を受け取るときに便利そうです。

```ソースコード.cr
3.times do
  a, b, *c = read_line.split.map(&.to_i)
  puts a
  puts b
  puts c
end
```

```cr:入力例
1 2 3 3
2 4
1
```

```cr:出力例
1
2
[3, 3]
2
4
[]
Failed to raise an exception
```

また、`Range` のスプラッタ変換を利用して、次のようなコードも書けるようになります。

```crystal
[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$ を返します。

```crystal
Math.isqrt(2) # => 1
Math.isqrt(3) # => 1
Math.isqrt(4) # => 2
Math.isqrt(5) # => 2
```

#### `Number#digits`

数字を桁ごとに区切った配列を返します。

```crystal
12345.digits # => [1, 2, 3, 4, 5]
12345.digits.sum # => 15
```

#### `String#to_i128`

以前までは `#to_i64` などを経由する必要がありましたが、直接変換できるようになりました。

#### 各種 bit 演算

高速なbit演算が実装されました。

```crystal
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?`

正負を判定するメソッドが追加されました。

```crystal
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)$ でした）

```crystal
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

次のようなコードでエラーが出なくなりました。

```crystal
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割はこのエラーだったので助かります。

一方で、次のようにダウンキャスト的（？）な場合はコンパイルエラーとなります。競プロ的には、面倒ではあるものの嬉しい仕様だと思います。

```crystal
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のように高速に動作する言語です。

競プロのためにあるんじゃないかと思えるほど競プロ向きの良い言語なので、ぜひこれを機会に皆さんお試しください。