はじめに
Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC242のA, B, Cを解きました。備忘録として解き方をまとめていきたいと思います。
A - T-shirt
a-242.rb
a, b, c, x = gets.split.map(&:to_f)
puts x <= a ? 1.000000 : x <= b ? c / (b - a) : 0.000000
解説
XがA以下の場合は、必ずTシャツがもらえるので確率は1です。また、XがB以下の場合は、Tシャツをもらえる確率はC / (B - A)となります。XがBより大きい場合は、Tシャツはもらえないので確率は0となります。
B - Minimize Ordering
b-242.rb
puts gets.chomp.chars.sort.join
C - 1111gal password
c-242.rb
n = gets.to_i
mod = 998244353
dp = Array.new(n + 1) { Array.new(11, 0) }
[*1..9].each{ dp[1][_1] = 1}
1.upto(n - 1) do |i|
1.upto(9) do |j|
dp[i + 1][j] = (dp[i][j - 1] + dp[i][j] + dp[i][j + 1]) % mod
end
end
puts dp[-1].sum % mod
解説
（公式解説を参考にしました）
動的計画法を使って解くことができます。dp[4][7] = f(7???)のとき、dp[4][7] = dp[3][6] + dp[3][7] + dp[3][8]のような漸化式が成り立ちます。
1桁のときはそれぞれの数値について1通りなので、1で初期化します。後は、与えられた整数の桁数に応じてdpの値を更新していきます。答えは、条件を満たす場合の総和を998244353で割った余りとなります。