Ruby競プロTips(基本・罠・高速化108 2.7x2.7)

最初に

Ruby Advent Calendar 2020の10日目の記事です。
昨日は、@coe401_さんのたのしいOSSコードリーディング: Let’s read WEBrick🏠 でした。
明日は、ima1zumiさんの記事です。

自分は、RubyでAtCoderの水色になれたレベルです。
最近は全くコンテストに参加してないですが、それなりにRubyの知見が溜まったと思います。
そういうわけで、Rubyでの競技プログラミング(競プロ)で得た知見を最初は書いていたのですが、
書いていくうちに細かい時間差が気になってたくさん計測しました。
そういうわけで、競プロで得た知見、及び、細かい高速化テクを集めました。
業務プログラミング(業プロ)で、使えるものもあるかもしれません。
高速化テクについては、最初の方に箇条書きでまとめています。

まだ編集が全然できてないのですが、いつまで経っても終わらずキリがないですし、アドベントカレンダー当日なので忘れないよう公開します。

表記・用語

Rubyの用語・表記

• るりま …… 『Rubyリファレンスマニュアル』、略して『るりま』。
• るびま …… 『Rubyist Magazine』、略して『るびま』。ウェブ雑誌。
• Hoge#foga …… Hogeクラスあるいはモジュールのfugaインスタンスメソッド。

競プロ用語

• AC (Accepted) …… 問題に正解したときの判定。
• WA (Wrong Answer) …… プログラムが正常に終了したが、出力が不正解のときの判定。
• RE (Runtime Error) …… プログラムでエラーが起きたときの判定。
• TLE (Time Limited Error) …… 時間制限内にプログラムが終了したときの判定。アルゴリズムが間違っているか、言語が遅いか。
• 定数倍高速化 …… アルゴリズム(時間計算量)に関係ない部分を高速化させること。
• 業プロ …… 業務プログラミング、略して業プロ。業務で使うプログラミング。最近、聞くようになった。
• ms …… ミリセカンド。ミリ秒。千分の1秒。プログラムの実行時間はこれで表記される、
  なお、本記事のRubyのBenchmarkによる計測の単位は、秒(s)です。total, realの列の時間を見てください。

各オンラインジャッジのRuby環境

2020年12月の環境です。

サイト	VERSION	PLATFORM	参考
AtCoder	2.7.1p83	x86_64-linux	公式情報
paiza	2.7.1p83	x86_64-linux	公式情報
yukicoder	2.7.2p137	x86_64-linux	公式情報
AOJ	2.4.0	x86_64-linux
Codeforces	2.7.1p83	i386-mingw32

今月3.0が新しく出る予定ですが、現時点では最新の2.7系ばかりで、これは珍しい状況です。
ふつう競技プログラミングサイトのバージョンアップはあまり行われません。国内最大手のAtCoderは今年全部の言語をまとめてアップデートしたばかりで、Rubyは一気に2.3.3から2.7.1へバージョンアップしました。50以上ある全部の言語を更新するのは大変らしくAtCoderはしばらくバージョンアップしないと思います。Codeforcesもしばらくバージョンアップしないと思います。

そういうわけで、Ruby 2.7を前提に書きます。
断りがなければ、テスト環境はruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x86_64-linux]です。
これは、RUBY_DESCRIPTION、RUBY_VERSION、RUBY_PLATFORMなどの定数で確かめられます。
基本的に、paiza.ioで試しています。

なお、海外最大手のCodeforcesも今年ジャッジ環境をバージョンアップしてRuby 2.7.1になったのですが謎のオーバーヘッドがあり、何もしなくても450msかかってしまい、参加したことがないです。問題の制限時間が2秒(2000ms)だとしたら、オーバーヘッドというハンデを背負っているせいで最初から実質的な制限時間が1550msの状況です。もし改善されたらRubyで参加したいところです。参考にいうと、AtCoderのRuby 2.7.1のオーバーヘッドは60ms前後です。

Rubyは競プロに向いているのか、他言語と比べたときのRuby

競プロで人気のある言語は、C++, Python(PyPy, Cython)が圧倒的です。
その次あたりに、Rust, C#, C言語, Ruby, Java等が続いている印象です。
そのあと、数多の言語が並んでいます。AtCoderは、サポートしている言語が多く、あと50個ぐらいあります。

C++と比べたときのRuby

たいていの競プロの問題では、1テストケースに対して2秒(2000ms)などの時間制限があります。
そして、C++, Rustに比べてしまうと、Rubyは10倍ぐらい遅いとイメージしていいと思います。
そのため、難しい問題になってくると、想定解法でもRubyだと解けない問題がでてきます。AtCoderだと今の6問制ABCのE問題、色でいうと水色ぐらいから想定解法でも解けない問題がではじめるイメージです。そのせいもあり、Rubyメイン使用者では暖色レベルの上位勢はまだいません。
ただ、C++と比べたとき、Rubyはオーバーフローがなく書きやすく学習もしやすい言語で、短くサッと書けるのは強みです。総合的に、簡単な問題に対してRubyはかなり有利だと思っています。

Pythonと比べたときのRuby

また、Pythonと比べると、どうでしょう。
一概には言えませんが、Rubyは、Pythonよりちょっと速いです。
しかし、Python勢は、選択肢が多く、言語提出にPyPy(やCython)という選択肢があります。
PythonでTLEになるコードをPyPyで提出するとACになるということも珍しくないです。
また、競技人口の多さなどでも負けています。
勝っている点は、個人的にはRubyの方が書き味がとてもいいです。
また、日本語のドキュメントなどが充実している印象です。

Rubyで解けなったときの言語の選択肢

Rubyの速さが原因で解けないコードがでたとき、どうするのでしょうか。
一定レベルからRubyからC++に流れる方が多い印象です。
C++であれば、大概の競技プログラミングのコンテストで使え、遅いということはないです。
それに、競プロ関係のライブラリが1番充実してます。
また、他の選択肢としては、最近はRustでしょうか。
他に、Rubyの文法と近い言語として、静的型言語のCrystalがあります。
CrystalはRubyとは似て非なる言語ですが、Rubyに似てC言語なみに速いのでオススメです。
ただ、Crystalは、やはりユーザー数が少ない点やコンパイル時間が長い点などがデメリットです。

時間の見積もり

AtCoderのテストでループにかかる時間を計測した結果、以下の表のようになりました。
(※あとの方でも触れますが、繰り返し処理はwhileが1番速いです。)

ループ回数	times計測	while計測	制限時間が2秒として(2秒のケースが多い)
0	約60ms	約60ms
10の6乗(百万)	約90ms	約75ms	余裕をもって間に合う。
10の7乗(一千万)	約330ms	約190ms	このあたりから中身が重たいと厳しい
10の8乗(一億)	約2600ms	約1450ms	現実的に無理。while中でもif1つ書けば、2秒超え。

計測方法は、(10**6).times{ }のような最小限のコードです。
実際、制限時間が2秒だとして、10の7乗台前後から、想定解法でも厳しくなってくる印象です。
それ以前の1,000,000回(10の6乗)で2秒超えてTLEするなら、自分の書いたアルゴリズムを疑いましょう。

今のC++は10の7乗だと「余裕をもって間に合う」レベルらしいので、C++と比べるとRubyは10倍遅い感じです。

競技プログラミングでは、問題に与えられた要素数も
方針・アルゴリズムを考えるヒントになるので、このあたりの感覚はもっておくとよさそうです。

高速化手法のまとめ・見方

先に高速化のまとめがあった方が親切かと思い、簡単にまとめておきます。
(まとめの方にしか書いてないのもあります……)
本記事は、アルゴリズムの話も少し混じっていますが、アルゴリズムはRubyに限らないので、ほぼ触れてません。
「アルゴリズムの前に当然知っておくべき」という内容や、「当然、避けるべき」という内容や、小手先の姑息で不毛な高速化Tipsなどをひっくるめてラインナップしています。
実践レベルで影響ないものを紹介するか迷いましたが、塵も積もれば山となるかもしれませんし、迷ったときに「ちょっと速い方にしておこう」と判断材料になったり、変えたところで大した影響ないことがわかると思うので、そういうのもたくさん混じっています。大抵の場合、マイクロベンチマークで1.1倍速くなる変更を加えたところで、全体として誤差レベルに過ぎないことに注意してください。

出力の高速化のまとめ

• 数値の出力は、putsを使う。pだと遅い。
  3,4倍違っていて、出力のウェイト大きいので、影響がでやすいです。
  実際の問題で、940msが430msへと約0.5秒縮むケースを確かめています。これは大きいです。
• ループのたびに出力するのではなく、ループ中に配列や文字列に<<で末尾に追加し、まとめたのを最後に1回で出力すると速い。
• putsでのStringの出力は速い。Symbolを出力するのは遅い。

数値計算の高速化のまとめ

• 整数どうしの割り算で浮動小数点数を返すとき、x.to_f / yが速い。
  fdivは、精度が高い分かいくらか遅め。
• 数値の配列の総和は、基本的にa.sumが高速。a.inject(:+)は、その次に速い。
• a.inject(:+)は、a.inject(&:+)等の方法よりも、桁違いに速い。
  &の有無が大違い。ブロックは遅い。
• 総和の余りを求めるときは、最後に余りをとるのが速い。
• 総乗の余りを求めるときは、その都度余りを求めるのが速い。
• 累乗の余りは、i.pow(j, mod)が高速。
  (i**j) % modは、桁違いに遅く、計算を放棄しうる。大切。
• 最大値・最小値の取得はmax・minを使う。
  sortで並び替えてから先頭や末尾をとるより、速い。
  複数の最大値や最小値の取得は、max・minの引数で個数を指定できる。
  a.sort[0, 2]ではなく、a.min(2)と書ける。
• 整数の演算の中に不用意に浮動小数点数が混ぜると少し遅いし、誤差が危険。
• 整数どうしの比較は、整数と浮動小数点数との比較よりも速い。
  無限大にFloat::INFINITYを使うのは避ける。
• i.nil?は速い。i == nilより4,5倍速い。Integer#==によるnil判定が遅い感じです。
  他のArray#==, String#==、Hash#==もnil?より2倍ぐらい遅いです。
• ゼロ判定は、i == 0が速い。i.zero?よりも、1.2倍ぐらい速い。
• 正負判定は、i > 0・i < 0が速い。i.positive?・i.negative?より、1.4倍速い。
• 奇数判定は、i & 1 == 1、i[0] == 1の順で速い。次にi % 2 == 1やi.odd?が速い。
  偶数判定は、i & 1 == 0、i[0] == 0の順で速い。次にi % 2 == 0やi.even?が速い。
  ビット演算は変態の記法ですね。odd?やeven?がわかりやすくていいです。

配列の高速化のまとめ

• 空配列の作成は、[]が速い。Array.newより2倍ぐらい速い。
• 初期化はArray.new(n, 0)が速い。[0] * nより1.1倍とちょっとだけ速い。
• 初期化はArray.new(n, 0)が速い。Array.new(n){ 0 }より10倍速い。ブロックは遅い。
• 初期化はArray.new(n){ [] }が、n.times.map{ [] }や(0...n).map{ [] }より1.2倍速い。
• 連番の配列を作るときは、(0...n).to_aが、[*(0...n)]よりちょっと速い。
• 連番の配列を作るときは、(0...n).to_aが、Array.new{ _1 }より桁違いに速い。
• 降順の配列を作るときは、(0...n).to_a.reverseが速い。(0...n).reverse_each.to_aより、1.7倍速い。
• 降順の配列を作るときは、(0...n).to_a.reverseが速い。(0...n).sort_by{ -_1 }より、10倍速い。
• 平方数の数列の配列を作るときは、Array.new{ _1 * _1 }が、(0...n).map{ _1 * _1}より少し速い。
• 配列のサイズは、sizeが、countよりも1.4倍前後速い。
• 範囲外参照時に返して欲しい値は、a[i] || 0が速い。a.fetch(i, 0)より速い。
• 空配列・空文字列の判定は、obj.empty?が速い。obj.size == 0より速い。
• 逆に、要素があるかの判定は、unless obj.empty?が速い。次にif !obj.empty?などより速い。
  if obj.any?は、3倍ぐらい遅く挙動も少し異なるのでよくない。
• 配列のアクセスは、a[0]・a[-1]が、a.first・a.lastよりも1.4倍前後速い。
• 要素の追加(配列の結合)は、<<, push, concatが速い。
  +=は、とても重たくなりうるので注意。
• 1要素の追加は、<<が速い。ついで、pushが速い。
  1要素の追加で、わざわざ配列を作りconcatするのは変で、いくらか遅いのでやめましょう。
• 破壊的メソッドかどうかは、特に速さとは関係ない。結局の速さは、メソッド・条件次第。
• 先頭・末尾の要素の削除は、pop, unshiftが、[]でスライスするより速い。
• 昇順ソートはsortが速い。sortでブロック指定は遅いので使わない。
• 降順ソートはa.sort.reverseが、a.sort_by{ _1 }より2.6倍速い。ブロック指定は遅い。
• ブロックで比較条件を指定するソートは、sort_byがsortよりも2,3倍速い。ブロックの実行回数が全く異なる。
• 同じ配列に対して何度もreverseはしない。1つの解決として、向きを変数として持って操作する。
• 昇順ソート配列があるときに降順ソートが欲しかったら、reverseするだけ。sort_byしない。

ハッシュの高速化のまとめ

• キーがないときの数値の返り値は、Hash.new(0)でデフォルト値の設定する。ブロックは遅い。これは数値などのみ。
• キーがないときの返り値を配列にするには、h[k] || []で返すのがいい。fetchよりいい。
• キーがなかったときに代入して返り値を返すには、h[k] ||= 0のように書く。初期化時のブロック指定より速い。ブロック指定はブロック指定で、配列を代入するときに便利。
• Hashのキーは、Symbolや凍らせたStringの方が、(凍ってない)Stringよりも速い。大切。
• Hashのキーに数値の組(ペア・トリオ)を使いたいときは、Integerの方が、Arrayよりも速い。
• Hashのキーの有無は、h[k]の方が、h.has_key?(key?)より1.1〜1.2倍ほど速い。
• キーと値の追加は、h[k] = v。新たにHashを作ってmergeするなんて大げさなことはしない。
• 既存のHashどうしの結合は、merge!がmergeより速い。結合系は、破壊的メソッドの方が速い印象。
• キーと値の組を1つ追加するなら、 []=を使う。わざわざハッシュを作ってからmergeはしない。
• Hashのサイズは、sizeを使う。
  配列と違って、Hashのcountは、Enumerableで定義され要素数に応じてコストが増え危険。
• h.kyes.eachがh.each_keyよりごくわずかに速く感じるケースもあるぐらいに誤差レベル(かな)

文字列の高速化のまとめ

• 文字列の末尾追加は、<<, concatが速い。
  +=は、とても重たくなりうるので注意。大切。
• 文字列の末尾追加は、<<が速い。ついで、concatが速い。
• 文字列に対してbytesを使って数値の配列にする。
  文字列で管理するのが色々重いので、数値の配列に変換しちゃいます。
  競プロテク。TLEの瀬戸際でかなり効く。可読性は犠牲になるが強力。
• 配列の[]での添字による参照は速く、文字列の参照は軽く3倍遅い。
• 数値の配列を作る方が速い。文字の配列を作るのは遅い。
  bytesがcharsよりも速い。
• 数値リテラルが、文字列を生成するリテラルより速い。← 数値の配列にした方が速い理由の1つ。
• シングルクォートリテラル・文字リテラルが速い。次にダブルクォートのリテラルが速い。
  frozen_string_literalを使えば、生成時間は一緒(数値含めて)。
• bytes(each_byte)がchars(each_char)より速い。
• 1文字の置換・交換・削除は、trが速くて便利。gsubより、速い。
• tr!は、trより、わずかに速い。
• gsubは、gsub!より、ちょっと速い。
• ASCIIコードに限定した文字のカウントは、String#countで数えた方が、tallyなどで数えるより桁違いに速い。

ループの高速化のまとめ

