RubyとCrystalでAtCoder青色になりました

2023年5月27日開催のABC303で青になりました。2021年4月24日のABC199からスタートですので、およそ２年かかりました。

自己紹介

• 仕事してます。コードをがっつり書いていた時期もありました（過去形なのが悲しい）
• Rubyが好き

開始〜入緑まで

コード書きは得意なつもりだったので、何もしなくても結構いけるだろうと根拠のない自信がありました。初参戦のABC199が３完でした。この時のC問題が愚直に実装するとダメで、ちょっとした工夫が必要な問題だったのですが、そういったことを考えるのが面白くてどっぷりハマっていくことになりました。

初めて数回ですぐに緑・水パフォがで始めたので、開始時点でも緑上位ぐらいの実力だったのだと思います。C問題ぐらいまでのdiffが低めの問題を高速に解くことができたのと、この頃は難易度の崖がある回が多く灰・茶コーダーには、C問題ぐらいまでの早解きで勝負がつくことが多かったのも幸いしました。

競技プログラミングは業務プログラミングに役立つか？みたいなのがよく話題になりますが、逆に「業務プログラミングは競技プログラミングに役立つこともある」という例です（内容によります）。

６回目のコンテストで入緑しました。

ここまでで役立った知識

• とくに競技プログラミング特有のないが、標準ライブラリ（配列、文字列、ハッシュ（辞書、連想配列）など）の習熟はかなり役立ちました

入水まで

このころ競プロ典型９０という大変素晴らしいコンテンツが進行していました。

効率的に典型アルゴリズムを学ことができました。☆7まで一応埋めましたが、☆6まででも十分だったような気がします。解説が簡潔で初心者には難しいところもあったのですが、逆に行間を考えたり別の資料を並行して調べることで理解が深まった気がします。

この時までほぼRubyだけでやっていたのですが、典型90でRubyで通せない問題にしばしば遭遇するようになりCrystalという言語も使い始めます。

競プロ典型９０が終わったあたりから、業務の忙しさやら体調不良などでAtCoderどころではなくなり、次第に練習もできなくなっていきます。数ヶ月コンテストにまともに出られない時期もありました。それでレートも停滞していったのですが、忙しい中でも練習しようとして考えたのが「考察練習」でした。通勤の電車内でABCの過去問題の解き方を頭の中で考えるという練習法です。実装することには拘っていませんでした。これが効いたのか、そこから徐々に伸び始めてなんとか入水を果たします。開始から１０ヶ月でした。

入青まで

水色になってからも相変わらずの忙しさで同じやり方を続けていました。考察練習メインで続けます。じわじわ上がり続けて水色になって10ヶ月ほどで、最高レートが1584に達して、青まであと少しというところまできました。しかし、この2022年は特に忙しくて、残業・休日出勤や過労やらで考察練習すらできない、土日も疲れが取れないような状況が続きその影響がレートに表れてきます。入青まであとちょっとというところから、不調に入り２００近く落としてしまいました。

やり方を変えなくてはということで、ここから実装練習に変えます。考察練習でたくさんの問題をすでに考察済みなので、それらをひたすら実装していくという練習です。考察力に実装力が追いついてない状態だったと思うのですが、それが解消されたのか一気にレートが上がり入青することができました。

入青直前までの練習はこんな感じです。

青問題を徹底的に実装練習することが効果的でした。平日に毎日青問題は大変そうに見えますが、考察自体は過去にしっかりやってるので、考察抜けがなければサクサク解けます。考察過程も楽しいのですが、やっぱりプログラムをカチャカチャ入力するのが楽しいです。

プログラミング言語Rubyとプログラミング言語Crystal

Rubyをすでに知っていて、これから競技プログラミングを始める！という方は、Rubyで競技プログラミングできます。PythonやらC++に変える必要は全くありません。Rubyのメリットは、

• 簡潔な表記
• 美しいクラスの階層構造
• ブロックによる柔軟な表記
• （人によると思うけど）書いてて楽しい！

です。

しかし、競プロ的視点ではRubyは速度がC++に比べると遅く、C++で通せるのにRubyでどうやってもTLEなんてこともあります。そういうのに何度も遭遇すると「C++でもういいか...」となりそうです。そういう時には、Rubyによく似た静的片付け言語Crystalがあります。Crystalを使うと言語が遅いのでTLEというのは基本的にはありません。

Rubyは知ってる。Crystalに興味を持った！という方は、私の記事ですが以下をご覧になっていただければと思います

競プロに特化した記事だと以下が参考になりました。

https://qiita.com/hakatashi/items/0892366ea47f1e88083d
https://qiita.com/tomerun/items/23ce2a2ed6ead291d222

