はじめに

前回記事の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 の作者さんありがとう
プルリクよろしくお願いします