• 繰り返し処理は、whileが高速で強力。while最高!! 次いで、times, eachが速い。
• forは、eachより遅い。なぜなら、forは中でeachを呼び出しているため。
• 降順で回すときも、whileが高速。次点downto。
  whileは、Enumerable#reverse_eachより3,4倍速いです。
  Enumerable#reverse_eachは、Enumerable#eachより1.5倍ぐらい遅い。
• ブロックに渡して回すメソッドは、そうする。str.split{|c| }が、str.split.each{|c| }より、1.5倍速い。
• each側でループ範囲を限定して、脱出判定の比較を実行しないようにする。
• 繰り返し行われる添字のアクセスを減らす。何度も使う要素は、別の変数におく。
• ループの外側で決まるものは、ループの外側におく。

数学の高速化

• primeライブラリのInteger#prime?が便利で速い。Prime.prime?より軽く6,7倍速い。
  もしInteger#prime?が遅いというなら、Rubyでより速い素数判定を再実装できます。
• 2のn乗は、1 << nが、2**nや2.pow(n)より桁違いに速い。
• 2乗するとき、x * xは、x**2やx.pow(2)よりも1.8倍速い。
• 原点からの距離を求めるとき、Math.sqrt(x * x + y * y)が、Math.hypot(x, y)よりも少し速い。
• popcountは、i.to_s(2).count("1")が、i.digits(2).sumより速い。Integer#to_sもString#countも高速。
• 数があまりに大きいときのInteger#digitsは、Rubyで実装し直した方が速い。
• Integer#bit_lengthは、その他の方法より速い。

その他の高速化

• 状況に応じてSet, Hash, Arrayなどを使いわける。
• 要素を入れつつ常に重複を除外して要素を格納するときは、HashやSetを使う。
  Arrayでuniq!を使ったら、毎回全要素を調べO(n)なので、同じ配列に何度もuniq!する状況は変。
• dupの方が速い。cloneの方が考慮する情報が多めでほんの少し遅い。
• ランダム整数の取得は、Random.rand(n)が、rand(n)より速い。
  rand(n)は、rand(0...n)より速い。rand(0...n)は、Random.rand(0...n)より速い。
• クラス変数のアクセスは、その他の変数のアクセスより1.6倍ぐらい変に遅い。
• 再帰関数が遅い印象です。再帰関数を使うより、非再起にすると少し速いです。
  また、Rubyのデフォルトだと、再起をできる上限が厳しいです。
  AtCoderでは上限を大きくしてくれていて普通に使えますが、その他のジャッジシステムだと厳しいかもしれません。
• メソッド定義でブロックを使うとき、yieldのみが速い。
• アルゴリズムレベルの話ですが、セグメントツリーは、再帰型ではなく、非再帰型に。
• セグメントツリーの要素に配列を乗せると遅いので、配列を避けれるなら避ける。
• 計算量のlogをとる。速い言語だと、計算量の中のlogは小さいから考えなくてもいいという話もあります。
  RubyでTLEになるケースで、想定解法からlogをとればACできたりします。
  例えば、線形探索の中で二分探索するケースをしゃくとり法に書き換えると通ることがあります。
• 競プロ用のac-library-rbを使う。高速化というか、時短術? 速いものを心がけて作っているつもりです。

だいたいのケースで10**6 = 1_000_000ほどの要素数・ループ数で計測してます。
何倍速いかも参考値として書いていますが、特定の条件下でのスピードなので過信は禁物です。
また、1.1倍レベル等のスピード差は、全体としてのインパクトは大きくないことに留意が必要です。
小さなスピードにこだわって、可読性が下がったり、アルゴリズムの計算量が悪かったりしたら、元も子もありません。
ただ、塵も積もれば山となるかもしれないので、最終手段として知っておいてもよさそうです。
ループでの計測は、純粋な比較のためには空ループの時間を取り除く必要があると思われますが、実践的な感覚に近いかと思い、そのままです。

標準ライブラリの範囲内で計測したかったので、benchmarkライブラリを基本的に使用しています。しかし、並び順を変更するだけで速さが変わるケースもあるので、結果の過信は禁物です。(大きめの)配列を作るときに誤った結果がでやすいです。これは、Benchmakr.bmをBenchmark.bmbmに変えるだけで、軽減されることもあります。

入出力

基本的な入力

RubyとCrystalの両方で使える標準的な入力を示します。
(Rubyのみ考えるとき、to_sは不要で、map(&:to_i)の短い書き方ができます。)

n = gets.to_s.to_i  # 整数1つを受け取る(1行に1つ整数がある前提)
s = gets.to_s.chomp # 1行を文字列として受け取る(chompで最後の改行を切り落としている)
a = gets.to_s.split.map{ |e| e.to_i } # 横1行のスペース区切りの整数を配列として受け取る
a = Array.new(n){ gets.to_s.to_i } # n行1列の改行区切りの整数を配列として受け取る
m = Array.new(n){ gets.to_s.split.map{ |e| e.to_i } } # n行m列の整数を2次元配列で受け取る

これぐらいの入力を用意すると、本番でコピペ・コメントアウト・ちょっとした編集で済むので楽です。
一時期テンプレートも作ってましたが、使わないと忘れ鬱陶しいので、自分はこの形に落ち着きました。
また、1行に2つある整数を別々の変数で受け取るときは、多重代入の形にします。

# 「10, 20」のような1行の入力を想定
n, m = gets.to_s.split.map{ |e| e.to_i } # 配列から多重代入

引数なしのgetsメソッドは、改行までの1行を読み込み、文字列を返します。
これは最後に改行を含むため、そのまま文字列で扱うなら、chompで改行を落とします。
また、整数値にするto_iは、後ろに非数字が来ると無視するので、chomp不要です。

【罠】紛らわしいメソッド名

String#splitとは別にString#stripというメソッドがあります。全くの別ものです。
String#chompとは別にString#chopというメソッドがあります。動作も似てます。

入力時のソートなど

入力後すぐソートしたいときがあり、昇順にするならsortし、降順ならsort.reverseします。
ブロックで並び順を指定するときは、sortではなく、sort_byを使います。

2次元配列の縦と横を入れかえたい、つまり転置させたいときはtransposeを使います。

gets, readline, readlines

Rubyではgetsと似たメソッドでreadlineがあり、さらにreadlinesがあります。
少し紛らわしいですが、getsのsはstringのsで、readlinesのsは複数形のsです。
getsとreadlineが対応関係にあります。
getsとreadlineの違いは入力がなかったときにエラー返すかどうかで、競プロの提出コードでエラーをだすことはなくreadlineは長いので使われません。ただ、readlinesは、残りの入力全てを改行区切りで文字列の配列にしてくれるので使いみちがありそうです。

入力メソッドのまとめ

メソッド	通常の返り値	入力がなかったとき
gets	文字列	nilを返す
readline	文字列	エラーになる
readlines	文字列の配列	空配列を返す
ARGF, $<	ARGFオブジェクト	左同
`dd`	文字列	空文字列を返す

いきなりでてきた$<や`dd`は、短いコードを書きたいゴルフ向けなので、ここでは紹介しません。

基本的な出力

基本は、putsを使います。
手元でのデバッグのための出力は、pかppを用いるのがいいです。
複数の変数を確かめたいとき、配列にいれてpで出力すると、1行でシンプルに出力されていいです。

n, m = 0, 1
p [n, m] #=> [0, 1]

Ruby 2.5から、requireしなくてもppを使えるようになりました。

Rubyのメソッドは丸括弧を書いても書かなくてもいいですが、
出力時には丸括弧を書かない人が多そうです。

数値の出力は、文字列にまとめてまとめて出力する

Integer等の出力はputsでもpでも出力の表示は同じですが、putsを使うべきです。
オンラインジャッジではpで数値を出力すると異常に遅くなることがあります。

くさころさんのツイート

Rubyでpの代わりにputsを使うと460msほど縮まった
pはinspectで整形してるのでたしかに時間かかりそう
https://atcoder.jp/contests/past202005-open/submissions/14080203

この問題の提出は、pが949ms(0.94秒), putsが483ms(0.48秒)と全体で倍近い差です。
たくさんのループのたびに数値を出力すると、かなりの差になりうるので、気をつけましょう。

さらに、そもそも、ループのたびに出力するのは、遅くなる原因です。
ループのたびに1つの文字列の変数に<<で末尾に追加し、最後にまとめて出力すると速くなりえます。
文字列に数値を数字にして改行つけて詰めるのが嫌なら、配列に数値を入れてもいいかもしれません。

以下が、それぞれを比較したときの計測タイムです。それぞれ数回ほど測っています。

n = 1_000_000

# Bad: 1913ms ~ 1938ms
n.times{ |i| p i }

# Good: 499ms ~ 510ms
n.times{ |i| puts i }

# Good: 468ms ~ 493ms
ans = []
n.times { |i| ans << i }
puts ans

# Good: 308ms ~ 333ms
ans = ""
n.times { |i| ans << "#{i}\n" }
puts ans

上記のようにかなり差がでます。AtCoder及びyukicoderで確認済みです。

文字列とシンボルの出力

putsだと文字列もシンボルも同じように出力されますが、一般的な文字列の方が速いです。

# frozen_string_literal: true
n = 1_000_000

# Bad:
# Symbol: 468ms ~ 473ms
n.times{ puts :Yes }

# Good:
# Not frozen: 289ms ~ 292ms
#     frozen: 213ms ~ 215ms
n.times{ puts "Yes" }

putsの内部では一般にto_sが適用され、シンボルはto_sでの変換作業という重たい時間があります。
対して、Stringをputsで出力する際は、String#to_sは使われずそのまま出力されます。
そのため、変換作業という追加時間のあるシンボルの方が時間がかかります。

また、# frozen_string_literal: trueを使うと、
同一内容は同じオブジェクトになり文字列の生成時間が減り、タイムがさらに縮みます。

配列(Array)の出力

配列に対するputsは、配列の要素を改行区切りで出力します。
putsの内部で、Array#to_sは実行されません。
もし1次元の配列の要素をスペース区切りで出力したいときは、joinメソッドで引数に区切りをとって、文字列にして出力します。
ここで、ループする形で、各要素を1つずつputsで出力させると遅くなると思います。
また、2次元の配列の中で、中の配列ごとにスペース区切りで結合したいときは、mapのブロック内でそれぞれjoinで結合させる文字列の配列にすると楽だと思います。

puts [0, 1, 2].join(' ')
# 0 1 2

puts [[1, 2], [3, 4]].map{ _1.join(' ') }
# 1 2
# 3 4

三項演算子こと条件演算子の組み合わせ

条件によって"Yes"か"No"の形で出力させる問題は、よくあります。
そのときに、ifではなく、条件演算子と組み合わせると1文で書けます。

if x == 0
  puts "Yes"
else
  puts "No"
end

puts x == 0 ? "Yes" : "No"

ところで、問題により"Yes"か"YES"か出力すべき形式が異なるので、注意してください。

puts以外の出力

改行したくないときは、printを使います。
なお、今のAtCoderの問題は、最後に改行がなくても行末に余計な空白があってもACできると思います。
しかし、昔のAtCoderや他サイトは違う可能性があるので、
出力に余計な空白はださないようにし、出力の最後は改行で終わらせるようにしましょう。

基本的な話

基本的な繰り返し(ループ)の処理

基本的な繰り返しの処理でよく使うのは、times, each, each_with_index, whileです。
また、降順で回すために、downtoやreverse_eachのようなメソッドも知っておくべきでしょう。

【高速化】loopは使わず、whileを使う

rubyのループ(loop, each, while, for)の速度のベンチマーク - 僕のYak Shavingは終わらない
上記のサイトによれば、Ruby 2.1で、whileが1番速く、loopが1番遅いとのことです。
同じ形式で、Ruby 2.7.1でも速度を比較してみましたが、同じ結果でした。
0から1_000_000まで回していき、配列に入れていく形式です。

            user     system      total        real
for     0.054588   0.000196   0.054784 (  0.054873)
each    0.043246   0.007900   0.051146 (  0.051152)
times   0.046832   0.003898   0.050730 (  0.050736)
while   0.031687   0.000078   0.031765 (  0.031770)
loop    0.070367   0.000522   0.070889 (  0.070899)

条件によって色々変わってくると思いますが、イメージとしては下記です。
while >> times = each > for >> loop
もしtimesで遅くて困ったら、奥の手としてwhileに書きかえると速いかもしれません。
forは単にeachを呼んでるだけなので、eachより遅めです。
whileは、配列が空になるまで要素を出し入れしするような、ループ数が定まらない場面などでよく使います。

降順もwhileは最強。reverse_eachは、遅い。

require "benchmark"
n = 10**6
Benchmark.bm(11) do |r|
  r.report("while       "){ i = n; while 0 < i; i; i -= 1 end }
  r.report("downto      "){ n.downto(1){ |i| i } }
  r.report("times       "){ n.times{ |i| n - i } }
  r.report("each        "){ (0...n).each{ |i| n - i } }
  r.report("reverse_each"){ (1..n).reverse_each{ |i| i } }
end
#                   user     system      total        real
# while         0.015437   0.000462   0.015899 (  0.015966)
# downto        0.037656   0.000083   0.037739 (  0.037741)
# times         0.040859   0.000972   0.041831 (  0.041837)
# each          0.041974   0.000000   0.041974 (  0.041982)
# reverse_each  0.061864   0.000613   0.062477 (  0.062480)

whileは、やはり高速でした。reverse_eachの4倍近いタイムで優勝です。
reverse_eachは、残念ながらタイムでeachに負けてしまいました。

なお、ここで計測したeachとreverse_eachは、Enumerableモジュールで定義されたメソッドである点に注意です。
Arrayでは、eachやreverse_eachが再定義され、どちらも同等の速さでした。
Arrayは、Enumerableを継承しているものの、効率化のため再定義しているものが多い印象で、Enumerableモジュールと同名のメソッドでもArrayで再定義されているものは性能が異なる部分があるので注意が必要です。

【高速化】ブロックでループできるメソッドはeachに渡さずにブロックで回す

高速化Tipsとして、ブロックに渡して回せるメソッドはたくさんあるので、それをそのまま使うといいです。
ブロックに渡して回せるメソッドなのにto_a.eachやらeachやらつけると、中間で配列やら作るため遅くなるようです。

Array …… zip, product, permutation, combination、repeated_permutation, repeated_combination
String …… chars(each_char), bytes(each_byte), split, scan

require "benchmark"
n = 10 ** 5
str = "abcdefghijklmnopqrstuvwxwz\n" * n
Benchmark.bm(4) do |r|
  x = r.report("split     "){ str.split{ |t| t } }
  z = r.report("split.each"){ str.split.each{ |t| t } }
  p z.real / x.real
end

#            user     system      total        real
# split       0.021684   0.000000   0.021684 (  0.021752)
# split.each  0.032365   0.000000   0.032365 (  0.032368)

上記の例だと、1.5倍前後ぐらい遅くなります。

swap

多重代入は、単に複数の代入だけでなく、配列からの代入もでき、スワップもできます。

n, m = 0, 1
n, m = m, n
p [n, m] # [1, 0]

基本的な数値計算 〜Integer及びArray(Integer)

四則演算

整数どうしの和、差、積は、義務教育の算数・数学と同じです。
ただ、整数どうしの/による割り算は、floor divisionといって、端数切捨ての整数を返します。

p 5 / 2  #=>  2
p 5 % 2  #=>  1

また、整数どうしの割り算で、浮動小数点数を得たいときがあります。
ほんの少しバリエーションがあり、一応差があるか気になり検証しました。
結果、専用のInteger#fdivだけ、数が大きいほど何倍も遅くなりました。

require "benchmark"
n = 10**6
m = 10**6
a = [*m...m+n]
# a = Array.new(n){ rand(m) }
Benchmark.bm(5) do |r|
  r.report("fdiv"){ a.each_slice(2){ |x, y| x.fdiv(y) } }
  r.report("1.0 "){ a.each_slice(2){ |x, y| 1.0 * x / y } }
  r.report("i/f "){ a.each_slice(2){ |x, y| x / y.to_f } }
  r.report("f/f "){ a.each_slice(2){ |x, y| x.to_f / y.to_f } }
  r.report("f/i "){ a.each_slice(2){ |x, y| x.to_f / y } }