練習の方法

ライブラリ整備をしよう

問題を解いて「他でも応用が効きそうだな！」という部分は積極的にライブラリにしています。結局使わないものが大半なのですが、ライブラリにすることで、アルゴリズムや言語への理解が深ます。

定番のUnion FindとかFenwick Treeとかは言うまでもないのですが、あまりライブラリにしているというの聞かないが本番での登板率が高いのをいくつか紹介します。

• 累積和

あえてライブラリにするほどのものではないと思われそうですが、クラス化することで、可読性が上がると思います。

a = [1,2,3,4,5]
ca = CumulativeSum.new(a)
puts ca.sum(1..3)  # a[1]~a[3]の合計
puts ca.sum(1...4)  # a[1]~a[3]の合計 (...は半開区間）
puts ca.sum(2..)    # a[2]以降の合計

みたいなことができます。累積和を何個も用意しながら細かい計算をするときに、ミスも防げます。クラスでなく愚直に書いた場合と比較しても速度低下もほぼないことは確かめています。

• 二分探索ラッパー１

Ruby/CrytalにはRangeとArrayにbsearchという二分探索の標準ライブラリが用意されています。
これは、単調性の仮定のもとで、falseからtrueに切り替わるようなtrueの場所を見つけるというものです。

puts (1..10).bsearch {|i| i*i >= 9} # => 3  i*iが初めて9以上になるのは3である。

考察において、逆にtrueからfalseに切り替わるようなギリギリのtrueの場所を見つけたいということもよくあります。つまり逆の単調性が成立している状況で、iが小さいときtrueで大きいときfalseという感じです。条件をひっくり返すだけなので、bsearchだけでも全く問題ないのですが、あえて自作のラッパーとして、次のメソッドを用意しています。

puts (1..10).rbsearch {|i| i*i <= 9} # => 3  iを大きい方から見てi*iが9以下になる初めてなるのが3

命名のイメージは逆向きのbsearchなのでrbsearchです(Ruby/Crystalのindexメソッドに対するrindexメソッドに似てます）。

ひっくり返すだけなら用意する意味ないように感じるかもしれませんが、見つからなかった場合nilを返すなど細かい配慮をしていて、コーディングにおける思考の細かい負荷を下げてくれます（この辺りの考え方はhamamuさんの記事を参考にしました。)

加えて、指数探索も実装していて、始点や終点がない区間の二分探索にも対応してたりします。

puts (1..).bsearch {|i| i*i >= 9} # => 3  
puts (..10).rbsearch {|i| i*i <= 9} # => 3  

二分探索の範囲の自明な上限がぱっと見えないときは使うこともあります

rbsearchの実装の一部は以下のような感じです(Crystal用。指数探索部分は含まず）

struct Range
  def rbsearch
    b, e = self.begin, self.end.not_nil! - (self.excludes_end? ? 1 : 0)
    i = (self.bsearch {|x| !yield(x) } || e+1)-1
    i < b ? nil : i
  end
end

• 二分探索ラッパー２

また、Arrayクラスへ組み込むmoduleとして以下のようなラッパーも実装しています。ソート済みの配列に対していろんな量が求められます

class Array
  include SortedArrayMethods
end
a = [1, 4, 6, 10, 12]
puts a.pred(8)   # => 8より小さい最大の値 6
puts a.pred_index(8) # => 8より小さい最大の値のindex 2
puts a.succ(8)   # => 8より大きい最小の値 10
puts a.succ_index(8) # => 8より大きい最小の値のindex 3
puts a.sorted_count(5..11) # => 配列中の5~11を満たす要素数: 2

他にも色々用意しています。これらの中身は標準ライブラリのbsearch, bsearch_indexを呼び出すだけなんですが、可読性が向上しますし、添字ミスがなくなります。

こちらの実装は長くなるので省略します。またどこかで公開したいです。

考察力アップは脳内考察練習

通勤時に考察練習をしていたと上に書きましたが、両手の塞がる電車内ですので、紙で書きながらの考察はできません。式変形を脳内で暗算したり、図をイメージしながら・・と、この方法は思考負荷がめちゃくちゃ高いです。紙を使って考察するようよりも数段難しくなります。しかし、逆にいうとコンテスト本のように紙で考察をする場合に、楽に考察できるようにようになったと感じました。この方法で考察力がかなりついたなと思っています。

最後に

AtCoderではRubyは多くなく、Crystalとなると数えるほどしかいないですが、増えていってほしいなとおもっています。
Ruby/Crystalをお使いの方に何かの参考になれば幸いです。