AtCoderで競技プログラミングを始めて二年半で青色コーダーになりました。使用言語はCrystalです。この記事はいわゆる色変記事ですが、Crystal言語推しを目的としています。
自己紹介
- 54歳で競技プログラミングを始めて56歳で入青
- 妻帯、一人娘（大学院）あり
- 元ゲーム開発者、現金融系SIerの技術系管理職
- Perl生まれのRuby育ち。毎年一つは新しい言語を覚えたい。
- 数学科出身
AtCoder開始～入緑まで
会社の後輩に紹介されてAtCoderの存在を知り興味を持って始めました。趣味でも仕事でも使用していたRubyを選択。ABC144から始めましたが、ビギナーズラックで水パフォを取り、毎週参加するようになっていきます。丁度10回目で入緑。
緑～水まで
件の後輩氏は「1年で青になる」と宣言して会社を辞めてしまったのですが、当方は世界の腕自慢と競えるオンラインゲームの感覚で、趣味の一環として継続して参加していました。蟻本を購入して読み始めたのもこの時期です。Ruby用にPriorityQueueの移植などしていたと思います。自分用のライブラリを整備するのがとても好きです。「盆栽」と呼んでいる競プロerがいましたが、なるほどという感じです。「セグ木で殴る」というパワーワードを知り、強く心惹かれたのもこのころです。私もセグ木で殴りたい！
水色で停滞
AGC044のJokerで壁に当たりました。どんなに正しくコードを書いてもRubyではTLEが取れません。Rubyは特に二次元配列の参照がからむと遅いのでそれが原因だとは思います。また、Ruby用にセグ木を書いてみましたが、速度の問題で実用になりませんでした。平衡二分探索木なんてもってのほか。
Crystalで青色へ
そんな中で以下の記事を読んでCrystal言語と出会いました。型制約があって速いRuby！セグ木で殴れるかもしれないと期待が膨らみます。
両氏には記事だけでなく、提出コードもとても参考にさせていただいており感謝しかありません。
AtCoder に登録したら解くべき精選過去問 10 問を Crystal で解いてみた - Qiita
プログラミング言語Crystalで競プロをする際のテクニックまとめ
その後、念願のセグ木や平衡二分木など、ライブラリを整備しては過去問を埋めることを繰り返し、入青することができました。
マクロ
C++を知っていると、最大・最小値の更新である、chmin/chmaxが羨ましくなります。
Rubyでは難しいところですが、Crystalではマクロで実現できます。
macro chmin(target, other)
%val = ({{other}})
{{target}} = %val if ({{target}}) > %val
end
x = 100
chmin x, 10
pp x # => 10
マクロは左辺値を展開できるので、上のようなマクロを定義しておくと、ほぼC++の感覚でchmin/chmaxが使用できます。
getterマクロ
Rubyのインスタンス変数は事前の宣言なくどこでも使えますが、Crystalでは型推論ができないのであれば宣言が必要です。
# 型推論ができないためエラー
class Hoge
def initialize(@a)
@b = 10_i64
end
def a # => いわゆるgetter
@a
end
end
Hoge.new # => Error: can't infer the type of instance variable
# 型の宣言をしているのでエラーにならない
class Hoge
@a : Int32 # <- こんな宣言が必要
def initialize(@a)
@b = 10_i64
end
def a # => いわゆるgetter
@a
end
end
Hoge.new(10) # => OK
また、Rubyのattr_reader, attr_accessorの代わりに、getter/propertyが使用できます。
クラスメソッドだと思っていたのですが、良く調べるとマクロでした。なおかつ、マクロの中で
メソッドの定義と型の宣言の両方をやっています。
#getterマクロの中で型宣言をしているのでエラーにならない
class Hoge
getter a : Int32
def initialize(@a)
@b = 10_i64
end
end
h = Hoge.new(1)
# getterメソッドaが定義されている
h.a # => 1
Procの再帰
DFSが想定解の場合、RubyではProc/ラムダ式の再帰が書けます。Crystalでは書けないかと思っていたのですが、ひと手間掛けると書くことができました。
# rubyの場合
fib = ->n do
case n
when 1 then 1
when 2 then 1
else fib[n - 1] + fib[n - 2]
end
end
pp fib[10] # => 55
# crystalの場合
fib = -> (n : Int32) do
case n
when 1 then 1
when 2 then 1
else fib.call(n - 1) + fib.call(n - 2)
end
end
pp fib.call(10)
# Error: can't use variable name 'fib' inside assignment to variable 'fib'
自分自身を呼べないというエラーになりますが、次のようにuninitializedで一旦初期化しておくと
# uninitializedで初期化しておく
fib = uninitialized Proc(Int32,Int32)
fib = -> (n : Int32) do
case n
when 1 then 1
when 2 then 1
else fib.call(n - 1) + fib.call(n - 2)
end
end
pp fib.call(10) # => 55
これでRubyと同じようにトップレベルでDFSを書くことができます。
Range#sum
CrystalのライブラリはCrystal自体で書かれています。そのため良くソースコードを読むんですが、コメント欄に計算量のO(1)という表記を発見。これって競技プログラミング向けにチューニングしてくれているのでは（錯覚です）
# If `self` is a `Int` range, it provides O(1) implementation,
# otherwise it is same as `Enumerable#sum`.
def sum(initial)
b = self.begin
e = self.end
if b.is_a?(Int) && e.is_a?(Int)
e -= 1 if @exclusive
n = e - b + 1
if n >= 0
initial + n * (b + e) // 2 # <= ここ
else
initial
end
else
super
end
end
難問の中間処理で、たまに手間が減らせることがあります。
浮動小数点のRange#bsearch
こちらもRange#bsearchのソースを読んでいて発見。
RangeがFloatを含む場合、内部的に整数として読み替えて処理している模様。最大65回程度で収束とあります。
回数を300回程度で決め打ちして回していましたが、ライブラリ任せでよさそう。
# If the range consists of floating value,
# it uses specialized implementation for floating value.
# This implementation is very fast. For example,
# `(1..1e300).bsearch{ false }` loops over 2000 times in
# popular implementation, but in this implementation loops 65 times
# at most.
{% for v in %w(from to) %}
if {{ v.id }}.is_a?(Float::Primitive)
return bsearch_internal from, to, self.excludes_end? do |value|
yield value
end
end
{% end %}
使用例：51～53行あたり
ARC003 暗闇帰り道
早くて短い
例えば以下の問題の最短コードはCrystalです。
かなり計算量が厳しい問題ですが、コードの短さと速さを両立させています。C～E問題で計算量が厳しい問題で、スクリプト言語のACが無い当たりでCrystalが最短を取っている印象です。今度ちょっと集計してみますね。
ABC198 D.Send More Money
今後について
幸運にも入青しましたが、まだまだ実力的には水色だと思っているので、まずは青安定が目標です。
その先は「還暦までに赤」あたりを目標にしていこうかと思います。