end
#             user     system      total        real
# fdiv    0.135053   0.000625   0.135678 (  0.135680)
# 1.0     0.073159   0.000000   0.073159 (  0.073162)
# i/f     0.073409   0.000000   0.073409 (  0.073412)
# f/f     0.071910   0.000000   0.071910 (  0.071922)
# f/i     0.069651   0.000000   0.069651 (  0.069657)

Integer#fdivは、誤差を減らすため、速さが犠牲になっているのかもしれません。
次のようなケースで、fdivの方が少し精度が高いことがわかります。

x, y = [10**29, 10**4]
p x.fdiv(y)  #=> 1.0e+25
p x.to_f / y #=> 9.999999999999999e+24

大半の場面では何を選んでも小さな差でしょう。
ただ、極端に大きい整数を扱うようなら、精度か速さか考えていいかもしれません。
なお、(競プロでは)誤差が許容されない限り、浮動小数点数は避けるのが鉄則です。

また、有理数・分数のRationalクラスもあり、
Integer#quoやKernel#Rationalで分数を作ることもたまにあります。

負数の絡む割り算

非負整数どうしの割り算は、C言語と同じです。
しかし、負数が絡む割り算は定義が1つでなく、言語によって商と剰余が異なります。
負数により割られ余りがあるとき、C言語は負数を返しますが、Rubyは正数を返します。

割られる数	割る数	Ruby	C言語
7	3	商 2, 余り 1	商 2, 余り 1
-7	3	商-3, 余り 2	商-2, 余り-1
7	-3	商-3, 余り-2	商-2, 余り 1
-7	-3	商 2, 余り-1	商 2, 余り-1

競プロの問題では、答えを特定の数で割った余りを求めさせることがあります。
ふつう答えとして求めるべき余りは、非負整数です。
しかし、C言語では対策していないと、負の余りが生じてしまいWAになりやすいです。
この点、Rubyは、正数で割る限り正数が返るのでひっかからなく安心です。

その他の演算子の記号メソッド

p 5 ** 2 #=> 25
p 5 ^ 1  #=>  4
p 5 & 1  #=>  1

**は累乗です。JavaScriptでもサポートされ、メジャーな演算子になった印象です。
^は、ビット演算の排他的論理和(xor)です。xorは、性質が面白いので、問題として出題されます。
&は、ビット演算の論理積です。ビット演算のメソッドは、高速な印象です。

最大公約数、最小公倍数

Rubyでは、簡単に最大公約数(GCD)・最小公倍数(LCM)を求められます。

12.gcd(10) #=> 2
12.lcm(10) #=> 60

数値の配列Array(Integer)

配列の全要素の総和・総乗・最大公約数・最小公倍数

数値の配列の総和は、sumメソッドを使います。
総乗などは、injectメソッド(reduceはエイリアス)を使います。
reduceよりinjectを使っている人が多い気がしますが、
Crystalだとreduceオンリーなのでコードはreduceで書きます。

p [1, 2, 3, 4, 5].sum           #=> 15 # Ruby 2.4以降
p [1, 2, 3, 4, 5].reduce(0, :+) #=> 15 = 0 + 1 + 2 + 3 + 4 + 5
p [1, 2, 3, 4, 5].reduce(1, :*) #=> 120 = 1 * 1 * 2 * 3 * 4 * 5
p [180, 36, 360, 99].reduce(0, :gcd) #=> 9 = 0.gcd(180).gcd(36).gcd(360).gcd(99)
p [1, 2, 3, 4, 5].reduce(1, :lcm) #=> 60 = 1.lcm(1).lcm(2).lcm(3).lcm(4).lcm(5)
p [1, 2, 3, 4].reduce(0, :^) #=> 4 = 0 ^ 1 ^ 2 ^ 3 ^ 4 # xor(排他的論理和)

引数でとっている:始まりのものは、Symbolです。
injectは、メソッド名を表したSymbolを引数にとれる設計です。

空配列のsumメソッドは、0を返してくれます。
しかし、injectは、空配列のときに引数がメソッド名のみだとnilを返す罠があります。
第1引数で初期値(単位元)を渡して、第2引数でメソッド名(:Symbol)を渡すようにするといいです。
(引数の数で、メソッド名の引数の位置が変わるの、変な感じ……)
空配列がくるようなケースはそんなに多くないでしょうが、たまにあると思うので日頃から気をつけたいですね。

あと、競プロでたくさんの数をそのまま総乗してしまうと、膨大な数になってTLEになるので注意しましょう。

【罠】【高速化】inject

基本、総和のときはArray#sumを使った方がいいです。
Array#sumは、カハンの加算アルゴリズムを用いていて、inject(:+)よりも浮動小数点数を扱ったときの精度が高く、計算も速いらしいです。
ただ、競プロで扱わないような10**16のような数値を超えてくると、sumが遅くなりinject(:+)が勝ちました。
なお、総和の中で、sumやinject(:+)は、他のinject(&:+)より桁違いに速かったです。
inject(&:+)はブロックの省略記法であり、Rubyではブロックを扱うケースは扱わないそれと比べて遅いと知っておくとよさそうです。

require "benchmark"
n = 10**6
m = 10**6
a = [*m..m+n]
x, y, z, w, s = nil
Benchmark.bm(10) do |r|
  r.report("sum        "){ x = a.sum } # 2.4で導入されたsumメソッド。誤差を軽減する。
  r.report("inject(:+) "){ y = a.inject(0, :+) } # injectはブロックを使う方法と使わない方法がある。
  r.report("inject{_1} "){ z = a.inject(0){ _1 + _2 } } # 2.7で導入されたナンパラ(Numbered parameters).
  r.report("inject{|| }"){ w = a.inject(0){ |s, e| s + e } } # クラッシクな普通のブロックの記法
  r.report("inject(&:+)"){ s = a.inject(0, &:+) } # Symbol#to_procを利用したブロックの省略記法(1.8->1.9あたりで入った)
end
p [x, y, z, w, s]

#                 user     system      total        real
# sum          0.000797   0.000585   0.001382 (  0.001379)
# inject(:+)   0.001136   0.000833   0.001969 (  0.001971)
# inject{_1}   0.061964   0.000000   0.061964 (  0.061967)
# inject{|| }  0.061409   0.000000   0.061409 (  0.061414)
# inject(&:+)  0.079613   0.000000   0.079613 (  0.079617)

上記の引数に単純にinjectにSymbolを与えればすむ単純なケースは、総和以外でも速そうでした。
間違えそうなのが、Symbolの:の前に&をつけてしまう記法です。
&をつけるのは、injectに限らない一般的なブロックの省略記法です。
対して、&をつけないのは、inject固有のSymbolを引数に渡すやり方です。この固有の方法は、他のinjectの方法に比べて10倍速そうです。

ブロックの速さは、どんぐりの背くらべ

ブロックを使った書き方は、3種類ぐらいあるのかなと思ってます。

• map{ |e| e.to_i } …… クラシックなブロックの書き方。Crystalでも動く書き方。
• map(&:to_i) …… 1.8〜1.9で入ったSymbol#to_procによる省略記法。特定条件下で省略可。
• map{ _1.to_i } …… 2.7で入ったナンパラ(Numbered parameter)

メソッドによりそうですが&を使った省略記法は、遅いことや変わらないことはあっても、速いことはなさそうでした。
&を使った省略記法は&がSymbol#to_procを呼び出してブロックに展開するイメージでちょっとは遅くなると思ったのですが、
inject!のようにちょっと遅くなるメソッドもあれば、mapのように計測しても変化が感じられないメソッドに分かれました。
また、2.7で導入されたNumbered parameter_1も特に速くも遅くもなくという感じでした。

map(&:to_s)がmap{ |i| i.to_s }よりも速いという記事も見ましたが、Benchmarkで計測すると並びに左右されるという結果になり、あまり差を感じなかったです。

結論、もしブロックの書き方によって速さに差がでたとしてもどんぐりの背比べなので、可読性が高いものを使用すべきでしょう。

余りを求める

【高速化】総和の余りは、最後に余りをとる

理論上の答えが巨大な数になるときに、1_000_000_007などの素数で割った剰余を答えとして求められることがあります。

C++のような言語は整数型に上限がありオーバーフローしないように計算する必要があります。
しかし、RubyのIntegerは多倍長整数でオーバーフローしないので、C++ほど剰余を求めなくていいことがあります。
例えば、和だけの場合は、「巨大な数との和」よりも、「普通の割り算」のコストが高いようです。
対して、積の場合は、途中で剰余を取らないと積がすぐ破茶滅茶に巨大な数になるため、途中途中で割り算をするコストより、「破茶滅茶に巨大な数との積」のコストの方が高くつくようです。

以下のコードと表が、和だけの場合に、いつ余りを求めるのが速いのかを示すものです。

require 'benchmark'

mod = 1_000_000_007

s = 10**7 # 和を求める数値のスタート(最初の数)
d = 10**6 # 和を求める数値の個数
ans0, ans1, ans2 = 0, 0, 0
Benchmark.bm(5) do |r|
  r.report("always"){ (s..s+d).each{ |i| ans0 = (ans0 + i) % mod  } }
  r.report("mod if"){ (s..s+d).each{ |i| ans1 = (ans1 + i);
                      ans1 %= mod if ans1 > mod            } } # %=
  r.report("last  "){ (s..s+d).each{ |i| ans2 += i };   ans2 %= mod }
end

p [ans0, ans1, ans2]
#             user     system      total        real
# always  0.059954   0.002514   0.062468 (  0.062588)
# mod if  0.055133   0.000502   0.055635 (  0.055635)
# last    0.046476   0.000086   0.046562 (  0.046561)

「always」は、足し算の都度、余りを求めるケースです。
「mod if」は、足し算の結果がmodを超えたときのみ余りを求めるケースです。
数が小さくてifによって割り算の回数が減るときは「mod if」が高速でしたが、
逆に数が大きすぎるときは常に比較時間が増えるだけなので「mod if」は遅くなりました。

そして、「last」が、総和の最後にだけ余りを求めるケースで、割り算がたった1回のみで、前述の2つより速かったです。

【高速化】総乗の余りは、その都度余りをとる

総和の余りを求めるコードの計測をしたように、総乗の余りをとる実験をしてみました。
2をかけ続ける実験です、
こちらは、1番速かったのが、常に積を求めるたびに割って余りを求めるケースでした。
最後にのみ余りを求めるケースは、すごく遅くなりました。
掛け算によって生じる大きめの数の余りを求めるコストは、とても高いようです。
2の総乗でも、その都度、余りをとる方法が1番速かったので、掛け算が絡むところでは毎回余りを取るのが1番良さそうです。

なお、同じ数をかける個数が決まっている場合は、Integer#powを使うのが1番速いです。

累乗(るいじょう)、冪剰余(べきじょうよ)

累乗の計算は、**とpowが使えます。
powメソッドは、第2引数で剰余を求めるための法をとれます。
剰余を求めるときは**ではなくpowを使います。

# Bad
(i**j) % mod

# Good
i.pow(j, mod)

※、i, j, modは、Integerです。

**の方は、膨大な数になって計算が遅くなり、最悪計算をやめて警告をだしてくれます。
対して、powは、内部で適切に途中途中で剰余をとっているので計算が高速です。

最大値・最小値

Array#maxの返り値

空配列のsumメソッドは、0を返します。
しかし、空配列のmax/minメソッドはnilを返します。

配列が空配列をとる可能性があり、特定の数値を返して欲しいときは次のように書けます。

a = []
m = a.max || 0

a = []
m = a.max.to_i

nil.to_iは0を返すので、0を返して欲しいときだけto_iが使えます。
nilを返してくるメソッドはたくさんあるので、1例でした。

Array#maxを利用した最大値・最小値

最大値を更新していく場面やいくつかの変数の最大値を求めたいときに、一時的な配列でmaxを使う方法があります。
昔のRubyだとArrayでmaxを使うと何倍も遅かったですが、2.4以降で大幅に改善されています。
ただ、差のないレベルですが、シンプルなケースではifや条件演算子を使った方が1.1倍ほど速いです。

require "benchmark"
n = 10**6
a = Array.new(n){ |e| rand(n) }
Benchmark.bm(8) do |r|
  x = r.report("Array#max"){ m = 0; a.each{ |e| m = [m, e].max } } # 昔は、何倍も遅かった
  y = r.report("if m < e "){ m = 0; a.each{ |e| m = e if m < e } }
  p x.real / y.real
end

#               user     system      total        real
# Array#max  0.052035   0.000000   0.052035 (  0.052036)
# if m < e   0.045816   0.000180   0.045996 (  0.046000)
# 1.1312083084045146

ゼロ判定、正負判定、偶奇判定

ゼロかどうかの判定は、i == 0だけでなく、Rubyではi.zero?と書けます。
同様に、正負判定はi > 0・i < 0だけでなく、i.positive?・i.negative?と書けます。
また、偶奇判定は、i % 2 == 0・i % 2 == 1だけでなく、i.even?・i.odd?と書けます。
それだけでなく、偶奇判定は、ビット演算の方法があと2種類ぐらいあります。

記事を書いていて、速さが気になり、計測してみました。以下は、奇数の判定です。

require 'benchmark'
n = 10**6
m = 10**14
a = Array.new(n){ rand(m) }
Benchmark.bm(8) do |r|
  r.report("odd?    ") { a.each{ |e| e.odd? } }
  r.report("% 2 == 1") { a.each{ |e| e % 2 == 1 } }
  r.report("[0] == 1") { a.each{ |e| e[0] == 1  } }
  r.report("& 1 == 1") { a.each{ |e| e & 1 == 1 } }
end

#               user     system      total        real
# odd?       0.063735   0.000034   0.063769 (  0.063770)
# % 2 == 1   0.059971   0.000030   0.060001 (  0.060004)
# [0] == 1   0.049855   0.000093   0.049948 (  0.049951)
# & 1 == 1   0.049756   0.000000   0.049756 (  0.049758)

上記は、奇数の判定でしたが、偶数も同様でした。
偶奇判定の場合、ビットで判定する方法が、ほんの1.2倍〜1.3倍速そうでした。
i & 1 == 1が、明らかにi.odd?やi % 2 == 1よりも速い感じです。
なお、乱数だと% 2 == 0がodd?よりもわずかに速い傾向がありましたが、連番で試すとそうならなかったです。
不思議な結果でしたが、誤差レベルで気にしたら負けな感じがします。
また、Rubyらしいi.zero?よりもi == 0で判定する方が、1.2〜1.3速かったです。
さらに、正負判定は、i > 0・i < 0が、i.positive?・i.negative?より、1.4倍速かったです。
このあたり、全体的にIntegerに関しては、ビット演算やRubyぽくない書き方の方が速い印象です。

実際問題、ビット演算の書き方は変態ですし、odd?やeven?の方がわかりやすくていい気がします。

浮動小数点数の誤差を避ける

Rubyに限らず一般的な浮動小数点数は、誤差を伴うこと等の様々な罠があります。
浮動小数点数を避けるテクニックや危険性を以下に書いていきます。

商の切り上げで、浮動小数点数をださない

C言語と同様、Rubyは/による整数どうしの割り算で、端数を切り捨てた整数を返します。
反対に、端数を切り上げた整数を得たいときは、次の手法をとります。

# Bad
( n.to_f / m ).ceil

# Good
( n + m - 1 ) / m

※n, mは整数(Integer)です。

C++やPythonでも見られる一般的な競プロTipsです。
実際、誤差が原因でWAになることもあります。また、整数と浮動小数点数の計算が混じると、少し遅くなるようです。

浮動小数点数以外の数値クラス

誤差をなくす方法は色々とありますが、浮動小数点数以外の数値クラスを使うのも1つの手です。
Rational(有理数, 分数)やBigDecimal(10進浮動小数点数)です。
BigDecimalはrequireでインポートして使えるようになります。

指数表記の浮動小数点数リテラル

eを使った指数表記は、浮動小数点数リテラルでFloatが返るので注意します。
他言語だと型を明示的に指定してキャストするようで、浮動小数点数リテラル感が見えなくなるようです。

1e4 #=> 10000.0

Integerで十分なときは、最初から**を使いましょう。

浮動小数点数の出力

puts 10.0 ** 16 #=> 1.0e+16
puts 0.00009    #=> 9.0e-05

