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

はじめに

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

A - Anyway Takahashi

a-269.rb

a, b, c, d = gets.split.map(&:to_i)
puts (a + b) * (c - d)
puts "Takahashi"

B - Rectangle Detection

b-269.rb

array = Array.new(10){ gets.chomp }
str = "." * 10
a = b = c = d = 0
array.each_with_index do |factor, index|
  if factor != str
    a = index + 1
    c = factor.index("#") + 1
    d = factor.rindex("#") + 1
    break
  end
end

array.reverse.each_with_index do |factor, index|
  if factor != str
    b = 10 - index
    break
  end
end

puts "#{a} #{b}"
puts "#{c} #{d}"

解説

最初にa, c, dを求めます。次に、配列の順序を逆転させてbを求めます。なお、bは配列の順序を逆転させているので10-indexとしています。

C - Submask

c-269.rb

n = gets.to_i
m = n
ans = [n]
while m > 0
  m = (m - 1) & n
  ans << m
end
puts ans.sort

解説

どちらも1であるような整数を求めればいいので、&を使うことで実装することができます。

D - Do use hexagon grid

d-269.rb

n = gets.to_i
array = Array.new(n){ gets.split.map(&:to_i) }

hash = {}
array.each_with_index do |factor, index|
    hash[factor] = index
end

searched = Array.new(n, false)
dx = [-1, -1, 0, 0, 1, 1]
dy = [-1, 0, -1, 1, 0, 1]
ans = 0
n.times do |i|
    next if searched[i]
    ans += 1
    stack = [i]
    while node = stack.pop
        x, y = array[node]
        searched[node] = true
        6.times do |j|
            nx = x + dx[j]
            ny  = y + dy[j]
            key = [nx, ny]
            if val = hash[key]
                stack << val unless searched[val]
            end
        end
    end
end
puts ans

解説

DFSで解いています。基本的には、連結成分の個数を求めるDFSと同様ですが、隣接している部分についてはあらかじめdx, dyを用意しておき順に探索しています。