kona0001の日記

Rubyで競プロする人の日記です

Rubyで競プロをするときに覚えておくと嬉しい機能

Rubyで競プロをする際に、知っていると地味に嬉しい機能をまとめてみました。

最近自分以外が書いたRubyのコードを見る頻度が増えたのですが、「ここはこう書いたらお得なのになぁ」と思う事がたまにあります。Rubyはすべてがオブジェクトであり、用意されているメソッドも豊富に思えます。自分がまだまだ知らないようなメソッドも多いことでしょう。

そこで、自分がRubyで競プロをする際に「これは便利だ」と思う割に、知らない人もいそうなものを羅列していきます。（掲載基準は自分がその機能を知ったときに特にびっくりしたものですｗ）思いつき次第追加していきます。

ModPow(累乗の剰余)

競プロでよくある「1000000007で割ったあまりを求める」問題で頻出な累乗の剰余ですが、自分で関数を定義して効率よく乗算をするプログラムを書いている人を見かけます。 Rubyだとこれが言語機能として標準で使えます。

MOD = 10**9+7
2.pow("とても大きい数",MOD) 
# => 2の累乗。pow関数の第二引数にMODを渡せる

剰余を計算してくれるだけでなく、高速な累乗の計算もしてくれるのでめちゃくちゃ便利です。

bsearch(二分探索)

Rubyには二分探索を行うためのメソッドbsearch, bsearch_indexがあります。「左側と右側を管理しながらwhileで差が１になるまで回して…」といった二分探索を簡単に実装できます。数値の範囲Rangeに対して実行することもできるし、ソートされたArrayオブジェクトに対しても同様に使えます。

(0..10**12).bsearch{|v| v >= 500}
# => 500が返される

(0..10**12).bsearch{|v| v >= -500}
# => 0が返される

(0..10**12).bsearch{|v| v >= 10**15}
# => nilが返される

[2,3,5,7,11].bsearch{|v| v > 5}
# => 7が返される(条件を満たす中で一番左の配列の値)

[2,3,5,7,11].bsearch_index{|v| v > 5}
# => 3が返される(条件を満たす中で一番左の配列のインデックス)

複雑な条件であってもブロック内で簡単に記述できますが、ブロックには返り値(boolean)が必要なことに注意です(左側がfalse、右側がtrue)。

nil || 数値

何かしらの処理をした後で変数にnilが代入されてしまい困るケースがあります。例えば上述した二分探索では、指定範囲内に満たすものが一つもない場合nilが返されます。多くのケースで一番右側の壁となっている数値が代入できれば嬉しいですが、これは論理演算子||を使うことで簡単に処理できます。

[2,3,5,7,11].bsearch{|v| v > 15} || 16
# => 16が返される(二分探索部分での返り値がnilなので、代わりに16が返される)

またこれとは別に、ある変数がnilの場合のみ右辺の値を代入する||=という記法も存在します。

x = nil
y = 5
x ||= 10
y ||= 15
p x  #=> 10
p y  # => 5

より厳密に、論理演算子||は「左から順に評価し真となる値を返す」という処理を行います。が、競プロにおいて||を同一の式で2つ以上使うことはあまりないと思います。

x = nil || false || 3 || true
p x  # => 3

GCD(最大公約数),LCM(最小公倍数)

Rubyにはユークリッドの互除法を用いたGCDおよびLCMを求めるメソッドが標準で用意されています。

12.gcd(16)  # => 4が返される
4.lcm(6)  #=> 12が返される

ただし、ユークリッドの互除法の考え方自体は競プロにおいて問われることがあるので、これらを地力で実装できる知識は付けたほうがいいでしょう。また、3つ以上のGCDやLCMを求めたいときは、injectまたはreduceメソッドを使うといいです。

(※2/23追記：simanmanさんから情報いただきました、ありがとうございます！)

# 1～10のLCMを求める
(1..10).inject(:lcm)

#12,16,18のGCDを求める
[12,16,18].inject(:gcd)

出力周り(putsでの改行、joinを用いた出力)

putsとArray(簡単に1行ずつ出力する)

putsの引数にArrayオブジェクトを渡すと、要素がひとつずつ改行された状態で出力されます。使えるかどうかは出力形式次第ですが、何かと使いやすいので積極的に使いましょう。

ans = [2,3,5,7,11,13]
puts ans  # => 配列の要素が一つずつ改行して出力される
puts ans[3..5]  #=> 配列の特定範囲の出力も簡単

join(一列に並べる)

たまにある出力形式で「答えの配列を一行に、要素同士をスペース入れる」ものがあります。そんな時に便利なのがjoinメソッドです。joinメソッドは「配列の要素の間に、joinの引数で指定された文字列を挿入した文字列オブジェクト」を返してくれます。つまりarray.join(" ")のようにスペースを引数に取ることで、一列にスペースで区切られて並んだ配列を出力することができます。

ans = [2,3,5,7,11,13]
puts ans.join(" ")
# => 2 3 5 7 11 13　が出力される

定数倍高速化

Whileでループを早くする(お手軽な定数倍高速化)

Rubyのブロックは遅いです。つまり、ブロックを使わずにループを回すと実行時間が早くなります。具体的には、forやtimesではなくwhileを使いましょう。

#遅い
n = 10000000
cnt = 0
n.times do |i|
  cnt += i
end

#早い
n = 10000000
cnt = 0
i = 0
while i < n
  cnt += i
  i += 1
end

これは完全に経験則なのですが、Rubyでの競プロ(Atcoder)において計算量106を越したらwhileを使ったほうがいいです。びっくりするぐらい実行時間が変わるので、実行時間に困ったときはとりあえずコード内のループをできるだけwhileに変えるといいと思います。よくある制約N=2000で想定解法O(N2)の問題では特に有効です。

長い文字列の入力

文字列の長さが大きい場合、文字列の一部分の参照(一文字ずつ取り出すなど)はとても実行時間が遅くなります。文字列の長さが100を超す場合は、一文字ずつ配列に格納した方がいいです。 (※2/23追記：simanmanさんからcharsメソッドの情報いただきました、ありがとうございます！)

input = gets.chomp.split("") 
# splitメソッドで文字列をひとつずつ分解し、配列に格納する

input = gets.chomp.chars
# 上と同じ処理。こっちのほうが簡潔で分かりやすい

これはgrid問題なんかでも使えます。「1行ずつ文字列オブジェクトとして取り出す」のではなく、「2次元配列として文字をひとつずつ格納する」方が取り扱い的にも速度的にも安心です。

結び

他にもRubyにおける細かいテクニックはたくさんあるので、思いつき次第追加していきます。（間違ったことがあったらコメントで指摘していただければ嬉しいです＞＜）

最後に、参考にしたサイトのリンクを貼って結びとします。こちらも素晴らしい記事なのでぜひ見てみてください！