Ruby と crystal で解く AtCoder ABC248 C-D

はじめに

AtCoder さん、ありがとうございます。

C - Dice Sum

動的計画法を応用して解きました。

Ruby

n, m, k = gets.split.map(&:to_i)
MOD = 998244353
dp = Hash.new(0)
dp[0] = 1
n.times do |i|
  dp2 = Hash.new(0)
  (1..m).each do |x|
    dp.keys.each do |key|
      if key + x <= k
        dp2[key + x] += dp[key]
        dp2[key + x] %= MOD
      end
    end
  end
  dp = dp2
end
puts dp.values.sum % MOD

動的計画法では、配列をコピーしたりしますが、Hash#keysでコピーしている様な感じです。

crystal

n, m, k = read_line.split.map(&.to_i)
MOD = 998244353
dp = Hash(Int32, Int64).new(0)
dp[0] = 1
n.times do |i|
  dp2 = Hash(Int32, Int64).new(0)
  (1..m).each do |x|
    dp.keys.each do |key|
      if key + x <= k
        dp2[key + x] += dp[key]      
        dp2[key + x] %= MOD
      end
    end
  end
  dp = dp2
end
puts dp.values.sum % MOD

crystalではHashを使用する際、変数の型を指定する必要があります。
ここでは、Int32を越える可能性がありますので、Int64を指定しています。

	Ruby	crystal
コード長(Byte)	319	358
実行時間(ms)	706	179

D - Range Count Query

二分探索を応用して解きました。

Ruby

n = gets.to_i
a = gets.split.map(&:to_i)
h = Hash.new{ |h, k| h[k] = [] }
a.each_with_index do |e, i|
  h[e] << i + 1
end
q = gets.to_i
q.times do
  l, r, x = gets.split.map(&:to_i)
  if h.has_key?(x)
    ss = h[x].bsearch_index{ |e| l <= e } || h[x].size
    se = h[x].bsearch_index{ |e| r < e } || h[x].size
    puts se - ss
  else
    puts 0
  end
end

ここは、範囲を超えた場合のnil対策です。

nilガード

    ss = h[x].bsearch_index{ |e| l <= e } || h[x].size

crystal

n = read_line.to_i
a = read_line.split.map(&.to_i)
h = Hash(Int32, Array(Int32)).new{ |h, k| h[k] = [] of Int32 }  
a.each_with_index do |e, i|
  h[e] << i + 1
end
q = read_line.to_i
q.times do
  l, r, x = read_line.split.map(&.to_i)
  if h.has_key?(x)
    ss = h[x].bsearch_index{ |e| l <= e } || h[x].size
    se = h[x].bsearch_index{ |e| r < e } || h[x].size 
    puts se - ss
  else
    puts 0
  end
end

Rubyでハッシュの値に配列を使用する場合の定番の書き方があります。

Hash

h = Hash.new{ |h, k| h[k] = [] }

crystalでの書き方がよく分からないのですが、ごてごてしいです。

Hash

h = Hash(Int32, Array(Int32)).new{ |h, k| h[k] = [] of Int32 }  

	Ruby	crystal
コード長(Byte)	370	423
実行時間(ms)	665	164

まとめ

crystalはnil安全として静的な型チェックが入りますので、それを意識してコーディングする必要があります。