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

はじめに

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

A - Good morning

a-245.rb

a, b, c, d = gets.split.map(&:to_i)
puts a < c || (a == c && b <= d) ? "Takahashi" : "Aoki"

B - Mex

b-245.rb

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

ans = 0
a.each do |number|
  if ans != number
    puts ans
    exit
  end
  ans += 1
end
puts ans

C - Choose Elements

c-245.rb

n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
dp = Array.new(2) { Array.new(n, false) }
dp[0][0] = true
dp[1][0] = true

1.upto(n - 1) do |i|
  if dp[0][i - 1]
    dp[0][i] = true if (a[i] - a[i - 1]).abs <= k
    dp[1][i] = true if (b[i] - a[i - 1]).abs <= k
  end
  if dp[1][i - 1]
    dp[0][i] = true if (a[i] - b[i - 1]).abs <= k
    dp[1][i] = true if (b[i] - b[i - 1]).abs <= k
  end
end
puts dp[0][n - 1] || dp[1][n - 1] ? "Yes" : "No"

解説

dp[i][j] := i=0のときAj=Xiが成り立つか、i=1のときBj=Xiが成り立つかとした動的計画法を考えることで解くことができます。なお、A(j-1), B(j-1)それぞれについて考える必要があることに注意して下さい。