Ruby と Crystal で解く AtCoder ABC 129 D

15184 ワード
Ruby ポエム crystal トランスパイラ AtCoder Ruby テキストリンク

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest D - Lamp
Difficulty: 1103

今回のテーマ、トランスパイラ

この問題は、以前に Ruby と Java で解く AtCoder ABC129 D 2次元配列 で解いております。Rubyにとって、速度的にきびしい問題です。

今回、Ruby のコードを Crystal のコードに手動トランスパイラしたところ、1281 ms->227 msに改善しました。将来、自動でトランスパイラされるとうれしいです。

Ruby -> JavaScript

RubyでトランスパイラといえばOpal
Ruby関連書籍の発刊がさびしいなか、2020年5月に 『実践Opal』 が出ています。
しかしながら競技プロでは、速度の改善は少ない（スクリプト言語->スクリプト言語のため）ものと考えられます。何かの間違いでRuby -> Javaになるとうれしい

Ruby -> C

Rubyを開発されている方は、RubyとCのマイスターなので、簡単にできる？

Ruby -> Go

Googleが密かに開発してそう

Ruby -> Crystal

Crystal

Crysta.cr
h, w = read_line.split.map { |c| c.to_i }
s = [] of Array(UInt8)
h.times do
  s << read_line.chomp.bytes
end
hs = [] of Array(Int32)
h.times do |y|
  cnt = 0
  v = [] of Int32
  w.times do |x|
    if s[y][x] == 46
      cnt += 1
    else
      cnt.times do
        v << cnt
      end
      cnt = 0
      v << 0
    end
  end
  cnt.times do
    v << cnt
  end
  hs << v
end
vs = [] of Array(Int32)
w.times do |x|
  cnt = 0
  v = [] of Int32
  h.times do |y|
    if s[y][x] == 46
      cnt += 1
    else
      cnt.times do
        v << cnt
      end
      cnt = 0
      v << 0
    end
  end
  cnt.times do
    v << cnt
  end
  vs << v
end
max = 0
h.times do |i|
  w.times do |j|
    max = hs[i][j] + vs[j][i] if max < hs[i][j] + vs[j][i]
  end
end
puts max - 1
Array.cr
h, w = read_line.split.map { |c| c.to_i }
s = [] of Array(UInt8)

標準入力と配列の初期化が変わっているだけで、違和感ないです。

Ruby

Ruby.rb
h, w = gets.split.map(&:to_i)
s = h.times.map { gets.chomp.bytes }
hs = []
s.each do |t|
  cnt = 0
  v = []
  t.each do |x|
    if x == 46
      cnt += 1
    else
      cnt.times do
        v << cnt
      end
      cnt = 0
      v << 0
    end
  end
  cnt.times do
    v << cnt
  end
  hs << v
end
vs = []
s.transpose.each do |t|
  cnt = 0
  v = []
  t.each do |x|
    if x == 46
      cnt += 1
    else
      cnt.times do
        v << cnt
      end
      cnt = 0
      v << 0
    end
  end
  cnt.times do
    v << cnt
  end
  vs << v
end
max = 0
h.times do |i|
  w.times do |j|
    max = hs[i][j] + vs[j][i] if max < hs[i][j] + vs[j][i]
  end
end
puts max - 1

元となったコードです。

Ruby 2.7.1 Crystal 0.33.0
コード長 (Byte) 710 811
実行時間 (ms) 1281 227
メモリ (KB) 158448 58176

約5倍速くなっています。

まとめ

  • ABC 129 D を解いた
  • Crystal に詳しくなった
Pythonは一方向チェーンテーブルの最下位からk番目のノードを見つけた
368. Largest Divisible Subset