AtCoder ABC #044 [Ruby]

abc044-a.rb

# AC
n = gets.chomp.to_i
k = gets.chomp.to_i
x = gets.chomp.to_i
y = gets.chomp.to_i
if n <= k then
  puts n * x
else
  puts k * x + (n - k) * y
end

abc044-b.rb

# AC
w = gets.chomp
h = Hash.new(0)
w.split("").each do |c|
  h[c] += 1
end
if h.values.all?{|x| x.even?} then
  puts "Yes"
else
  puts "No"
end

abc044-c-2.rb

# AC
# O(N^2X)
N, A = gets.chomp.split(" ").map(&:to_i)
x = gets.chomp.split(" ").map(&:to_i)
y = [0] + x.map{|x| x - A}
K_MAX = (x + [A]).max

dp = Array.new(N+1){Array.new(2*N*K_MAX+1, 0)}

(N+1).times do |i|
  (2*N*K_MAX+1).times do |j|
    if i == 0 && j == N * K_MAX then
      dp[i][j] = 1
    elsif i > 0 && (j - y[i] < 0 || j - y[i] > 2 * N * K_MAX) then
      dp[i][j] = dp[i - 1][j]
    elsif i > 0 && j - y[i] >= 0 && j - y[i] <= 2 * N * K_MAX then
      dp[i][j] = dp[i - 1][j] + dp[i - 1][j - y[i]]
    end
  end
end

puts dp[N][N * K_MAX] - 1

abc044-c.rb

# TLE (0)
n, a = gets.chomp.split(" ").map(&:to_i)
x = gets.chomp.split(" ").map(&:to_i)
xx = x.max
dp = Array.new(n + 1){Array.new(n + 1){Array.new(n * xx + 1, 0)}}
(0..n).each do |j|
  (0..n).each do |k|
    (0..(n * xx)).each do |s|
      if j == 0 && k == 0 && s == 0 then
        dp[j][k][s] = 1
      elsif j >= 1 && s < x[j - 1] then
        dp[j][k][s] = dp[j - 1][k][s]
      elsif j >= 1 && k >= 1 && s >= x[j - 1] then
        dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]
      end
    end
  end
end
ret = 0
(1..n).each do |i|
  ret += dp[n][i][i * a]
end
puts ret