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

はじめに

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

A - Sequence of Strings

a-284.rb

n = gets.to_i
array = Array.new(n){gets.chomp}
puts array.reverse

解説

与えられた文字列を配列に格納して、reverseメソッドを使って順序を逆にしています。

B - Multi Test Cases

b-284.rb

t = gets.to_i
t.times do
  gets
  a = gets.split.map(&:to_i)
- puts a.select{ |i| i.odd?}.size
+ puts a.select(&:odd?).size
end

<追記>
コメントでいただいた別解になります。

別解

t = gets.to_i

t.times do
  gets
  puts gets.split.map(&:to_i).count(&:odd?)
end

解説

selectメソッドを使って奇数である要素とすべて取得して、sizeメソッドを使ってその要素数を取得しています。

C - Count Connected Components

c-284.rb

n, m = gets.split.map(&:to_i)
array = Array.new(n + 1){[]}
m.times do
    u, v = gets.split.map(&:to_i)
    array[u] << v
    array[v] << u
end

searched = Array.new(n + 1, false)
ans = 0
for i in 1..n
    next if searched[i]
    searched[i] = true
    ans += 1
    stack = [i]
    while node = stack.pop
        array[node].each do|factor|
            next if searched[factor]
            searched[factor] = true
            stack << factor
        end
    end
end
puts ans

<追記>
コメントでいただいた別解になります。tsortライブラリを使って解くこともできるようです。

別解1

require "set"
require "tsort"

n, m = gets.split.map(&:to_i)

graph = (1..n).to_h{ |i| [i, Set[]] }

m.times do
  node1, node2 = gets.split.map(&:to_i)
  graph[node1] << node2
  graph[node2] << node1
end

class << graph
# class Hashでもできるみたいです
  include TSort

  alias tsort_each_node each_key

  def tsort_each_child(node, &block)
    fetch(node).each(&block)
  end
end

puts graph.strongly_connected_components.count

別解2

class UnionFind
  def initialize(size)
    @rank = Array.new(size, 0)
    @parent = Array.new(size, &:itself)
  end
  
  def unite(x, y)
    x = root(x)
    y = root(y)
    return if x == y

    if @rank[x] > @rank[y]
      @parent[y] = x
    else
      @parent[x] = y
      @rank[y] += 1 if @rank[x] == @rank[y]
    end
  end

  def root(x)
    loop do
      if @parent[x] == x
        return x
      else
        x = @parent[x]
      end
    end
  end
  
  def same_set?(x, y)
    root(x) == root(y)
  end
  
  def size
    @parent.map { root(_1) }.uniq.size
  end
end

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

union = UnionFind.new(n)
uvs.each { |u, v| union.unite(u - 1, v - 1) }
puts union.size

解説

DFSを使って連結成分の個数を数え上げることができます。

D - Happy New Year 2023

d-284.rb

t = gets.to_i
t.times do
    n = gets.to_i
    a, b = 0, 0
    i = 2
    while i * i * i <= n
        if n % i != 0
            i += 1
            next
        else
            break
        end
    end
    if (n / i) % i == 0
        a = i
        b = n / (i * i)
    else
        a = Math.sqrt(n / i)
        b = i
    end
    puts "#{a.to_i} #{b.to_i}"
end

解説

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

<方針>
問題文のにある通り、N=p^2 qが成り立つことから、min(p,q)^3<=Nであることが分かります。したがって、min(p, q)について探索するのはNの立方根までで良いことが分かります。そして、一方が決まればもう一方は一意に定まります。

<実装方法>
方針で述べたことに場合分けをプラスして実装していけばOKです。なお、#{}の中に変数を書くと文字列内でも変数を使うことができます。

終わりに

C問題は、以前にも連結成分ごとに調べるようなDFSを実装したことがあったので簡単でした。D問題は、自力ではTLEが消せませんでしたね...。