こういうのはRubyに限らないでしょうが、
浮動小数点数は、大きすぎたり小さすぎたりすると、eを使った指数表記で出力されます。
ジャッジによって指数表記の出力を許容したりしなかったりするので、気をつけましょう。

【高速化】Float::INFINITY

inf = Float::INFINITY

Rubyには、無限大を表すFloatクラスの定数があります。
最小値を求めるときに暫定値として入れる等、色々と使いみちがあります。
ただ、整数がベースの問題では、このFloatの無限大より、適当な整数(10**18)などを使った方が速いです。
IntegerとFloatを一緒に使うと、クラスを判定したりクラスを揃える処理をしたりするので、遅くなっています。
整数値の最短距離を求めるグラフ問題で、頂点数や辺が多いときは、適当な整数にした方がいいでしょう。

require 'benchmark'
n = 1_000_000
a = Array.new(n){ rand(n) }
Benchmark.bm(14) do |r|
  r.report('big integer    '){ inf = 10**18; a.each{ |e| e < inf } }
  r.report('big float      '){ inf = 10e18;  a.each{ |e| e < inf } }
  r.report('Float::INFINITY'){ inf = Float::INFINITY; a.each{ |e| e < inf } }
end

#                     user     system      total        real
# big integer      0.043069   0.000065   0.043134 (  0.043136)
# big float        0.068930   0.000270   0.069200 (  0.069208)
# Float::INFINITY  0.067209   0.000050   0.067259 (  0.067275)

真偽値

Rubyで、偽となるのはfalseとnilのみで、覚えやすいです。

他言語では0、0.0、空配列、空文字列が偽になる言語も少なくないです。
この点、他言語のコードを参考にするときに、書き間違えやすいです。

nil判定

nilかどうか判定したいときは、nil?メソッドを使います。
obj == nilではなく、obj.nil?という書き方がRubyらしい書き方です。

Rubyらしい書き方が速いのか気になったので、計測してみました。計測結果は、以下です。

require "benchmark"
n = 10 ** 6
a = Array.new(n)
a = Array.new(n){ "str" }
a = [*0...n]
Benchmark.bm(6) do |r|
  r.report("nil?  "){ a.each{ |e| e.nil? } }
  r.report("!     "){ a.each{ |e| !e } }
  r.report("== nil"){ a.each{ |e| e == nil } }
end
#              user     system      total        real
# nil?     0.043702   0.000000   0.043702 (  0.043709)
# !        0.043984   0.000000   0.043984 (  0.043990)
# == nil   0.206171   0.000080   0.206251 (  0.206256)

結果として、Rubyらしい書き方nil?が、1番速かったです。
レシーバがnilのときnil?と==は1.1倍程度の差ですが、
レシーバがArray, Hash, Stringのとき軽く2倍の差になり、
レシーバがIntegerのとき軽く4〜5倍の差になりました。

なお、否定の!は、nilとfalseをtrueにするので、falseに対する働きが他と違います。

空配列、空文字列の判定

sizeメソッドの返り値が0かを見ても同じですが、Rubyではempty?メソッドが使われます。
配列でも文字列でも、a.size == 0よりa.empty?の方が少し速かったです。

問題は、この逆の配列に要素があるかを判定して実行するケースの書き方です。
どれも表記的に甲乙つけがたかったので、時間計測してみました。その結果が以下です。

require "benchmark"
n = 10**5
m = 10**3
arrays = Array.new(n){ Array.new(rand(m), 0) }
Benchmark.bm(17) do |r|
  r.report("unless a.empty?   "){ arrays.each{ |a| x = 0 unless a.empty? } }
  r.report("if !a.empty?      "){ arrays.each{ |a| x = 0 if !a.empty? } }
  r.report("if a.empty?.!     "){ arrays.each{ |a| x = 0 if a.empty?.! } }
  r.report("unless a.size == 0"){ arrays.each{ |a| x = 0 unless a.size == 0 } }
  r.report("if a.size != 0    "){ arrays.each{ |a| x = 0 if a.size != 0 } }
  r.report("if a.any?         "){ arrays.each{ |a| x = 0 if a.any? } }
end

#                         user     system      total        real
# unless a.empty?     0.004705   0.000298   0.005003 (  0.005000)
# if !a.empty?        0.005608   0.000000   0.005608 (  0.005610)
# if a.empty?.!       0.005410   0.000000   0.005410 (  0.005411)
# unless a.size == 0  0.005470   0.000000   0.005470 (  0.005471)
# if a.size != 0      0.005763   0.000000   0.005763 (  0.005765)
# if a.any?           0.016315   0.000000   0.016315 (  0.016318)

何回か計測して、この中でトップとビリはいつも同じでした。
トップはunless a.empty?。ビリはif a.any?。間は、抜いたり抜かされたり。

この中で、否定を使わないany?は読みやすく期待しましたが、any?は想像以上に遅くビリでした。
false・nilのない配列なら、any?でも判定はO(1)でそこまで変わらないかと甘く見てました。
結論、any?は遅いし挙動も違うしあまり使われず否定派の方が多いので、よくないです。

あと、このif e.empty?.!という記法をごく最近知ったのですが、使っている方いわく「見た目はだいぶ気持ち悪いが、カーソルを後ろに戻さなくて済む」とのことです。

||(or演算子)による短絡評価

Rubyは、なにかにつけてnilを返すものが多いです。

• Array、Hashの範囲外参照
• 指定のないArray.newによる初期化の要素
• 未代入のインスタンス変数、未代入のグローバル変数
• 空配列のとき(max, min, inject, pop, shift, !つき破壊的メソッドの一部など)

ただ、nilが返ってきたときに、nil以外の値を使いたいケースが多いです。
そういうときは、||(or演算子)を利用した短絡評価を使うと、スッキリ書けます。
||の左側が真の要素ならそのオブジェクトを返し、偽のときだけ右側を評価して返します。
そのため、nilが返ってきたときにだけ、別の値を返したいときは||を使います。
さらに、nilのときに、更新した上で返したい場合は、自己代入の||=を用います。

x = obj || 0 # objの評価が真ならobjを返し、objがnilかfalseなら右側を評価して返します。
x = obj ||= 0 # objがnilかfalseなら右側を評価して、objに代入します。

Array#fetchは引数を評価したり、ブロックを取ったりできる分、短絡評価より少し遅い印象です。
競プロでfetchを使う方は、あまり見ない気がしますね。

Array

イミュータブルな同一数値での配列の作成

同じ数値で埋めた配列を作りたいときは、いくつかの方法があります。

n = 5

x = [0] * n
y = Array.new(n, 0)
z = Array.new(n){ 0 } # 同一数値を作るだけなら、ブロックを要素数の数だけ実行し、上2つより遅い。

計測するとArray.new(n, 0)の方が少し速そうでしたが、一般的な[0] * nで十分でしょう。
ただし、両者とも2次元配列は作るとき、例えば[[]] * nとすると、内側の要素としての各空配列が全て同じオブジェクトになってしまいます。換言すると、同じオブジェクトID、同じオブジェクト参照値を持ってしまいます。Pythonなどもこうですが、最初は直観と反してしまう挙動だと思います。

require "benchmark"
n = 10**6
Benchmark.bm(11) do |r|
  x = r.report(".new(n, 0)  "){ Array.new(n, 0) }
  y = r.report("[0] * n     "){ [0] * n }
  z = r.report(".new(n){ 0 }"){ Array.new(n){ 0 } }
  w = r.report("n.times.map "){ n.times.map{ 0 } }
  s = r.report("(0...n).map "){ (0...n).map{ 0 } }
end
#                   user     system      total        real
# .new(n, 0)    0.000250   0.004121   0.004371 (  0.004370)
# [0] * n       0.000514   0.004341   0.004855 (  0.004874)
# .new(n){ 0 }  0.043284   0.007565   0.050849 (  0.050919)
# n.times.map   0.061078   0.000310   0.061388 (  0.061392)
# (0...n).map   0.056501   0.004056   0.060557 (  0.060563)

一般に、ブロックを使う方法は応用がきく一方で、引数に初期値を指定する方法より遅いです。
配列の初期化も同様で、Array.new(n){ 0 }は、Array.new(n, 0)より遅いです。
今回は、桁違いに速く10倍の差がつきました。
実践でも、760ms台と450ms前後と0.3秒もの差がつくことがあったので、引数指定できるときはすべきです(PAST002 K - 括弧)。
配列の新規作成でも要素を1つ作るたびにブロックを呼び出してしまうので、要素が数値のようにイミュータブルで同一オブジェクトで済むケースはブロックは呼ばない方がいいでしょう。

異なるオブジェクトでの配列の作成

文字列の配列や2次元配列など、要素を文字列や配列などのミュータブルなオブジェクトにするときは注意です。

n = 10

# Bad: 各要素をすべて同一オブジェクト(の参照値)にしてしまう。
[[]] * n
[[0] * n] * n
["a"] * n
[rand(n)] * n

# Good: 各要素を異なるオブジェクトにするために、要素毎にブロックを評価してオブジェクトを作成する
Array.new(n){ [] }
Array.new(n){ [0] * n }
Array.new(n){ "a" }
Array.new(n){ rand(n) }

連番の配列を作る方法など

連番を作る方法はたくさんありますが、3つぐらい知っておけばいいかなと思います。

p b = [*1..5]     #=> [1, 2, 3, 4, 5] # メジャーな印象
p a = (1..5).to_a #=> [1, 2, 3, 4, 5] # 上よりちょっと速い。

p x = Array.new(5){ |i| i }     #=> [0, 1, 2, 3, 4]
p y = Array.new(5){ _1 }        #=> [0, 1, 2, 3, 4] # v2.7で導入されたナンパラ記法。
p z = Array.new(5){ |i| i * i } #=> [0, 1, 4, 9, 16]
p w = Array.new(5){ |i| [i, i * i] } #=> [[0, 0], [1, 1], [2, 4], [3, 9], [4, 16]]

配列の作成でブロックパラメータを使う方法があり応用がきき複雑なケースで速いと思うので、知っておいてよさそうです。

require "benchmark"
n = 10**6
m = 10**0
Benchmark.bm(13) do |r|
  x = r.report("n.times.to_a  "){ m.times{ n.times.to_a } }
  y = r.report("Array(0...n)  "){ m.times{ Array(0...n) } }
  x = r.report("(0...).take(n)"){ m.times{ (0...).take(n)} }
  z = r.report("(0...n).to_a  "){ m.times{ (0...n).to_a } }
  w = r.report("[*(0...n)]    "){ m.times{ [*(0...n)] } }
  s = r.report(".new {|i| i } "){ m.times{ Array.new(n){ |i| i } } }
  t = r.report(".new &:itself "){ m.times{ Array.new(n, &:itself) } }
end
#                     user     system      total        real
# n.times.to_a    0.019988   0.003949   0.023937 (  0.024007)
# Array(0...n)    0.024549   0.000107   0.024656 (  0.024749)
# (0...).take(n)  0.016503   0.008205   0.024708 (  0.024709)
# (0...n).to_a    0.017382   0.007119   0.024501 (  0.024504)
# [*(0...n)]      0.025250   0.008429   0.033679 (  0.033683)
# .new {|i| i }   0.046754   0.003618   0.050372 (  0.050375)
# .new &:itself   0.084499   0.000154   0.084653 (  0.084656)

特に上5つは、速度の面で五十歩百歩です。作成する配列の要素数も速さの順位を左右しました。
n.times.to_aは、応用がきかず特化している分か、要素数が多いと(五十歩百歩ですが)1番速かったです。
ArrayメソッドことKernel#Arrayは、使われているところを見ませんが、思ったより速かったです。
(0...).take(n)は、2.6からの機能を使っており、要素数が少ないと(五十歩百歩ですが)1番速かったです。
(0...n).to_aと[*(0...n)]は、*の内部を知っていれば前者の方が少し速いとわかります。前者はRange#to_aを使っているだけですが、後者は*(splat演算子)の内部でRange#to_aで配列にしたあとに分離させて[ ]でまた配列を作っている感じで、前者より後者の方の処理が多いです。
Array.new(n){ |i| i }は、要素を作るたびにブロックを使い遅いですが、複雑なケースでは応用がきき速いです。
Array.new(n, &:itself)は実践的なところで見たことないですが、ググるとたまに見かける謎な記法です。めちゃくちゃ遅かったです。

【罠】紛らわしいArrayメソッド

Arrayクラスだけでなく、Arrayメソッドがあります。Kernel#Arrayです。
Array.new()の書き方をしていて、うっかり.newを書き忘れると全く別の配列になるので注意しましょう。

n = 5
Array.new(n){ 0 } #=> [0, 0, 0, 0, 0]
Array(n){ 0 }     #=> [5]

Kernel#Arrayの存在、デメリットの方が大きい気がします。

逆順、降順の配列の作り方

ある配列を逆順にした配列を作りたいときは、reverseです。
逆順と降順は、違う意味なので注意です。
降順の連番配列の作り方は、昇順の連番配列をreverseで逆順するだけでいいです。

require "benchmark"
n = 10**6
Benchmark.bm(16) do |r|
  x = r.report("to_a.reverse     "){ (0..n).to_a.reverse }
  y = r.report("reverse_each.to_a"){ (0..n).reverse_each.to_a }
  x = r.report("sort_by{ |e| -e }"){ (0..n).to_a.sort_by{ |e| -e } }
end
#                        user     system      total        real
# to_a.reverse       0.024807   0.004139   0.028946 (  0.029020)
# reverse_each.to_a  0.045325   0.004056   0.049381 (  0.049393)
# sort_by{ |e| -e }  0.273388   0.022673   0.296061 (  0.296081)

to_a.reverseは、中間配列も作り2回配列を作っています。
reverse_each.to_aは、最後に1回だけ配列を作っています。
配列の作っている回数だけ見ると、前者の方が遅そうですが、実際は逆です。
Array#reverseの処理は、配列を新しく作るときほど時間はかかりません。5, 6分の1です。
そして、#<Enumerator: 0..1000000:reverse_each>を配列化するのが、とても遅いです。
これは、#<Enumerator: 0..1000000:each>の倍の時間がかかります。
そのため、to_a.reverseの方が、短いし速く降順の配列を作ります。

また、昇順で並んでいるものを降順にしたいときは、reverseで逆順にするだけです。
sort_byで降順ソートしてしまうと、要素の評価、要素の評価値の比較を余計にするので当然遅くなりました。

何度も反転しない

問題の操作として配列や行列を何度も反転しているからといって、実際に何度も反転させてしまうと重たくなります。
reverseを何度もすることは時間のかかる操作で、TLEになる可能性があります。
同一の配列に対して、何度も実際にreverseすることはないでしょう。
向きの状態を変数としてもつ等して、実際に反転させないようにしましょう。
これはRuby特有のことではなく、競プロの問題として当たり前に出題されます。

逆順に回したいとき

逆順の配列を作りたいときはArray#reverseで、
配列の要素を逆順に回したいときはArray#reverse_eachでしょう。

require 'benchmark'
n = 10**6
a = [*0..n]
Benchmark.bm(11) do |r|
  x = r.report("reverse_each"){ a.reverse_each{ |i| i } }
  y = r.report("reverse.each"){ a.reverse.each{ |i| i } }
  z = r.report("reverse     "){ a.reverse }
  w = r.report("each        "){ a.each{ |i| i } }
  # p y.real / x.real
end
#                   user     system      total        real
# reverse_each  0.039804   0.000134   0.039938 (  0.039938)
# reverse.each  0.040246   0.004068   0.044314 (  0.044317)
# reverse       0.001099   0.003485   0.004584 (  0.004585)
# each          0.040013   0.000155   0.040168 (  0.040172)

reverse_eachが、reverse.eachよりちょっぴり1.1倍ほど速そうでした。
reverse.eachは、Array#reverseで中間配列を作る分、遅くなっているようです。

Enumerable#reverse_eachを継承しているRangeのreverse_eachはeachと比べ遅さを感じますが、
Array#reverse_eachはArrayで再定義されていてArray#eachと同等の速さで良さそうです。
同名メソッドでも、どこで定義されているかで性能が別物なので、その点は留意したいですね。

配列の要素数

