AtCoder Beginner Contest 344参戦記録(A～C問題)

RubyでAtCoderに参戦した記録です。
AB2完で、C問題はコンテスト終了後に解説を見てからコードを書きました。

ABC344 A Spoiler

2つの「|」を含む文字列Sが与えられ、「|」とその間にある文字を削除して出力します。

# 提出コード
a = gets.chomp
pos = a.index("|")
ans = []
ans << a.slice(0...pos)
pos2 = a.index("|", pos+1)
ans << a.slice(pos2+1..-1)
puts ans.join

早く解かねばと焦ってしまい、回りくどいことをしてしまいました。
「|」記号でsplitすればシンプルに書けました。。

a = gets.split("|")
puts a[0] + a[2]

ABC344 B Delimiter

与えられる個数不明の整数を、逆順に出力する問題です。
IO#readlinesで入力値を受け取れば、行数が不明でも大丈夫です。

line = readlines.map(&:to_i).reverse
line.each do |e|
  puts e
end

ABC344 C A+B+C

A、B、C、Xと4つの数列が与えられ、数列Xの各値について、A、B、Cの各要素から1つずつ選んだ和で表すことができるかを出力する問題です。
Xの値一つ一つに対し、A、B、Cで実現できるか？を試すとTLEになります。
そこでA、B、Cから1つずつ選んだ和をリストアップし、Xがそのリストに含まれているかどうか？で判定しよう、というところまでは思いついたのですが、これでもTLEとなってしまい、結局解くことができませんでした。。

# TLE解答
n = gets.to_i
arraya = gets.split(" ").map(&:to_i)
m = gets.to_i
arrayb = gets.split(" ").map(&:to_i)
l = gets.to_i
arrayc = gets.split(" ").map(&:to_i)
q = gets.to_i
arrayx = gets.split(" ").map(&:to_i)

result = []
arraya.each do |a|
  arrayb.each do |b|
    arrayc.each do |c|
      result << (a+b+c) if !result.include?(a+b+c)
    end
  end
end

arrayx.each do |x|
  if x < result.min || result.max < x
    puts "No"
  elsif result.include?(x)
    puts "Yes"
  else
    puts "No"
  end
end

解説を見ると考え方は合っていたようです。
ACされた方の解答を参考にしながら、上記TLEの解決法を考えました。

方針1：和のリストをHashにする

どうやら和のリストを配列にしていたのがまずかったようです。Xの値が和のリストに含まれているかの検索に時間がかかり、TLEになってしまっていました。
検索速度の違いは、

• 配列：O(n)
• ハッシュ：O(1)
  ということで、ハッシュでコードを書きなおしてみました。

# 標準入力の受け取りは省略
result = {}
arraya.each do |a|
  arrayb.each do |b|
    arrayc.each do |c|
      result[a+b+c] = true
    end
  end
end

arrayx.each do |x|
  if result[x]
    puts "Yes"
  else
    puts "No"
  end
end

こちらでACとなりました。

方針2：Setクラスの利用

調べていく中でSetクラスなるものを知りました。Arrayクラスよりも高速に検索できる手法のようです。

【Setクラス概要】

• setライブラリに含まれているので、「require 'set'」で読み込みが必要
• Set.newすると、引数で与えた要素をもとに新しい集合が作られる
• その集合は引数の配列要素をキー、値をtrueとするHashのような形で作成される

つまり、方針1でHashに和の要素を格納したのと同じような形になるので、検索速度が上がりTLEにならずに済むということのようです。

require 'set'
n = gets.to_i
arraya = gets.split(" ").map(&:to_i)
m = gets.to_i
arrayb = gets.split(" ").map(&:to_i)
l = gets.to_i
arrayc = gets.split(" ").map(&:to_i)
q = gets.to_i
arrayx = gets.split(" ").map(&:to_i)

result = []
arraya.each do |a|
  arrayb.each do |b|
    arrayc.each do |c|
      result << a+b+c
    end
  end
end

set = Set.new(result)
arrayx.each do |x|
  if set.include?(x)
    puts "Yes"
  else
    puts "No"
  end
end

おわりに

今回もC問題の配点が低かったので確実に取りたかったのですが、焦りもあり結果を出せませんでした。落ち着いて考えてみればハッシュ化することも気づけたはずなのに…
ただこの問題のおかげでSetクラスの存在を知ることができました。引き続き貪欲に学んでいこうと思います。

参考リンク

https://docs.ruby-lang.org/ja/3.2/class/Set.html
https://qiita.com/an_sony/items/708c47d073ad709431d6
https://zenn.dev/hyzsa/articles/20230914-ruby-array-include-vs-set-include