ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Rubyで競プロするときのTips

Ruby 競技プログラミング プログラミング

ある程度知見が溜まってきたのでまとめていきます。

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

2018年12月くらいの情報です。

サイト バージョン
AtCoder 2.3.3
Codeforces 2.0.0
yukicoder 2.5.3
AOJ 2.4.0

この記事は基本的にAtCoderの2.3系を対象に書いていきます。

Codeforcesはちょっとバージョンが古いのと、実行時間制限がキツ目なので私はRubyを使っていません。

入出力編

基本的な入力。

N = gets.to_i               # 単一整数
a = gets.split.map(&:to_i)  # スペースで区切られた複数の整数
a = N.times.map{gets.to_i}  # 縦に並んだ複数の整数。たまにある
S = gets.chomp              # 文字列。chompを付けないと改行文字がついてくる

以下のような形式の入力もよく見ますね。

N
a_1 b_1
...
a_N b_N

これは次のように書くとスマートです。

N = gets.to_i
a, b = N.times.map{gets.split.map(&:to_i)}.transpose

# [[a_1, b_1], ..., [a_N, b_N]] を転置して
# [[a_1, ..., a_N], [b_1, ..., b_N]] にする

出力は puts を使うとよいです。数値も文字列も出力できて、改行文字が自動で付与されます。

数値編

多倍長整数

Rubyの整数は自動的に桁数が拡張されるため、算術オーバーフローはありません。

10**100    #=> 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

とはいえ、あまりに桁数の多い多倍長整数を計算し続けているとTLEやMLEになります。

負の数を含む剰余計算

bが正のとき、a % bは必ず0以上となります。

-1 % 3    #=> 2

言語によっては上記の結果は-1となるかもしれません。競技プログラミングではどちらが扱いやすいでしょうか？個人的にはRubyの挙動のほうが好きです。

ちなみにほとんどやらないと思いますが、-1 % -3は-1になります。

浮動小数の出力

浮動小数をputsなどで出力する場合、値が大きくなると指数表記になります。

puts (10**15).to_f    # 出力: 1.0e+15

内部的にはto_sが実行されているのですが、リファレンス上は「人間が読みやすい形の文字列表現」という何ともスッキリしない書かれ方がされています。

実際にこの問題の出力例3に示されている数は、putsを用いると1.0e+15と出てしまいます。（ただ、この問題はそれでもジャッジが通りました。）

解決方法はsprintfなどを使うことです。

puts sprintf("%f", (10**15).to_f)    # 出力: 1000000000000000.000000

1e9のようなリテラル表記

例えば C++で 10^{9} + 7 を代入したい時にこんな書き方をします。

const int64_t MOD = 1e9 + 7;

1e9 のようなリテラル表記はRubyでもC++でも浮動小数ですが、C++では変数を整数型で宣言していれば代入時にキャストされます。

一方、Rubyの場合は変数に型がないので浮動小数のままです。整数値を代入したい場合は**を使いましょう。

MOD = 1e9 + 7    #=> 1000000007.0
MOD = 10**9 + 7  #=> 1000000007

ビット演算

ORやANDなどの基本的な演算は他言語と同様にありますが、個人的によく使うのが「整数の k ビット目を取り出す」操作です。Rubyでは以下のように書くことができます。

5[2] #=> 1    最下ビットを0として、下から2番目のビット

ビットシフトなどを使って書くよりも簡潔ですね。見た目はキモいですが便利です。取り出すだけで、ビットへの代入（値の変更）はできません。

また、整数のビット長は bit_length を使って取り出すことができます。これは2.0系にはないのでCodeforcesで使うとREで死にます。

5.bit_length #=> 3

最小公倍数、最大公約数

標準で使えます。

10.gcd(4)  #=> 2
10.lcm(4)  #=> 20

素数関連

prime モジュールを使えば素数列挙や素因数分解ができます。

require 'prime'
Prime.each(15).to_a       #=> [2, 3, 5, 7, 11, 13]  15以下の素数
Prime.prime_division(24)  #=> [[2, 3], [3, 1]]      2**3 * 3**1

配列編