Array#sizeとArray#lengthはエイリアスですが、Array#countは別物です。
Array#countの方が、引数やブロックをとれるので高機能です。
その分、配列の要素数を求めるために引数なしのcountを使うと少し遅かったです。

require "benchmark"
n = 10**6
a = Array.new(n){ 0 }
Benchmark.bm(5) do |r|
  x = r.report("size "){ n.times{ a.size } }
  y = r.report("count"){ n.times{ a.count } }
  p y.real / x.real
end

#             user     system      total        real
# size    0.046479   0.000000   0.046479 (  0.046477)
# count   0.065314   0.000000   0.065314 (  0.065315)

sizeの方が、countよりも1.4倍前後速かったです。
なお、引数なしのcountについては要素数に応じて時間が増えるという感じではないでしょうが、
引数をとる場合は要素数に応じて時間が増えるはずなので、その点注意です。

ただし、今までのはArrayの話であって、HashのcountメソッドはEnumerableクラスを継承したもので1つ1つ数えるのでとても遅いです。
ArrayはEnumerableと同名メソッドを最適化のために定義し直していることが多い印象です。

範囲外参照のnil

配列の範囲外参照は、nilを返します。
ハッシュのデフォルトの範囲外参照も、nilを返します。
未代入のインスタンス変数・未代入のグローバル変数の参照も、nilを返します。

配列の範囲外参照の返り値を変更したいときは、いくつか方法があります。

a = []

p a[1] || 0
p a[2] ||= 5

p a #=> [nil, nil, 5]

範囲外参照時に、特定の値などを返してほしいとき

配列の範囲外参照は、nilを返します。
ハッシュのデフォルトの範囲外参照も、nilを返します。
未代入のインスタンス変数・未代入のグローバル変数の参照も、nilを返します。
これらのように、Rubyでは、存在しないものを取ろうとるするとnilが返ることが多いです。

範囲外参照時に、特定の値などを返してほしいときは、||を使った短絡評価がよく見られる書き方です。
||は汎用的で短くわかりやすくよく使われています。
fetchと比べて見たところ、||の方が1.3〜1.5倍速かったです。

require 'benchmark'
n = 10**6
Benchmark.bm(5) do |r|
  r.report("||   "){ h = []; n.times{ h[64] || 0  } }
  r.report("fetch"){ h = []; n.times{ h.fetch(64, 0)  } }
end
#             user     system      total        real
# ||      0.047474   0.000000   0.047474 (  0.047646)
# fetch   0.070130   0.000000   0.070130 (  0.070130)

||=と書けば代入もできますし、||の書き方は知っておくと良さそうです。

負の添字

負の添字をとることで、末尾から数えてアクセスできます。

グリッドを探索するときに、行けないところに四方に壁を作ったり配列の範囲外参照に色々条件を設けなければならないでしょうが、Rubyだと添字の-1が末尾を示すので二方向だけに壁を設けるだけで済んだりシンプルに書けたりします。

..........#
..........#
..........#
..........#
..........#
###########

負の添字、色々と便利です。

要素へのアクセス

require "benchmark"
n = 10**6
a = [*0...n]
Benchmark.bm(7) do |r|
  x = r.report("a.first"){ n.times{ a.first } }
  y = r.report("a[0]   "){ n.times{ a[0] } }
  w = r.report("a.last "){ n.times{ a.last } }
  z = r.report("a[-1]  "){ n.times{ a[-1] } }
  p x.real / y.real
  p w.real / z.real
end

a[0]の方が、a.fistより、1.2〜1.3倍速かったです。
[]で複数の要素を配列として取得したいときは、2引数のようにしたり、Rangeを書く手法があります。

a = ['a', 'b', 'c', 'd', 'e', 'f']
p a[2, 3] #=> ["c", "d", "e"]
p a[2..3] #=> ["c", "d"]

累積和の求め方

添字のアクセスがあるとき、遅くなる印象です。
速さを求めるなら、添字によるアクセスは、なるべくない方がいいでしょう。
1次元の配列から累積和の配列を求める手法を紹介します。

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Bad
cumsum = [0] * a.size
(a.size).times{ |i| cumsum[i] = a[i] + cumsum[i - 1] }
p cumsum # [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

# Good
s = 0;
cumsum = a.map{ |e| s += e }
p cumsum # [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

配列を作るときは、mapを使えないか考えてみるといいかもしれません。

複製

a = [1, 2, 3]
b = a         # 参照の値渡し(共有渡し)
c = a.dup     # 複製

配列をそのまま代入することは、オブジェクトの参照値を代入するだけです。
同じ要素の別の配列を作りたいときは、dupやcloneを使って複製を作ってから代入します。
また、短いコードを書くゴルフでは、*(splat演算子)を利用して展開する方法があるようです。これは遅いです。

深い複製

文字列の配列や2次元配列の場合など、コピーの深さが問題になることがあります。

a = [[1, 2], [3, 4]]
b = a
s = a.dup        # 浅いコピー: 複製元と同一要素を参照し、要素まで複製してません。
d = a.map(&:dup) # 深いコピー

競プロ程度なら3次元配列などの深いコピーをしたいケースはマレなので、この程度の深いコピーで十分でしょう。

メソッドの引数

Rubyのメソッドで、配列を引数にとると、参照の値渡し(共有渡し)が行われます。
配列の中身の全要素をメモリの別の場所にコピーするわけではないので、要素数に応じて時間がかかるということはありません。
ただ、(メソッド内で別のオブジェクトを代入されるまでは、)メソッド呼び出し元もメソッド内も同一オブジェクトを参照(共有)しているので、破壊的操作をするとメソッド呼び出し元のレベルでも配列の中身が変わります。

破壊的メソッド

Ruby本体では、!つきメソッドは、(同名の)!なしメソッドに比べて「危険」とされています。
競プロで使う範囲でのメソッドなら、!つきメソッドなら破壊的メソッドと考えていいでしょう。
逆は成り立たなくて、!なしの破壊的メソッドはたくさんあります。

【罠】!つき破壊的メソッド

両者の速度差は、結局はメソッドや条件次第ですが、大して変わらなかったりします。
String#gsubは、!なしの方が速いのが普通な感じがします。

!つき破壊的メソッドを使うのは、以下が主なケースだと思います。

• 変化がなかったときにnilを受け取って、条件に利用したい。
• レシーバを変更したいが、a = a.sortとaを繰り返したくないとき(DRY)。

そのため、破壊的メソッドの返り値からチェーンメソッドに繋げたり代入するのは、違和感があることが多いです。
破壊的メソッドはレシーバが変更されることより、nilが返ることがあったりなかったりするのが危険な感じがします。

a = [3, 1, 2, 3, 2, 3, 1]
p a.uniq  #=> [3, 1, 2]
p a.uniq! #=> [3, 1, 2]

# 破壊的メソッドであるuniq!により、aは重複が削除され要素がユニークな配列になっており、これ以上削除するものはない
p a.uniq  #=> [3, 1, 2]
p a.uniq! #=> nil

Array#uniq!

配列の中の重複を判定したいとき、uniq!を用いることができます。
ただし、これはレシーバの配列の全ての重複要素を削除することが主機能で、レシーバを破壊的に変更する上、重複1つでも見つかれば十分なケースにおいて他の実装より明らかに遅くなります。

【罠】【高速化】使うべき破壊的メソッド、要素の出し入れ

!のつかない破壊的メソッドの代表例に、push(<<), pop, shift, unshift, concat等があります。
今挙げたのは、配列の要素の出し入れや配列どうしの結合に使うメソッドです。
これらは、他の方法と比べると速いので、積極的に使うべき破壊的メソッドです。
特に、配列どうしの結合をするconcatと同等の動作の非破壊的メソッド+を使うと異常に遅いです。

require 'benchmark'
n = 20_000
a = Array.new(n){ rand(n) }
x, y, z, w = nil
Benchmark.bmbm(6) do |r|
  r.report('<<    '){ y = []; a.each{ |e| y << e } }
  r.report('push  '){ x = []; a.each{ |e| x.push(e) } }
  r.report('concat'){ z = []; a.each{ |e| z.concat([e]) } }
  r.report('+     '){ w = []; a.each{ |e| w += [e] } }
end
p [x == y, y == z, z == w, w == z] # [true, true, true, true]

#              user     system      total        real
# <<       0.000781   0.000313   0.001094 (  0.001092)
# push     0.001030   0.000412   0.001442 (  0.001442)
# concat   0.003774   0.000054   0.003828 (  0.003830)
# +        0.215722   0.056435   0.272157 (  0.272248)

計測目的で配列の要素を1つずつ移す作業をしましたが、+の方は100倍以上も遅いです。
単に配列の複製を作るだけだとそこまで遅くならず、+を使うときや複製を作った上で要素を追加すると遅くなります。
そういうわけで、配列の+は「使ってください」という見た目ですが、とても危険です。罠です。
末尾に要素1つ追加するなら<<, 複数追加ならpush, 配列どうしの結合ならconcatを用いましょう。

同様に文字列の+も遅いです。

pop, shift

配列の要素を出し入れしてループ回すとき、配列が空になったらループを終了したいです。
こういうときpopやshiftは、要素があれば要素を取り出して返し、要素のない空配列だとnilを返すので便利です。

a = [0, 1, 2, 3]
while (e = a.pop)
  p e
end

また、whileの条件式の中で、イコール判定ではなく、代入のときは()で囲むスタイルがあります。
実際、()で囲んで評価値を返してあげないと動かないケースがあります。
それは、次のようなケースです。

a = [[1, 2], [3, 4]]
while (x, y = a.pop)
  p [x, y]
