はじめに
前回記事のview数の伸びに驚きました。普段の記事の10倍くらい
それはさておき、少しずつマッシュアップしたいものです。
Yokan Party
ご存知、競プロ典型90問の1問目。
二分探索を行います。
Ruby 元コード（最適化前）
before.rb
def check(mid)
cnt = 0
cut = 0
@a.each do |x|
if x - cut >= mid
cut = x
cnt += 1
end
end
cnt >= K + 1
end
N, L = gets.split.map(&:to_i)
K = gets.to_i
@a = gets.split.map(&:to_i)
@a << L
@a.unshift 0
puts (0..).bsearch{ check(_1).! } - 1
前回記事に比べ、defとbsearchを使用している分、難易度？がアップしています。
予め、crystalのACコードを参照させていただきました。（以下、当社調べ）
crystalでACされたユーザ：7名 少なっ
crystalのbsearchメソッドの使用ユーザ：3名（重複あり）
自作二分探索関数の使用ユーザ：2名（重複あり）
メソッド・関数の未使用ユーザ：3名
（メソッド・関数の未使用とは、いわゆるwhile high - low > 1を実装）
crystalのbsearchメソッドの認知度が低い様ですが、その理由も明らかになります？！
最適化
error01
13 | N, L = read_line.split.map(&.to_i)
^
Error: Multiple assignment is not allowed for constants
はい、コンスタントやめます。
error02
15 | @a = read_line.split.map(&.to_i)
^
Error: can't use instance variables at the top level
はい、インスタンス変数やめます。
error03
18 | puts (0..).bsearch{ check(_1).! } - 1
^-
Error: undefined local variable or method '1' for top-level
はい、Numbered parameterやめます。
error04
4 | a.each do |x|
^
Error: undefined local variable or method 'a' for top-level
はい、引数で渡します。
error05
5 | if x - cut >= mid
^
Error: no overload matches '=' with type (Int32 | Nil)
はい、range(0..)がInt32を越えていました。
error06
18 | puts (0..1000000000).bsearch{ |b| check(b, a, k).! } - 1
^
Error: undefined method '-' for Nil (compile-time type is (Int32 | Nil))
はい、bsearchメソッドの戻り値が コンパイルの結果(Int32｜Nil) という型であることを知りませんでした。
Ruby 元コード（最適化後）
after.rb
def check(mid, a, k)
cnt = 0
cut = 0
a.each do |x|
if x - cut >= mid
cut = x
cnt += 1
end
end
cnt >= k + 1
end
n, l = gets.split.map(&:to_i)
k = gets.to_i
a = gets.split.map(&:to_i)
a << l
a.unshift 0
puts (0..1000000000).bsearch{ |b| check(b, a, k).! } - 1
Ripper.lexでbsearchが出現後の最初の}を}.not_nil!に変換するという力業。
crystal トランスパイルコード
crystal
def check(mid, a, k)
cnt = 0
cut = 0
a.each do |x|
if x - cut >= mid
cut = x
cnt += 1
end
end
cnt >= k + 1
end
n, l = read_line.split.map(&.to_i)
k = read_line.to_i
a = read_line.split.map(&.to_i)
a.push l
a.unshift 0
puts (0..1000000000).bsearch{ |b| check(b, a, k).! }.not_nil! - 1
| Ruby | crystal | |
|---|---|---|
| コード長(Byte) | 296 | 360 |
| メモリ(KB) | 21184 | 10476 |
| 実行時間(ms) | 206 | 36 |
実行時間が一桁速くなりました。
まとめ
- ripper の作者さんありがとう
- crystal の作者さんありがとう
- プルリクよろしくお願いします