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

はじめに

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

A - flip

a-289.rb

puts gets.chomp.tr("01", "10")

解説

（他の方の提出結果を参考にしました）

trメソッドを使い、"0"を"1"に"1"を"0"に置換しています。

メモ
・String#tr：str.tr(pattern, replace)の形で使い、patternに書いた文字列がreplaceに書いた文字列に置換される。ただ、文字列自身というわけではなく、本質は文字の置換。今回の問題の場合は、"01"->"10"としてるが、これは"0"->"1"、"1"->"0"を意味している。

B - レ

b-289.rb

n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
hash = {}
a.each{ |i| hash[i] = true}

ans = []
l = 1
while l <= n
    r = l
    while hash[r]
        r += 1
    end
    r.downto(l).each{ |i| ans << i}
    l = r + 1
end
puts ans.join(" ")

解説

まず、レ点がある部分を連想配列hashにもたせます。そして、lを開始位置としてそこからレ点をもたない部分までrをインクリメントします。次に、rからlまでのindexに対応する数字をansに格納していきます。この操作を繰り返し行なっていき、最後にansを出力することで実装できます。

C - Coverage

c-289.rb

n, m = gets.split.map(&:to_i)
a = []
m.times do
    gets
    a << gets.split.map(&:to_i)
end

ans = 0
[0, 1].repeated_permutation(m).each do|arr|
    check = Array.new(n, false)
    i = 0
    while i < m
        if arr[i] == 1
            a[i].each do|j|
                check[j - 1] = true
            end
        end
        i += 1
    end
    ans += 1 if check.all?(true)
end
puts ans

<追記>
コメントでいただいた別解になります。すごくコンパクトですね！
こちらでは、combinationメソッドを使って条件を満たすものがいくつあるかを数え上げています。

別解

n, m = gets.split.map(&:to_i)
as = Array.new(m) { gets; gets.split.map(&:to_i) }

puts (1..m).sum {|i|
  as.combination(i).count {|arys|
    (1..n).all? { |j| arys.any? { _1.include?(j) } }
  }
}

解説

<方針>
この問題のように「選ぶ」「選ばない」といった２択を扱うような問題は、bit全探索という手法を使って解きます。Rubyでは、Array#repeated_permutationを用いることで簡単に実装することができます。

<実装方法>
前述したように、bit全探索を行なっていき、問題文の条件を満たすならansをインクリメントします。なお、ここでは0を「選ばない」、1を「選ぶ」として考えています。

D - Step Up Robot

d-289.rb

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

dp = Array.new(x + 1, false)
dp[0] = true
b.each{ |i| dp[i] = -1}

x.times do|i|
    next if !dp[i] || dp[i] == -1
    a.each do|factor|
        break if i + factor > x
        dp[i + factor] = true if dp[i + factor] != -1
    end
end
puts dp[x] ? "Yes" : "No"

解説

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

<方針>
DPを使って解いていきます。dp[i]をi段目に登れるならtrue、登れないならfalseとします。また、モチがある段は-1とします。

<実装方法>
順に、その段に登れるかを判定していき、最終的にx段目に登れればYes、登れなければNoを出力します。

終わりに

個人的には、B問題が工夫が必要で苦戦しました。また、D問題でDPを使うことを思いつくことができませんでした...悔しい。
次回は、AtCoder ABC288を解いていきたいと思います。