end`

【罠】配列内の要素のソート方法

Rubyには配列の中身をソートするメソッドが、sortとsort_byの2つあります。
さらに、破壊的メソッド版のsort!, sort_by!があります。

# 昇順
p [2, 4, 1, 3, 5].sort             #=> [1, 2, 3, 4, 5]

# 降順
p [2, 4, 1, 3, 5].sort.reverse      #=> [5, 4, 3, 2, 1]
p [2, 4, 1, 3, 5].sort_by{ |e| -e } #=> [5, 4, 3, 2, 1]

ブロックで比較条件を指定するソートは、sortよりsort_byがいいです。
sort_byの方が書きやすいだけでなく、高速で使い勝手がいいです。
Rubyリファレンスマニュアル(るりま)にも、高速である旨が書いてあります。

Enumerable#sort_by (Ruby リファレンスマニュアル)

Enumerable#sort と比較して sort_by が優れている点として、比較条件が複雑な場合の速度が挙げられます。

「比較条件が複雑な場合」というのが少しわかりませんが、「比較条件をブロックでとる場合」に読み替えていいです。るりまに実行回数の検証コードもあり、sort_byのブロックの実行回数は要素数(O(N))だけど、sortは比較のたびにブロックを実行するので(O(N logN))、遅くなるようです。要素数が1000だとすると、log2(1000) ≒ 10なので、重たいブロックの実行回数が10倍に増えて桁違いに遅くなってきます。

ブロックをとらない昇順ソートはsortを使い、それ以外の比較条件をブロックに指定したいときはsort_byと考え問題ありません。要素それぞれの比較回数は一緒ですが、sortは比較ごとにブロックを実行し、sort_byは比較の前に各要素を1度評価するためのブロックを走らせ、ブロックの実行回数が異なっているようです。速さ
が2.5倍ぐらい変わってきます。

降順ソートの比較

require "benchmark"
n = 10**5
a = Array.new(n){ rand(n) }
b, c, d, e = a.dup, a.dup, a.dup, a.dup
Benchmark.bm(11) do |r|
  x = r.report("sort    "){ a = a.sort{ |a, b| b <=> a } }
  y = r.report("sort_by "){ b = b.sort_by{ |e| -e }  }
  z = r.report("sort!   "){ c.sort!{ |a, b| b <=> a } }
  w = r.report("sort_by!"){ d.sort_by!{ |e| -e }  }
  s = r.report("sort.reverse"){ e.sort.reverse  }
  p w.real / s.real
end

#                   user     system      total        real
# sort          0.108920   0.000249   0.109169 (  0.109231)
# sort_by       0.041350   0.000000   0.041350 (  0.041353)
# sort!         0.107935   0.000000   0.107935 (  0.107943)
# sort_by!      0.042225   0.000000   0.042225 (  0.042227)
# sort.reverse  0.015906   0.000000   0.015906 (  0.015908)
# 2.654471956109129

非破壊的メソッド、破壊的メソッドに速度差はないと思います。並び替えると順位が入れ替わったりしました。

# 配列の中に配列がある2次元配列のとき
students = [[1, "Sato", 60], [2, "Sato", 100], [3, "Takahashi", 100], [5, "Watabe", 20], [4, "Yamada", 50]]

p students.sort_by!{|(id, name, score)| id }
p students.sort_by!{|(id, name, score)| [name, id] }
p students.sort_by!{|(id, name, score)| score }
p students.sort_by!{|(id, name, score)| -score }

tally

tallyは、Ruby 2.7 で追加されたメソッドです。
返り値はHashです。Crystalでも使えます。

p ["c", "a", "b", "b", "b", "b", "c"].tally #=> {"c"=>2, "a"=>1, "b"=>4}

配列の要素を集計して、Hashで返してくれます。
簡単に書けるので、便利です。
独特なメソッド名ですが、日本で数えるときの「正」のグローバルなものを指すようです。

配列を利用した等号比較

平面座標の点(x, y)と(z, w)が一致しているかどうか調べたいときがあります。
ふつうx == z && y == wと書くと思いますが、[x, y] == [z, w]と書くと見やすそうです。
ただし、配列の作成や比較は相対的にコストがあり、2,3倍は実行時間が変わってしまいます。危険を伴います。

require "benchmark"
n = 10**6
m = 2**9
a = Array.new(n){ rand(m) }
Benchmark.bm do |r|
  r.report("[ ]"){ a.each_slice(4){ |x, y, z, w| p x if [x, y] == [z, w] } }
  r.report("&& "){ a.each_slice(4){ |x, y, z, w| p x if x == z && y == w } }
end

#        user     system      total        real
# [ ]  0.101413   0.000483   0.101896 (  0.101898)
# &&   0.036634   0.000114   0.036748 (  0.036751)

配列どうしの大小比較

Arrayに==, !=, <=>は最初から定義済みですが、<のような不等号はありません。
Rubyはオープンクラスなので既存クラスを拡張でき、Comparableモジュールをインクルードするだけで、配列どうしの大小比較をできるようになります。

class Array
  include Comparable
end

p [1, 2, 3] <= [1, 9, 9] #=> true
p [1, 2, 3] >= [1, 2]    #=> true

仕組み的には、もともとArrayクラスにソートのための<=>メソッドが定義されており、Comparableモジュールをインクルードすることで<=>を利用して==, !=, <, >などのメソッドが定義されます。
そんなに使わないと思いますが、いざのために知っていてもいいかもしれません。

Hash

範囲外参照のデフォルト値の変更

Arrayの範囲外参照の返り値がnilであったように、
Hashの範囲外参照(key未設定)をしたときの返り値もnilです。
ただ、Hashの場合、この返り値を変更する方法のバリエーションが多いです。

まず、Hash特有の機能として、デフォルト値があります。
何も設定しない場合のデフォルト値は、nilです。つまり、デフォルトのデフォルト値は、nilです。
デフォルト値には、オブジェクトとブロックの2種類あります。どちらかのみ機能します。
ブロックの方は複雑なことが出来ますが、その分遅くなる可能性があります。

h = {}        # 何も指定しないと、デフォルト値は`nil`。
h.default = 0 # デフォルト値はあとから変更できる。左の例では、0にした。
Hash.new(0)   # デフォルト値を0で新規作成。
Hash.new{ [] } # キーがなかったときに空配列を返すブロックを設定したHashを作成。
Hash.new{ |hash, key| hash[key] = [] } # 参照したときに代入することも出来る。

ブロックの中身の記法が特殊ですが、別オブジェクトを作成できます。

また、Hashから取り出すときにも、短絡評価やfetchを使って、keyがなかったときの返り値を決めることが出来ます。(Arrayと同様)

範囲外参照したときに、数値などのイミュータブルな値を返す方法

require 'benchmark'
n = 10**6
Benchmark.bm(6) do |r|
  r.report(".new()"){ h = Hash.new(0); n.times{ h[:A] } }   # 初期化時にデフォルト値を設定。1番速い。
  r.report("||    "){ h = {}; n.times{ h[:A] || 0 } }       # ||を使う汎用的な方法。キー&値があっても、値が偽なら右を返す。
  r.report("fetch "){ h = {}; n.times{ h.fetch(:A, 0)  } }  # fetchはブロック渡せたり多機能なせいか、ちょっと遅め。
  r.report(".new{}"){ h = Hash.new{ 0 }; n.times{ h[:A] } } # キーがなければ、ブロックを実行する。
end

#             user     system      total        real
# .new()   0.053120   0.000513   0.053633 (  0.053749)
# ||       0.056578   0.000000   0.056578 (  0.056583)
# fetch    0.067479   0.000000   0.067479 (  0.067486)
# .new{}   0.100452   0.000000   0.100452 (  0.100463)

ちょっとですが時間差がハッキリつきました。速さの順は、感覚とも整合しています。
競プロのコードだと汎用的な||を使う人が少し多そうな気がしますが、Hash特有の初期化時に引数で指定した方が少しよさそうです。
ただ、初期化時のデフォルト値の設定は、数値などには使えますが、配列などは同一オブジェクトになってしまいます。

範囲外参照したときに、特定のオブジェクトを返すだけでなく、値を設定する方法

require 'benchmark'
n = 10**6
Benchmark.bm(5) do |r|
  r.report("||=   "){ h = {};  n.times{ |i| h[i] ||= 0 } }
  r.report(".new{}"){ h = Hash.new{ |h, k| h[k] = 0 }; n.times{ |i| h[i] } }
end

#             user     system      total        real
# ||=     0.184578   0.038666   0.223244 (  0.223343)
# .new{}  0.251309   0.019284   0.270593 (  0.270604)

ブロックはやはり遅いので、自己代入の形で||=を使用すると良さそうです。
複雑なコードだとブロックにせざるを得ないと思いますが、||=を利用すると、シンプルです。

Array#tallyが追加される前のカウント方法

2.7でArray#tallyが追加される前は、Hashのデフォルトの返り値を0にしてカウントする方法が使われていたのではないかと思います。

a = ["c", "a", "b", "b", "b", "b", "c"]
h = Hash.new(0)
a.each{ |e| h[e] += 1 }
p h #=> {"c"=>2, "a"=>1, "b"=>4}

今はArray#tallyで1発ですね。

【高速化】HashやSetのキーを変更する

【高速化】HashのキーをStringからSymbolにする。あるいは、凍結文字列リテラルにする。

Hashのキーは、Stringではなく、Symbolにすると速いです。

普通の文字列は同じ内容でも違うオブジェクトとして生成されます。
しかし、Hashのキーを文字列とするとき、内部では文字列をコピーをしフリーズしたものをキーとします。
そうすることで、Hashは効率的にキーを管理しています。
そのため、フリーズされてない文字列をキーにしようとするときに、コピーやフリーズの作業が発生するため遅くなるようです。

Symbolでなくとも、マジックコメントで# frozen_string_literal: trueと書いておけば、
最初からフリーズした状態で文字列を作るためHashのアクセスはSymbolと同等のようです。

【高速化】Hashのkeyを数値の配列から整数値へ

特定の範囲の2, 3個の整数値のペアにして、それをHashのキーにしたりSetに入れたいときがあります。
るりまに書いてありますが、HashのキーをArrayやHashにするのは向いてません。数値に変換します。
具体的な例で説明するために、n, mが0〜99の整数を取ると仮定します。そういう前提をおきます。

# 配列をキーにするのは遅い
h = {}
h[[n, m]] = "hoge"

# 数値をキーにした方がいい。もしn = 25, m = 3なら、2503がキーになる。
h = {}
h[100 * n + m] = "hoge"
# 逆に、キーから取りだすときは、それぞれk / 100, k % 100のようにする。

こういったときは、数値どうしを文字列の結合のように1つの整数値にするといいです。
これは、配列の作成や比較が、数値の作成や比較のコストを上回っているためです。
特に、配列からHash内部で管理するハッシュ値の計算は重たいようで、要素の数に比例するように増えていきます。

なお、例ではわかりやすく0〜99の整数としましたが、
このぐらいの数であれば2次元配列や1次元配列でも管理できそうです。

また、例では、数値が重ならないように10進数でみて100倍しましたが、2進数でみてbit shiftで重ならないように作っても良さそうです。

傾きをHashのキーにしたいときは、Rational

(x, y)を格子点(整数値)として、y / xのような傾きをHashのキーにしたいときがあります。
このようなときは、浮動小数点数にすると誤差が生じてしまうので、Rational(有理数・分数)を使います。
2数を既約して配列をキーにする方法もあるとは思いますが、配列をキーにするのは遅いですし、Rationalが自然なはずです。

キーがあるかの確認

キーがあるかの確認方法は、メソッドだとhas_key?(key?)があります。
他に、キーがないときの[]によるアクセスがnilであることを利用しても確かめられます。こちらの方が、1.1〜1.2倍ほどちょっぴり速いです。
※ 厳密には、返り値の種類が違ったり、ハッシュの値がnilであるときの区別がつかないのような違いはあるので、注意してください。

require "benchmark"
n = 10**6
h = {:key => :value}
Benchmark.bm(10) do |r|
  x = r.report("[]      "){ n.times{ h[:key]  } }
  y = r.report("has_key?"){ n.times{ h.has_key?(:key) } }
  z = r.report("[]      "){ n.times{ h[:none] } }
  w = r.report("has_key?"){ n.times{ h.has_key?(:none) } }
  # p [y.real / x.real, w.real / z.real]
end

#                  user     system      total        real
# []           0.052646   0.000000   0.052646 (  0.052699)
# has_key?     0.066828   0.000000   0.066828 (  0.066829)
# []           0.058835   0.000000   0.058835 (  0.058836)
# has_key?     0.065312   0.000000   0.065312 (  0.065313)

文字列

競プロの入出力で使われる文字は、ASCIIコードが基本です。
主な文字は0-9A-Za-z, それに半角スペース、改行です。
それ以外に、.#+-*/[]!?などの記号があります。
そのため、ASCIIコードの文字を前提に話を進めます。

Stringにはeachがない

Array#eachもあるし、Hash#eachもありますが、String#eachはないです。
あるのはeach_char(chars)、each_byte(bytes)、each_line(lines)等です。
これは、文字列に対して回したいものが文字か行かバイトか明確でないため、昔v1.9でString#eachは廃止されました。
まぁ、配列や文字列の添字の取り方からすると、文字で回すのが1番自然そうな感じがしますけど。

【高速化】String#chars, String#bytes

文字列の文字を1文字ずつ回して処理をしたいとき、いくつかの方法があります。
1番初歩的な方法としてtimesで数値を回して添字でアクセスする方法は、時間がかかります。
競プロテクですが、bytes(each_byte)で文字列を数値の配列にして回すと速いです。
あるいは、charsで文字の配列にしても、そこそこ効果があります。
bytesを使うと可読性は落ち業務等では使えないでしょうが、ACかTLEかに影響を及ぼすことがあるぐらいの差が容易にでます。

s = "123abcABC"
c = "123abcABC".chars #=> ["1", "2", "3", "a", "b", "c", "A", "B", "C"]
b = "123abcABC".bytes #=> [49, 50, 51, 97, 98, 99, 65, 66, 67]

require 'benchmark'
n = 10**5
stris = "a" * n     # "aaa......a"
chars = stris.chars # ["a", "a", "a",......, "a"]
bytes = stris.bytes # [97, 97, 97,......, 97]
Benchmark.bm(6) do |r|
  r.report("string"){ n.times{ |i| stris[i] } }
  r.report("chars "){ n.times{ |i| chars[i] } }
  r.report("bytes "){ n.times{ |i| bytes[i] } }
end
#             user     system      total        real
# string   0.015229   0.000000   0.015229 (  0.015228)
# chars    0.004546   0.000000   0.004546 (  0.004546)
# bytes    0.004633   0.000000   0.004633 (  0.004634)

文字列を扱うのは色々と遅いですが、添字でアクセスするのが配列と比べて軽く3倍も時間がかかります。
正確にいえば、空ループでの時間を差し引いて純粋に考えれば、3倍より多いはずです。
添字での参照が多いほど、時間差は開き、文字列を扱う時間は何倍も膨れ上がっていきます。
そのため、文字列は、文字の配列や数値の配列にした方がいいです。

文字の配列を作成するのは、コストがかかる。

文字列への添字の参照は遅かったですが、文字の配列と数値の配列への添字での参照は、時間差はあまりなさそうでした。
ただし、「文字列から文字の配列を作る」のと「文字列から数値の配列を作る」のとでは、コストの桁が違います。
以下が、比較のコードと結果です。

require 'benchmark'
n = 10**5
stris = "a" * n # "aaa......a"
Benchmark.bm(5) do |r|
  r.report("chars"){ stris.chars }
  r.report("bytes"){ stris.bytes }
end
#            user     system      total        real
# chars   0.016304   0.000114   0.016418 (  0.016494)
# bytes   0.001102   0.000245   0.001347 (  0.001347)

1文字の配列を作るとき、全ての文字オブジェクトを頑張って作って遅くなるのでしょう。
「文字列から文字の配列を作る」の初期コストは高いものの、文字列を[]の添字で参照するコストが高く積み重なるので、結局はトータルで「そのまま文字列を扱う」より、「文字列を文字の配列に変換してから扱う」方が断然速くなります。
また、初期の作成コストが低い「bytesによる数値の配列を扱う方法」は、より速いです。

文字を扱うコストと数値を扱うコスト

数値どうしの比較、文字どうしの比較だと、前者の方が少し速いです。
また、リテラルの速い順で、数値リテラル > 文字リテラル > 文字列リテラルになっていました。
ただし、# frozen_string_literal: trueがセットされている場合には、数値でも文字列でも文字でもリテラルの時間差はなさそうでした。

インデックスを減らす

また、インデックスによる参照を極力抑えた方がいいです。
Stringにはeachがなく、最初はtimesでインデックスをとったりして回してしまうかもしれません。
しかし、bytes(each_byte), chars(each_char)があり、そのブロックでそのまま回せるので、そうした方がいいです。

require "benchmark"
n = 10**4
s = "0123456789abcdefghijklmnopqrstvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" * n
Benchmark.bm(10) do |r|
  r.report("chars.each"){ s.chars.each{ |c| c } }
  r.report("size.times"){ s.size.times{ |i| s[i] } }
  r.report("chars     "){ s.chars{ |c| c } }
  r.report("bytes.each"){ s.bytes.each{ |b| b } }
  r.report("bytes     "){ s.bytes{ |b| b } }
end

#                  user     system      total        real
# chars.each   0.102959   0.007834   0.110793 (  0.110903)
# size.times   0.089584   0.004354   0.093938 (  0.093948)
# chars        0.057789   0.000000   0.057789 (  0.057797)
# bytes.each   0.028419   0.003753   0.032172 (  0.032179)
# bytes        0.024417   0.000063   0.024480 (  0.024482)

また、charsやbytesのブロックで直接回さず、bytes.eachで回してしまうと、中間配列の生成のため少し遅くなるようです。
なお、charsやbytesにブロックを渡すのは公式的には非推奨で、ブロックを渡すときはeach_char, each_byteと明示的なメソッドを使った方がいいのかもしれません。。
同様に、Hash#keysやHash#valuesではブロックに渡して回すことができて欲しいですが、できません。そのため、h.each_keyやh.each_valueを使うか、h.keys.eachとh.values.eachと繋げるかです。h.each_keyの方が速いという記事をよく見かけますが、計測した感じ誤差レベルか、むしろh.keys.eachの方が気持ち速そうでした。まぁ、別の方法で計測したら結果が変わりそうですし、h.each_keyが無難ですかね。

chrで文字コードを知る

1文字の文字コードを知りたいときに、chrを使います。
反対に整数値から文字にするメソッドは、Integer#ordです。

p 'a'.ord # 97
p 97.chr # "a"

# 「'a'を0, 'b'を1, ……, 'z'を25」と置換する方法。
# 文字を数値に対応させると、配列の添字できて便利。
# cは、任意の英小文字の1文字です。'a'.ordは97です。また、1文字リテラルを使い、？a.ordと書けます。
c = 'e'
p c.ord - 'a'.ord #=> 4

【高速化】String#countは高速

ASCIIコードのように小さく限られた文字のカウントは、String#countを使うと高速になるようです。
こちらのくさころ氏のツイートで知りました。

require 'benchmark'
n = 10**5
str = "hogefuga" * n

h0, h1, h2, h3, h4 = nil
Benchmark.bmbm(10) do |r|
  r.report('chars      '){ h0 = Hash.new(0); str.chars{ |c| h0[c] += 1 } }
  r.report('chars.tally'){ h1 = str.chars.tally }
  r.report('bytes      '){ h2 = Hash.new(0); str.bytes{ |b| h2[b] += 1 }; h2.transform_keys!(&:chr) }
  r.report('bytes.tally'){ h3 = str.bytes.tally.transform_keys(&:chr) }
  r.report('count      '){ h4 = {}; ("a".."z").each{ |c| h4[c] = str.count(c) }; h4.reject!{ |_c, cnt| cnt == 0 } }
end

p [h0 == h1, h1 == h2, h2 == h3, h3 == h4] #=> # [true, true, true, true]

#                  user     system      total        real
# chars        0.188682   0.001504   0.190186 (  0.190408)
# chars.tally  0.189960   0.007955   0.197915 (  0.197934)
# bytes        0.079417   0.000036   0.079453 (  0.079457)
# bytes.tally  0.050439   0.004119   0.054558 (  0.054564)
# count        0.003459   0.000000   0.003459 (  0.003461)

文字列を1つずつ数えたり、tallyを使ったりではなく、同じ文字をまとめてString#countで数えた方が速いです。
条件にもよりますが、10〜100倍ぐらいは時間に差がでる感じです。

なお、日本語だとstring.chars.tallyが速そうでした。

文字・文字列の変換・置換

文字を数字にするのにも便利tr

trは、Unixコマンド由来のメソッドです。translate、transliterateの略です。
trは、1文字を何か別の1文字(または0文字)に置換・交換・削除するときに使え、多彩です。
引数の指定方法は、単純ですが、少し独特です。

# `tr`で文字を数字にする。文字を数値に変換する際に便利です。
p "AAATACCGCG".tr("ATGC", "0123") #=> "0001033232"

# 文字の交換に便利。
p "AAATACCGCG".tr("ATGC", "TACG") #=> "TTTATGGCGC"

# `tr`で、2進数表記に置換、改行(`\n`)は削除。ここから`to_i(2)`で数値にしたりする。
p ".#..###\n".tr("#.\n", "10") #=> "01001110"

# 連続指定もできる。
p "AB-ABC123".tr("A-E", "1-5") #=> "12-123123"

# ROT13も簡単。ROT13文字というのは、13文字ズラす古典的な暗号。
p "Rail".tr("A-Za-z", "N-ZA-Mn-za-m") #=> Envy
p "Envy".tr("A-Za-z", "N-ZA-Mn-za-m") #=> Rail

文字列の置換

文字列の置換は、gsub(gsub!)、tr、sub(sub!)の順によく使っています。

破壊的メソッドのgsub!は破壊しなかったときにnilを返すので、法則に従って置換していくときに便利です。
例えば、括弧のみの文字列があるときに、括弧対応する部分だけを削除して、対応しない部分だけを残したいときは、次のような方法で書けます。

s = "))(())("
1 while s.gsub!("()", "")
p s #=> "))("

後置whileを書いており、置換できる限り置換して、置換できなくなったときにwhileを抜けるように書いています。

split/scan

splitは正規表現も使えます。splitの引数は、分割したい切れ目を指定するところ。
反対に、scanの引数は取り出したい要素を指定します。表裏一体です。
scanの方が正規表現を書きやすいこともあると思うので、両方存在は認識しておくと良さそうです。
また、ブロックをとって分離した要素をそのまま回せます。

グリッド問題、二重ループ

グリッド問題や三重ループあたりの問題は、Rubyが苦手なのか、遅くなってしまう書き方をしやすいのか、基準が厳しいのか、ACしにくい印象です。このあたりのことは、他の方のブログでも言及があります。

グリッド系の問題は、数値の配列で扱う

文字列のところで言及しましたが、String#bytesメソッドで数値の配列にして回すとかなり高速なることが多いです。
timesメソッドでindexを回して文字列から[]の添字で取得するのが1番遅いです。

脱出処理を範囲に持たせる

0 ≦ i < j < nのような大小関係があるという問題で、全てのi, jの組み合わせについて、ループを回したいときがあります。

# Bad
n.times do |j|
  j.times do |i|
    break unless i < j
    # 主な処理
  end
end

# Good
(0 ... n).each do |j|
  (0 ... j).each do |i|
    # 主な処理
  end
end

見た目は好みもあると思いますが、速さの観点では後者の方がベターです。
二重ループの中だと処理回数数が多くなりがちで、Badな方は何度も条件判定が行われてしまいます。
ループの範囲の識別は、eachに任せてあげるようにしましょう。
n = 5_000で、0.06秒ほどの差がありました。
時間制限の際どいところでは、こういう小さな積み重ねが効いてきます。
また、やはりwhileが強くて、whileを使うともっと速くなりました。

なお、上記の処理は、Array#combinationを使うと次のように書けます。

(0 ... n).to_a.combination(2) do |i, j|
  # 主な処理
end

三重ループ・四重ループと増えるときは可読性等のためにcombination等の活用を考えると良さそうです。

改めて、計測してみた結果が以下です。

require 'benchmark'
n = 5_000
a, b, c, d = [0] * 5
Benchmark.bm(12) do |r|
  x = r.report("times with if") do
    n.times do |j|
      j.times do |i|
        break unless i < j
        # a+=1 # 主な処理
      end
    end
  end
  y = r.report("Range#each") do
    (0 ... n).each do |j|
      (0 ... j).each do |i|
        # b +=1 # 主な処理
      end
    end
  end
  y = r.report("while") do
    j = 0
    while j < n
      i = 0
      while i < j
        # c+=1 # 主な処理
        i += 1
      end
      j += 1
    end
  end
  y = r.report("combination") do
    (0 ... n).to_a.combination(2) do |i, j|
      # d += 1
    end
  end
end
p [a, b, c, d]
#                    user     system      total        real
# times with if  0.386122   0.000128   0.386250 (  0.386259)
# Range#each     0.371400   0.000000   0.371400 (  0.371415)
# while          0.174395   0.000000   0.174395 (  0.174396)
# combination    0.792681   0.000000   0.792681 (  0.792732)

ループの外側に出来るだけもっていき、添字を減らす

繰り返し行う処理はメソッドにしようというように、
ループの中で繰り返しアクセスする添字や変数は減らした方がいいです。

雰囲気を掴んでもらうためのもので細かい説明はしませんが、ARC104のB問題「DNA Sequence」のコードで、制限時間2秒を超えるTLEコードと0.8秒以上縮んでACとなるコードのループ部分を見せます。

n = 3
m = [[1, 0, 0, 0], [1, 1, 0, 0], [2, 1, 0, 0], [0, 0, 0, 0]] # 累積和の配列で、最後の配列が番兵。

# Bad: TLE
ans = 0
(0...n).each do |j|
  (0...j).each do |i|
    ans += 1 if (m[j][0] - m[i - 1][0] == m[j][1] - m[i - 1][1]) && (m[j][2] - m[i - 1][2] == m[j][3] - m[i - 1][3])
  end
end
puts ans

# Good: AC
ans = 0
(0...n).each do |j|
  ea, et, eg, ec = m[j]
  (0...j).each do |i|
    sa, st, sg, sc = m[i - 1]
    ans += 1 if (ea - sa == et - st) && (eg - sg == ec - sc)
  end
end
puts ans

問題の要素数の上限が5,000で、上限の5,000としたときに、外側のループが5,000回実行され、内側のループ数がおよそ1,250,000回(= 5000 * 5000 / 2)となります。これは想定解法の時間計算量なので、通って欲しいところですが、無駄を省いていかないとRubyではTLEでした。
2秒超えのBadなコードは、処理が全て内側にあり、m[j]やm[i - 1]のアクセスやi - 1という計算が繰り返されています。
大した処理じゃくても、ループで実行される回数が多いので、時間に多大な影響を及ぼします。
そこで、m[j][0], m[j][1], m[j][2], m[j][3]の値は外側のループで決まることなので、内側から外側の部分で代入を確定させてアクセス回数が減らしてあげます。また、m[j]から多重代入の形で変数を分離すると、添字が1回で済みます。

なお、上記のコードはwhileで書き換えると、また時間が短縮しました。

数学

場合の数

["A", "B", "C"]が、A, B, Cという区別できる箱があり、引数がボールの数です。

p ["A", "B", "C"].repeated_permutation(2).to_a
# 箱に入れるボールを何個入れてもよくボールを区別するとき = 箱の重複ありで箱2つ並べる順列の数
# 3**2 = 9通り
#=> [["A", "A"], ["A", "B"], ["A", "C"], ["B", "A"], ["B", "B"], ["B", "C"], ["C", "A"], ["C", "B"], ["C", "C"]]

p ["A", "B", "C"].permutation(2).to_a
# 箱に入れるボールは1個か0個のときでボールを区別する = 箱を2つ並べる順列の数
# 3P2 = 6通り
#=> [["A", "B"], ["A", "C"], ["B", "A"], ["B", "C"], ["C", "A"], ["C", "B"]]

p ["A", "B", "C"].repeated_combination(2).to_a
# 箱に入れるボールを何個入れてもよくボールを区別しないとき = 箱の重複ありで箱を2つ選ぶ
# 3H2 = 4C2 = 6通り
#=> [["A", "A"], ["A", "B"], ["A", "C"], ["B", "B"], ["B", "C"], ["C", "C"]]

p ["A", "B", "C"].combination(2).to_a
# 箱に入れるボールは1個か0個のときでボールを区別しない = ボール1個を入れる箱(or 入れない箱)を選ぶ組合せ = 重複なしで箱を2つ選ぶ
# 3C2 = 3通り
#=> [["A", "B"], ["A", "C"], ["B", "C"]]

permutationを並び替えて一致するものは、combinationにおいて重複して数えます。

そのため、場合の数は、以下のような大小関係があります。
repeated_permutation >= repeated_combination
permutation >= combination

また、repeatedするものは重複(繰り返し)を認めているので、repeatedしないものより多いはず。

実践的には、to_aとせずにそのままブロックに渡して回します。

["A", "B", "C"].combination(2) do |cmb|
  p cmb
end

全探索 / bit全探索

n個の各要素について「する」「しない」のような2通りをそれぞれ考えたとき、場合の数は2のn乗通りになります。
この2のn乗通りを全て試す方法として、bit全探索と呼ばれる手法があります。

1つコードの概略を書くと、このような形で使うことが多いです。

n = 8

# 全2のn通りをループさせる。
(1 << n).times do |bits|

  # それぞれのケースの中で、各要素を使うか使わないか取り出す。
  n.times do |i|
    if 1 == (bits >> j & 1)

    end
  end
end

要素数に応じてループ数がすぐ膨れ上がるので、bit全探索を使う問題は要素数が小さいです。
問題の要素数の上限が8とか小さければ、bit全探索の問題なのでは疑ったりします。

【高速化】2のn乗の比較

n個の各要素について「する」「しない」のような2通りをそれぞれ考えたとき、場合の数は2のn乗通りになります。
まず、全通りの2のn乗の求め方です。
Rubyでは、2のn乗は、2**n、2.pow(n), 1 << n, と書きます。

n = 10
p [2**n, 2.pow(n), 1 << n] #=> [1024, 1024, 1024]

どの方法が速いか検証してみます。

require "benchmark"
n = 10**4
Benchmark.bm(8) do |r|
  r.report("1 << i  ") { n.times{ |i| 1 << i   } }
  r.report("2.pow(i)") { n.times{ |i| 2.pow(i) } }
  r.report("2 ** i  ") { n.times{ |i| 2 ** i   } }
end

#               user     system      total        real
# 1 << i     0.006290   0.000000   0.006290 (  0.006316)
# 2.pow(i)   0.059857   0.000000   0.059857 (  0.059934)
# 2 ** i     0.060374   0.000000   0.060374 (  0.060379)

ビットのシフト演算、桁違いに速いですね。ビット演算は特化している分、速いようです。
1つ注意したいのは、**は+・*・%よりも優先順位が高いですが、
<<は+・-よりも優先順位が低いので、書き換えるなら気をつけたいです。

bitの取り方

bit全探索は、大きく2のn乗通りをループさせる中で、1つ1つの要素について「する」か「しない」かのような2択を取り出して検証して使うことが多いです。

Rubyでは他言語と同様に、数値iの2進数表記の下からj桁目(0始まり)は、((i >> j) & 1)という書き方だけでなく、i[j]とも書けます。
競プロで扱う範囲の数値であれば、i[j]の方が1.1〜1.3倍速かったです。1 << 64ぐらいの数値帯になってくると、急に逆転してました。

require "benchmark"
n = 10**6
m = 1 << 46
a = Array.new(n){ [a = rand(m), rand(a)] }
Benchmark.bm(10) do |r|
  x = r.report("i[j]      "){ a.each{ |(i, j)| i[j] } }
  y = r.report("i >> j & 1"){ a.each{ |(i, j)| ((i >> j) & 1) } }
  p y.real / x.real
end
#                  user     system      total        real
# i[j]         0.067578   0.000000   0.067578 (  0.067582)
# i >> j & 1   0.084774   0.000067   0.084841 (  0.084849)

bit全探索の実践

bit全探索に数値を使う方法以外にも、Array#repeated_permutationを用いる方法があります。
大きく2のn乗通りをループさせる中で、内側で1つ1つの要素をループさせて「する」か「しない」かを取り出して検証するケースが多いです。

require "benchmark"
n = 17
Benchmark.bm(20) do |r|
  x = r.report("1 << n") do
    (1 << n).times{ |bits| n.times{ |i| bits[i] } }
  end
  y = r.report("repeated_permutation") do
    [0, 1].repeated_permutation(n){ |bits| n.times{ |i| bits[i] } }
  end
  p y.real / x.real
end
#                            user     system      total        real
# 1 << n                 0.112471   0.001103   0.113574 (  0.113755)
# repeated_permutation   0.120982   0.000251   0.121233 (  0.121240)

配列を使っている後者の方がきっと遅いと予想しましたが、大きな差はなかったです。
数値が大きいときには1.1倍未満になったり、ほとんど時間が変わりませんでした。
お好みの方で好きな方を書いたらいいと思います。
なお、内外の両方のtimesループをwhileに変更すると、全体として1.7倍ぐらい速くなる感じでした。

2通りではなく、3通り、4通りのケース

bit全探索は、N個の要素をそれぞれ使うかどうかの2択みたいな状況で全2**N通りを1つずつ調べる手法です。
しかし、例えば、N個の要素について「Aに使う、Bに使う、Cに使う、使わない」のような4択の状況で4**N通りを全探索したいと思ったときには使えません。
このようなときは、repeated_permutationがシンプルに書きやすいと思います。

["A", "B", "C", nil].repeated_permutation(n) do |bit|
  # 4**n通りループする
end

二分探索

アルゴリズムレベルの話ですが、二分探索を知らないと解けないケースがあります。
詳しい話はしないので、二分探索を知らない方は別途調べて欲しい。
Rubyでは、二分探索はbsearch, bsearch_indexを用いて書けます。
ソートできるなどの条件が必要だったりしますが、線形探索findよりも速いです。

Range#bsearchによる浮動小数点数の探索

Rangeのどちらか片方が、浮動小数点数であれば、浮動小数点数の探索になるようです。

i = 0
max = Float::MAX
min = Float::MIN
ans = (min .. max).bsearch{ |f| i += 1; f > 0.123 }
p [ans, i] #=> [0.12300000000000001, 63]

実験してみるとわかるのですが、大半のケースでブロックは63回実行されます。
Rubyの内部では計算回数を減らすために64bit整数に1度変換して計算しているため、63回という数値になるようです。
また、るりまによればRubyのFloatはC言語のdoubleで実装され、競技プログラミング上、不利が起こる精度ではないはずで、安心して使って問題ないと思います。

連続性があって解が存在すれば、解を1つ見つけてくれるので、便利でしょう。

p (-10e6 .. 10e6).bsearch{ |x| x ** 2 - x - 30 >= 0 } #=> 6

素数、約数

Rubyでは、素数判定、素因数分解、素数列挙が簡単にできます。

# primeライブラリのロード
require "prime"

#素数判定
p 1.prime? #=> false
p 2.prime? #=> true
p 3.prime? #=> true
p 4.prime? #=> false
p (-2).prime? #=> false
p (10**9+7).prime? #=> true
Prime.instance.prime?(2)  #=> true # なぜか遅い
Prime.prime?(2)           #=> true # なぜか遅い

# 素因数分解。
# 48 = 2 ** 4 + 3 ** 1
p 48.prime_division        #=> [[2, 4], [3, 1]]
p Prime.prime_division(48) #=> [[2, 4], [3, 1]]

# 素数列挙
p Prime.each(12).to_a #=> [2, 3, 5, 7, 11]
p Prime.take(5)       #=> [2, 3, 5, 7, 11]

Rubyでは、primeライブラリをロードするだけで、Integerクラスにprime?などの便利なメソッドが使えるようになります。
primeライブラリをロードしないと動かないので注意しましょう。
また、Prime.eachは素数が無限に続くので、引数に上限を指定するなどが必要です。

【高速化】素数判定

require "benchmark"
require "prime"

s = 10**10
n = 10**2
Benchmark.bm(13) do |r|
  x = r.report("Integer#prime?"){ (s...s+n).each{ |i| i.prime? } }
  y = r.report("Prime.prime?  "){ (s...s+n).each{ |i| Prime.prime?(i) } }
  z = r.report("Prime#prime?  "){ (s...s+n).each{ |i| Prime.instance.prime?(i) } }
  p y.real / x.real
end

#                     user     system      total        real
# Integer#prime?  0.004364   0.000970   0.005334 (  0.005331)
# Prime.prime?    0.042238   0.000501   0.042739 (  0.042837)
# Prime#prime?    0.040686   0.001122   0.041808 (  0.041809)

1番シンプルなIntegerクラスを拡張したprime?が、他よりも軽く6〜7倍速かったです。
あと、2.7のprime?は必ずしも速いアルゴリズムを採用してないので、自分で再実装した方が速かったりします。
なお、最新版のprimeライブラリはミラーラビン素数判定法を採用し速くなっているとのことです。

Mathモジュール

三角関数、対数、平方根、hypot(斜辺の長さ)などを扱いたいとき、このモジュールを使います。
頭の片隅にとめておきたいです。

p Math::PI
p Math.sin(Math::PI)
p Math.cos(Math::PI)

なお、インクルードすることでモジュール名は省略できます。
モジュール名を省略して、遅くなるということもなかったです。

include Math
p PI
p sin(PI)
p cos(PI)

平方根ことsqrt

Mathモジュールは浮動小数点数演算をサポートするモジュールのようで、基本的な返り値がFloatクラスの数値みたいです。

p Math.sqrt(25) #=> 5.0

引数が整数で返り値の端数がでない場合でも、浮動小数点数になるので注意しましょう。

なお、Integer.sqrt(number)というクラスメソッドが存在し、こちらは巨大な整数にも対応し、必ず整数値を返します。
自分は、まだ使ったことないです。

斜辺の長さ・2点の距離を求めるhypot

hypotとは、直角三角形の斜辺(hypotenuse)の長さを計算するメソッド。点と点の距離を求めるときに便利です。
C++やPythonにもあり、C++17以降のhypotは3引数にも対応しています。
C++の場合、数値に型があり、オーバーフロー等の回避のために遅いことが知られています。
では、オーバーフローしないRubyはどうなのかと思い、計測しました。

require "benchmark"
n = 10**6
m = 10**9
a = Array.new(n){ rand(m) }
include Math
Benchmark.bm(18) do |r|
  r.report("sqrt(x * x + y * y)") { a.each_slice(2){ |x, y| sqrt(x * x + y * y) } }
  r.report("hypot(x, y)        ") { a.each_slice(2){ |x, y| hypot(x, y) } }
  r.report("sqrt(x**2 + y**2)  ") { a.each_slice(2){ |x, y| sqrt(x**2 + y**2) } }
end

#                          user     system      total        real
# sqrt(x * x + y * y)  0.068594   0.000000   0.068594 (  0.068594)
# hypot(x, y)          0.074236   0.000041   0.074277 (  0.074280)
# sqrt(x**2 + y**2)    0.104252   0.000000   0.104252 (  0.104255)

hypotは、2番手なものの、十分速かったです。
それより、x * xに比べたときのx**2の遅さが目立ちますね。
**はより大きな指数に対応するため、2乗程度にとっては余計な動作があるのかもしれません。
Ruby 3.0では、x**2の速さに改善が入って、差が縮まっているらしいです。

実践的には2点(x, y)と(w, z)の距離は、hypot(w - x, z - y)と算出した方がいい気がします。
sqrtは、sqrt((w - x) * (w - x) + (z - y) * (z - y))のように複雑になってしまい、タイム差が縮みます。

2乗の比較

2の累乗ではなく、2乗の比較です。

require "benchmark"
n = 10**6
Benchmark.bm(8) do |r|
  r.report("i * i   ") { n.times{ |i| i * i } }
  r.report("i**2    ") { n.times{ |i| i**2 } }
  r.report("i.pow(2)") { n.times{ |i| i.pow(2) } }
end
#               user     system      total        real
# i * i      0.042185   0.000000   0.042185 (  0.042249)
# i**2       0.077069   0.000000   0.077069 (  0.077076)
# i.pow(2)   0.077866   0.000000   0.077866 (  0.077867)

i * iとi**2の差が、想像以上にありました。
なお、Ruby 3.0では、i**2の速さが改善され差が縮まっているとのことでした。

数値と文字列

Rubyでは、数値を2進数や16進数などの文字列へ簡単に変換できます。
引数なしのto_sは数値を10進数の文字列にしますが、引数をとることでN進数の文字列に簡単に変換できます。

p 2.to_s(2) #=> "10"
p 3.to_s(2) #=> "11"
p 65535.to_s     #=> "65535"
p 65535.to_s(2)  #=> "1111111111111111"
p 65535.to_s(16) #=> "ffff"

逆も同様で、引数をとることでN進数の文字列を数値に変換できます。

p "10".to_i    #=> 10
p "10".to_i(2) #=>  2
p "11".to_i(2) #=>  3
p "ffff".to_i(16) #=> 65535

popcount

2進数で表現したときの1の数(ビットの立っている数)をpopulation count、略してpopcountというらしいです。
他言語にはそういう関数がありますが、Rubyにはないので、次のような方法をとります。

p 11.to_s(2)            #=> "1011"

# 11は2進数で表したとき"1011"なので、popcountは3になる。
p 11.to_s(2).count("1") #=> 3 # to_s & countを利用した実装が1番速い
p 11.digits(2).sum      #=> 3
p 11.digits(2).count(1) #=> 3

popcountは、to_s(2).count('1')が常に1番速そうでした。
文字列を扱うのは遅いイメージがあって文字列を避けがちですが、これはto_sもcountも速いので速いようです。

require "benchmark"
s = 10**6
n = 10**6
Benchmark.bm(17) do |r|
  r.report("digits(2).sum     "){ (s..s+n).each{ |i| i.digits(2).sum      } }
  r.report("digits(2).count(1)"){ (s..s+n).each{ |i| i.digits(2).count(1) } }
  r.report("to_s(2).count('1')"){ (s..s+n).each{ |i| i.to_s(2).count("1") } }
end

#                         user     system      total        real
# digits(2).sum       0.608299   0.000000   0.608299 (  0.608408)
# digits(2).count(1)  0.738929   0.000000   0.738929 (  0.738940)
# to_s(2).count('1')  0.425530   0.000000   0.425530 (  0.425563)

なお、普通扱わないような非常に大きい数値のケースにdigitsは爆発的に時間が増えることが報告されています。

Integer#bit_length

正の数であるときに限れば、
2進数で表現するために必要なビット数であり、
n.bit_lengthは、0.to_s(2).lengthと等しいです。
ただし、0.bit_lengthは0を返しますが、0.to_s(2).lengthは1を返します。
また、負数のときにn.to_s(2).lengthは、マイナス記号も長さに含んでしまいます。
bit_lengthを使うのが2倍ぐらいは速かったですし、使えるときはbit_lengthを使いたいですね。

使い所が限られたメソッドだと思うのですが、
セグメントツリーのような完全二分木の高さ、bit単位でループ回すときの回数などに使えるでしょう。

Set、Array、Hashを状況に応じて使い分ける。

要素を追加していき最後に重複を削除すれば十分で、重複が多いケースでは、
Setを使うより、Arrayを使って最後にuniq!で削除すると速そうです。
また、Setを使う場面だろうと思っても、Hashが速かったりします。

Rubyライブラリ

競プロで使えそうな標準添付ライブラリ

標準添付ライブラリは、requireでロードして使えるようになるライブラリと思っていいです。

require "prime"
require "bigdecimal"
require 'openssl'
require "set"
require "matrix"
require "tsort"

primeは使いますが、それ以外はあまり使っていないので紹介のみです。

BigDecimal, OpenSSL::BNという数値クラスがあります。
それぞれ、精度が必要な場面や、modの逆元や素数判定の場面で使えるかもしれません。
たまに使っている方を見かけます。

SetやMatrixといったデータ構造もあります。
ただ、SetよりHashが速いと思うので、Hashを使いこなせていれば不要に感じています。
自分が使いこなせてない可能性もありますが、SetやMatrixは見た記憶が薄いです。

補助的な標準添付ライブラリ

require "benchmark"
require "minitest"
require "minitest/autorun"

外部ライブラリに頼ってないものとして、標準添付ライブラリを紹介します。

Benchmarkは、実行速度を比較するのに使えるライブラリです。
Minitestは、名前の通りテストのためのもので、ライブラリ管理に使えます。
実務では、RSpecが使われることが多いのではと思います。

外部ライブラリ numo-narray

AtCoderの言語アップデートでRuby 2.3 -> 2.7に変更になった段階で、numo-narrayという外部ライブラリが含められ、AtCoderではrequireでロードすることで使えるようになりました。Pythonの有名ライブラリであるnumpyに相当するものです。行列演算などの数的処理をするライブラリだと思いますが、まだ自分は使いどころがわかってないです。1回使おうと思ったのですが、numpyのfmin/fmaxに相当するメソッドがなさそうで断念しました。競プロ人口の多いPythonだとnumpyを使いこなす人を見ますが、numo-narrayは使う方がちょっといるぐらいだと思います。

require 'numo/narray'
include Numo

その他基本的なこと

定数、グローバル変数、インスタンス変数

大文字始まりは、定数です。
いわゆる一般的な定数と異なり、Rubyの定数は(警告こそでるものの)再代入できることで有名です。
トップレベルで定義した定数は、トップレベルのメソッド内でそのまま使えます。
メソッド定義で仮引数を書いて、呼び出しでも引数を書く煩わしさから解法されます。

$始まりは、グローバル変数です。
自分は使いませんが、どこでも使えるので便利といえば便利でしょう。
業務プログラミングではグローバル変数は名前衝突などがあり避けるものでしょうが、
競技プログラミングは個人が使うもので個人の勝手・自由です。
また、大文字始まりで書けるというメリットがあるらしいです。

@始まりは、インスタンス変数。
グローバル変数と同じように、大文字始まりで書け、トップレベルで自由に使うことができるようです。

eval

Make10のように数字の間に+や-などの記号を入れたり入れなかったりして色々な数式を作って評価するときに、evalは便利だと思っています。

eval "6 + 3 * 2 - 2" #=> 10

あと、短いコードを書くゴルフ勢が、入力まわりでevalを用いているのをよく見ますね。

優先順位

算数・数学で、四則演算はx``÷は+``-より優先されます。
同じようにRubyの挙動もそうなっており、様々な記号について優先順位がついてます。

【罠】三項演算子こと条件演算子の優先順位

条件演算子がよく使われるのは代入や出力の場面です。丸括弧を書かない人も多く見受けられます。
ここだけみると、代入やメソッドよりも、条件演算子の優先順位が高いことがわかります。
しかし、全体的に見たとき、条件演算子の優先順位は、遅い方なので気をつけた方がいいです。特に要素を<<で挿入するときです。

ans = true ? "Yes" : "No" # "Yes" # 「ans = (true ? "Yes" : "No")」というように条件演算子が先です。
puts true ? "Yes" : "No" # "Yes"

a = []
a << true ? 0 : 1 # 「(a << true) ? 0 : 1」と解釈される。「a << (true ? 0 : 1)」ではない。
p a #=> [true]

一応説明しますと、ここでは例としてtrueをそのまま書きましたが、実践では真偽値の入った変数やメソッドを使うところです。

【罠】and/or, &&/||は似て非なるもの

and/orと&&/||は、一見エイリアスぽく見えそうです。
もしPythonからRubyを知ると、and/orを使いたくなるかもしれません。
しかし、and/orと&&/||とでは優先順位などが異なり、ふつう&&/||を使います。

優先順位の中で、and/orは、&&/||より遥か下です。
Ruby リファレンスマニュアルの演算子式 ()を見ると、and/orの優先順位は1番下です。
and/orは、式ではなく文であるため、優先順位が低いです(Matzが言ってました)。文を丸括弧で囲むと式になります(Matzが言ってました)。式は、返り値を返すものです。どうも、and/orは、左と右に式を並べて式 and 式のような形で並べて1つの文を作り、返り値を返す想定はしてないようです。返り値を返したくば、x = (式 and 式)と丸括弧で囲んで式にしてやるらしいです。

p true && true ? "Yes" : "No"  #=> "Yes" # p((true && true) ? "Yes" : "No")、と解釈される。
p true and true ? "Yes" : "No" #=> true  # (p(true)) and (true ? "Yes" : "No")、と解釈される。

一般に判定のための2条件を論理演算子でまとめるときは&&/||なら思わぬ挙動をしなくて済むはずなので、&&/||を使いましょう。

なお、Ruby リファレンスマニュアルの演算子式 ()で列挙されている中ではand/orの優先順位は1番下ですが、それらより後置if/後置while等の方がさらに優先順位が低いです。and/orと後置if/後置unlessの関係は、左から見るか右から見るかの違いだと思います。厳密には、式にしたときの返り値が違ったり、並べられる個数などに違いはありますが。

再帰関数を使わないようにする

再帰関数は遅いイメージがあったり、再帰回数に制限があるので、避けれるなら避けてみてもいいのかなと思います。
AtCoderの方は再帰できる回数が増えるようにスタックサイズを変更してくれているのですが、他のジャッジはそうではなく深い再帰をするとすぐエラーになるはずで厳しいです。

なお、以下が階乗の余りを求めるときの、再帰と非再帰による時間の比較です。

require 'benchmark'

def recursive_factorial(n)
  n == 0 ? 1 : (n * recursive_factorial(n - 1) % 1_000_000_007)
end

def non_recursive_factorial(n)
  a = [n]
  res = 1
  while(i = a.pop)
    (i == 0) ? (i = 1) : a.push(i - 1)
    res = res * i % 1_000_000_007
  end
  res
end

n = 10**6
Benchmark.bm(12) do |r|
  z = r.report("Recursive    ") { recursive_factorial(n)  }
  z = r.report("Non-Recursive") { non_recursive_factorial(n)  }
end
#                    user     system      total        real
# Recursive      0.048837   0.043499   0.092336 (  0.092420)
# Non-Recursive  0.077441   0.000025   0.077466 (  0.077481)

【高速化】クラス変数は遅い？

クラス変数のアクセスが、その他のインスタンス変数やグローバル変数などよりも1.6倍以上遅い感じがします。
コードをリファクタリングしたときにクラス変数に変更したら、遅くなって気がつきました。
遅くなるのは困るので、仕方なくクラス変数の代わりにグローバル変数を用いました。

以下が、実際に遅くなる計測結果です。

require "benchmark"

$var = 10**9 + 7

class Variable
  @@var = 10**9 + 7
  CONST = 10**9 + 7
  def initialize; @var = @@var end
  def instance_var; @var end
  def class_var;   @@var end
  def global_var;   $var end
  def const; CONST end
end

n = 10 ** 6
puts "n = #{n}"
Benchmark.bm(11) do |r|
  v = Variable.new;
  r.report("class_var   "){ n.times{ |i| v.class_var    } }
  r.report("instance_var"){ n.times{ |i| v.instance_var } }
  r.report("global_var  "){ n.times{ |i| v.global_var   } }
  r.report("global_var  "){ n.times{ |i| v.const   } }
end

# n = 1000000
#                   user     system      total        real
# class_var     0.093062   0.000000   0.093062 (  0.093142)
# instance_var  0.054679   0.000000   0.054679 (  0.054680)
# global_var    0.056477   0.000000   0.056477 (  0.056478)
# global_var    0.054198   0.000000   0.054198 (  0.054212)

その他

jitオプション

AtCoderの起動オプションに対してjitオプションをつけてみてはという提案があったのですが、
2秒程度のプログラムだとかえって遅くなるとのことでデフォルトでのオプションは入らなかったようです。
jitが機能しているかどうかはRubyVM::MJIT.enabled?を出力することで確かめられるようです。
時間制限のかなり長い問題だったら、RubyやBashからjitオプションつけてコマンドを叩き直すと効果があるかもしれません。

(この記事を最初に公開したとき、「自分は時間に変化がなく効果を感じたことがないですが、時間制限の長い問題では有効かもしれない」みたいに書いた気がするのですが、実際機能するようにできないようで、当然効果を感じるわけもなかったです!!)

オンラインエディタ

エディタにこだわりがなければ、オンラインでRubyを書いてそのまま実行できるサービスがいくつかあります。

• paiza.io
  使いやすいです。使ったことないですが、Vimやemacs風にしたり、共同編集、GitHub連携もできるらしいです。
• Wandbox
  Rubyの色々なバージョンが揃っていて、最新や過去のバージョンを使えてすごいです。
• ideone.com
  海外のサイトです。

この他、各競技プログラミングサイトAtCoder, yukicoder, Coedforcesでも、コードを確かめるだけの場所があります。
自分はかなり意外だったのですがAtCoderのエディタが変なサジェストもなくシンプルで使いやすいという方もいるので、使ってみるといいかもしれないです。

ac-library, ACL

AtCoder Library(ac-library, ACL)というのがあります。
これは、AtCoderが、幅広い問題を出題するために、公式に提供するC++ライブラリです。
DSU(UnionFind), FenwickTree(BIT), SegTreeなど大きく10種類ぐらい提供しています。

公式はC++ライブラリのみですが、各メジャーな言語について有志が同様のライブラリを作成しており、
Ruby版のac-library-rbbが存在します。
ただ、難しい問題で使うライブラリも多く、抽象遅延セグメントツリーやConvolutionなどはRubyそのものの遅さにより問題を解いてもTLEする可能性が高い気がします。

最後に

本記事で、i == 0とi.zero?のどっちを書こう等の煩悩が取り払われたら幸いです。

明日のRuby Advent Calendar 2020は、ima1zumiさんの記事です。

参考サイト

Rubyで競プロするときのTips - ARMERIA
2018/12/01の記事。本記事を作成するにあたり、参考にさせてもらいました。

RubyでAtcoder水色になりました！ - kona0001の日記
2020/11/24の最近の記事で、とても共感できることが多かったです。
特に「２次元グリッド問題が通らない」という主張について、「わかる!!」と共感しました。

ARC104 / B - DNA Sequence - kasumi∞blog (2020/10/4)
ハッシュのキーを文字列ですると通らなかったけれど、シンボルに変更したら通ったというブログ。
この問題は、想定解法と同じアルゴリズム・計算量でも、書き方でAC/TLEが分かれる典型だと思います。

Ruby 3.0 で x ** 2 が速くなった件 - Qiita (2020/10/6)
Ruby の prime が爆速化した件 - Qiita (2020/12/10)
scivolaさんのQiita記事。最新のRubyでは、改善されることがわかりました。