Rubyで競技プログラミング
DiaryRubyで競技プログラミングに参加する場合のTips等を書いていきます。
Rubyが使える競プロサイト
- 日本語あり
- 英語
入力について
基本(1) 整数の読み込み
いろいろなやり方がありますが、筆者はgets.split.map(&:to_i)をよく使います。
Kernel#getsで1行読み込み、String#splitで空白区切りで分解し、String#to_iで整数に変換します。
例：
N M
a1
a2
...
an
N, M = gets.split.map(&:to_i)
AS = N.times{ gets.to_i }
基本(2) 小数の読み込み
入力が小数である場合はto_iの代わりにto_fを使います。
基本(3) 文字列の読み込み
入力が文字列である場合はgetsで1行読むことができます。getsの返り値は改行文字も含むので、改行文字が要らない場合はgets.chompとしてString#chompメソッドで末尾の改行文字を削ります。
応用
入力がすべて整数値の場合は、$stdin.readを使うと少し短く書けます。
N M
a1
a2
...
an
N, M, *AS = $stdin.read.split.map(&:to_i)
1行に複数の数がある場合はEnumerable#each_sliceが使えます。これはEnumeratorを返すのでto_aで配列にします(しなくても問題ないケースもありますが、例えばn番目の要素を取得したりとかはArrayでないとできません)
N M
a1 b1
a2 b2
... ...
an bn
N, M, *rest = $stdin.read.split
ABS = rest.each_slice(2).to_a
注意点
気をつけた方がいいことを書きます。
整数の割り算は整数になる
3 / 2が1.5になるか1になるかはプログラミング言語によって違いますが、Rubyは1になるタイプの言語です。このため、数xとyの割り算結果を小数で得たい場合は、
x / y.to_f
のように割り算をするまえにto_fで小数に変換します。
高速化について
TLE(Time Limit Error)を回避するためのテクニックを書きます。
注：高速化はボトルネック(一番重たい部分)に対して適用するものです。重くない部分に以下のテクニックを適用しても効果は薄いでしょう
中間配列の生成を避ける
xを最小値に更新する際、以下のように書くのが自然ですが、minメソッドを呼ぶためにArrayオブジェクトが生成されます。
x = [x, y].min
以下のようにすることでArrayの生成を避けることができます。
x = y if y < x
Floatの使用を避ける
経路探索などで配列をFloat::INFINITYで初期化することがありますが、計算に整数(Fixnum)しか使わない場合は、最大値も適当な整数にすることで少し速くなります。
最終手段
Crystal を使うという手があります(?)。CrystalはRubyによく似た文法のコンパイル言語です。
