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

はじめに

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

A - Filter

a-294.rb

- n = gets.to_i
+ n = gets
a = gets.split.map(&:to_i)
ans = a.select{ |i| i.even?}
puts ans.join(" ")

解説

selectメソッドを使って偶数である要素を取得することができます。

メモ
・Array#select：Array.select{|要素| 条件}の形で使い、条件が真である要素をすべて含む配列を返す。

B - ASCII Art

b-294.rb

# 修正前
h, w = gets.split.map(&:to_i)
arr = ("A".."Z").to_a
h.times do
    a = gets.split.map(&:to_i)
    s = ""
    a.each do|i|
        if i == 0
            s += "."
        else
            s += arr[i - 1]
        end
    end
    puts s
end

b-294.rb

# 修正後
h, w = gets.split.map(&:to_i)
arr = [".", *"A".."Z"]
h.times do
    a = gets.split.map(&:to_i)
    s = a.map{ |i| arr[i]}
    puts s.join
end

<追記>
コメントでいただいた別解になります。こちらは、ASCIIコードにおいて、Aが65に、Bが66に、（以下同様）対応していることを利用しています。

別解

h, _ = gets.split.map(&:to_i)
as = Array.new(h) { gets.split.map(&:to_i) }

puts as.map {|row|
  row.map { |n| n.zero? ? "." : (n + 64).chr }.join
}

解説

まず、ピリオドとアルファベットをarr配列にもたせます。そして、インデックスがaの要素と等しいarrの要素を保持した配列を空白区切りで出力すればOKです。

メモ
・なぜ[*"A".."Z"]でアルファベットの配列を作れるのか
Splat展開：to_aを経由して展開されるため配列で返ってくる。（C言語のポインターみたいにアドレスを保持してそこから参照している？）

・文字列連結で次々に結合させていくのが良くない理由
str = str + charのように文字列を結合していくと、新たなStringオブジェクトが生成され元のStringオブジェクトは残ってしまうらしい（ガーベジ）。このガーベジはRubyの処理系が自動で消去してくれる（ガーベジコレクション、GC）がその処理がプログラムのノイズになり得るため。

C - Merge Sequences

c-294.rb

n, m = gets.split(" ")
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
c = (a + b).sort

hash = {}
c.each_with_index do|i, j|
    hash[i] = j + 1
end

aa = a.map{|i| hash[i]}
puts aa.join(" ")

bb = b.map{|i| hash[i]}
puts bb.join(" ")

解説

方針として、N, MがN, M <= 10^5と大きく愚直に何番目かを求めようとするとTLEするので一重ループで実装していくことを考えます。
まず、問題文通りにcを作り、連想配列hashにその要素がcでは何番目かをもたせます。そして、a, bそれぞれの要素に対して対応するvalueを返せば答えが求まります。

D - Bank

d-294.rb

n, q = gets.split.map(&:to_i)
hash = {}
call = 1
q.times do
    t, x = gets.split.map(&:to_i)
    case t
    when 1
        hash[call] = true
        call += 1
    when 2
        hash.delete(x)
    when 3
        puts hash.key(true)
    end
end

解説

C問題と同様、QがQ <= 5×10^5と大きいため一重ループで実装していくことを考えます。
初期設定として何番の人が呼ばれたかを記録する連想配列hashと次に呼ばれる人の変数callを用意しておきます。なお、最初に呼ばれるのは１番の人なのでcallの初期値は１としています。

1. t=1の場合
   番号がcallの人が呼ばれるのでhash[call]=trueとします。また、次に呼ばれるのは番号が１つ大きい人なのでcallの値をインクリメントしておきます。
2. t=2の場合
   呼ばれた人をhashから削除します。
3. t=3の場合
   最も番号が小さい人が呼ばれるのでtrueをvalueにもつkeyを出力します（左から探してくれるのでこのままいけます）。

終わりに

今回の問題は、D問題が比較的簡単でした。たまにこういうことがあるのでD問題だからと捨てずに少し挑戦してみるのもレーティングを上げる戦略としてはありだと思います！

参考

・メソッド呼び出し(super・ブロック付き・yield)
・Rubyのsplat展開について
・【Ruby のまずいコード】文字列連結