要素の追加/削除にはなるべく破壊的操作を使う

Rubyの配列は、先頭・末尾に対する要素の削除と追加を効率的に行うことができます。この点ではC++のdequeと似ています。

これらの操作は破壊的操作（push/pop/shift/unshift）として提供されています。もし不都合がなければできるだけ破壊的操作を使うようにしましょう。速度が全然違います。

a = a + [1]    # 非破壊的操作
a.push(1)      # 破壊的操作

配列のmax/minよりifや三項演算子を使う

複数の値の最大値や最小値を求めるとき、わざわざ配列を作ってmin/maxで判定するよりは、ifや三項演算子を使ったほうが速くなります。競技プログラミングでは以下のような操作をよく行いますね。

ans = #<暫定最適解>
while #<何かの条件>
  result = #<何かの計算結果>
  ans = [ans, result].max      # これは遅い
  ans = result if ans < result # こっちのほうが速い
end
puts ans

ループの深いところでminやmaxを使うとかなり遅くなるので注意です。たまに300点問題とかでもこれが原因でTLEを食らったりします。

なお、この現象はRuby 2.4以降においては改善されています。

負のインデックス

Rubyの配列で負のインデックスを取ると、「末尾から数えて k 番目」の意味になります。C++のvector::backと同様、末尾の値が欲しいときによく使います。

a = [1, 2, 3]
a[-1]  #=> 3

他にも少しトリッキーな使い方があって、添字がマイナスになるところの処理を少し簡略化できます。例えば

  • 累積和を0-indexで取ると範囲和が S[r] - S[l-1] のようになり、l=0 の時に負数になってしまう
  • グリッドで隣のマスにアクセスする時に、インデックスが減る方向を参照すると S[i-1][j] のようになり、i=0 の時に負数になってしまう

など。負数インデックスが例外や未定義動作になる言語では気を使わないといけないですが、Rubyでは末尾の参照になるので、末尾に「番兵」的な値を入れておくことで少しだけ実装をスマートにできます。ただ、ちょっと気持ち悪いとかバグらせそうとかあると思うので、お好みで。

配列の要素の合計

2.4だとsumが使えるのですが、2.3系以前であればinjectを使いましょう。

a = [1, 2, 3, 4]
a.inject(:+)  #=> 10
a.inject(:*)  #=> 24    たまに積も使う

二分探索

競技プログラミングでよくつかう二分探索。C++だとlower_boundやupper_boundがよく使われますが、Rubyにはもう少しだけ高機能なbsearchメソッドがあります。これは判定条件をブロックとして与えることができます。

※C++だとpartition_pointという関数で類似のことができるようですが、あまり使われていないような気がしますね…。

これはArrayまたはRangeに対して使えます。リファレンス をみる限りちょっと仕様が難しいのですが、二分探索可能な（単調な）場合において「ブロック内の条件を満たす一番左の要素」を返します。どの要素もブロック内の条件を満たさない場合はnilが返るので注意です。

(1..(10**9)).bsearch{|n| n*n >= 500}  #=>23    これはceil(sqrt(500))に相当

ブロックの中に判定ロジックが書けるので、判定ロジックが短く書けるような問題においては特に使いやすいです。こんな書き方もできます。

浮動小数の範囲オブジェクトに対しても使えますが、精度や反復回数を指定できないので競技プログラミングにおいて使うのは少し不安です。

スコープ編

定数

大文字で始まる識別子は定数となり、オブジェクトを再代入すると警告が出力されます。警告なのでまあ処理はされるのですが、気になる場合は再代入しそうなものを大文字で書き始めるのは避けましょう。競プロでは入力として与えられる整数などは定数でよいと思います。

また定数の地味なメリットですが、トップレベルで宣言した定数はトップレベルで宣言したメソッドの中で使うことができます。Rubyのグローバル変数は少し記法が面倒なので、競プロであれば入力値などのプログラム全体で使う値くらいはこのように楽に参照してもよいでしょう。

def subroutine
    a = N/2    # ここでNを参照できる
   ....
end

N = gets.to_i
....

おわり

何か思いついたら追記します。