RubyでAtCoder ABC248(A, B, C, D)を解いてみた

はじめに

Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC248のA, B, C, Dを解きました。備忘録として解き方をまとめていきたいと思います。

A - Lacked Number

a-248.rb

puts [*"0".."9"] - gets.chomp.chars

解説

0~9の配列から与えられた文字列を配列にしたものを引いた後の数字が答えとなります。

B - Slimes

b-248.rb

a, b, k = gets.split.map(&:to_i)
ans = 0
while a < b
  a *= k
  ans += 1
end
puts ans

C - Dice Sum

c-248.rb

n, m, k = gets.split.map(&:to_i)
mod = 998244353

dp = Array.new(n + 1){Array.new(k + 1, 0)}
dp[0][0] = 1
n.times do |i|
  k.times do |j|
    1.upto(m) do |l|
      dp[i + 1][j + l] += dp[i][j] if j + l <= k
    end
  end
end
puts dp[n].sum % mod

解説

（公式解説を参考にしました）

dp[i][j] := 先頭からi項目までの総和がjであるような数列の決め方の総数として、dpの値を更新していくことで解くことができます。

D - Range Count Query

d-248.rb

gets.to_i
a = gets.split.map(&:to_i)

hash = Hash.new{ |h, k| h[k] = [] }
a.each_with_index{ |number, index| hash[number] << index }

q = gets.to_i
q.times do
  l, r, x = gets.split.map(&:to_i)
  l -= 1
  r -= 1
  val = hash[x]
  val_size = val.size
  nl = val.bsearch_index{ |i| l - 1 < i } || val_size
  nr = val.bsearch_index{ |i| r < i } || val_size
  puts nr - nl
end

解説

最初に連想配列hashにAの要素の数字をキー, インデックスを値として記録します。そして、与えられたクエリごとにAにおけるインデックスがL~Rの範囲で値がXとなるものの個数を出力することで解くことができます。なお、TLEを避けるため、nlとnrのインデックスを求める際にはbsearch_indexメソッドを使って二分探索しています。