【AtCoder】AtCoder Beginner Contest 391 解法メモ【Ruby】

勉強会で解説するためのメモ。

A - Lucky Direction

8方位を文字列で与えられるので、反対側の方角を出力する問題。

8個しかないので全て列挙して反対の方角を出力するコードで解けるが、NE, NW, SE, SWの4つについては南北が先、東西が後に来るのでシンプルにNとS、EとWを置換した文字列を出力すれば良い。

自分の回答

s = gets.chomp
d = {
  "N" => "S",
  "S" => "N",
  "E" => "W",
  "W" => "E",
}
puts s.each_char.map {|c| d[c]}.join("")

解説を読んでの追記

ユーザー解説でPythonのstr.translate()が紹介されていたので調べてみたところ、RubyにもString#trがあったのでそちらのコードも記載する。

puts gets.chomp.tr("NSEW", "SNWE")

B - Seek Grid

グリッドSの中に1つだけ含まれるグリッドTの位置を求める問題。

シンプルに解くと、Sの全て($ N^2 $個)のマスに対してTの左上のマスと重ねた時に、Tの全て($ M^2 $個)のマスがSの対応する位置のマスと一致するか、を確認することになる。
制約に$ 1 \le M \le N \le 50 $とあるので、$ N^4 = 50^4 = 6.25 * 10^6 $よりシンプルに解いても間に合う。(実際はTがSからはみ出るマスの選択方法もあるので$ O((N-M)^2M^2) $程度で済む)

自分の回答

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

# Sの全ての点
n.times do |i|
  n.times do |j|
    flag = true

    # Tの全ての点
    m.times do |ii|
      break flag = false if narr[i + ii].nil?

      m.times do |jj|
        next if narr[i + ii][j + jj] == marr[ii][jj]
        
        flag = false
        break
      end
      next if flag
      
      break
    end

    if flag
      puts [i + 1, j + 1].join(" ")
      exit
    end
  end
end

C - Pigeonhole Query

$ N $羽の鳩が$ N $個の箱に1匹ずつ入っていて、鳩を移動させながら定期的に複数匹の鳩がいる箱の数を求める問題。

鳩がどの箱にいるか、あるいは、箱にどの鳩がいるか、のどちらか一方でデータを管理してしまうと、前者は複数の鳩が入っている箱を、後者は鳩を移動させる時に特定の鳩が入っている箱を探すのに検索が必要になってしまうため、クエリごとに検索を行っているとTLEしてしまう。

求めたいのは2匹以上鳩がいる箱の数のみであるため、2匹以上鳩がいる箱の数を用意しておいて鳩が移動するたびに増減して、個数を出力する時にそのまま出力してあげれば良い。

2匹以上鳩がいる箱の数が増減するのは、

• 1匹いる箱に新たに鳩が移動してきた時
• 2匹いる箱から鳩が出ていく時

の2ケースのみであるため、鳩iがいる箱の番号と箱iにいる鳩の数を用意して、移動する時に2匹以上鳩がいる箱の数が増減するかを確認しながら更新してあげれば$ O(Q) $で解ける。

自分の回答

※箱にいる鳩の数をHashで持っているがキーが1~NなのでArrayで持つのと変わらない。

n, q = gets.split.map(&:to_i)
arr = [] # 鳩がいる箱
hash = {} # 箱にいる鳩の数
(1..n).each do |i|
  arr[i] = i
  hash[i] = 1
end

c = 0
q.times do
  x, i, h = gets.split.map(&:to_i)
  if x == 1
    hash[arr[i]] -= 1
    c -= 1 if hash[arr[i]] == 1 # 移動元の箱が2匹から1匹に減少
    arr[i] = h
    hash[h] += 1
    c += 1 if hash[h] == 2 # 移動先の箱が1匹から2匹に増加
  else
    puts c
  end
end

D - Gravity

1時刻単位(以下秒とする)ごとに、一番下の行が埋まってたら消す→全てのブロックを一つ下に移動する、を繰り返していくグリットで、$ T_i $秒後にブロック$ A_i $が消えているかどうかを判定する問題。

問題文の状況をそのままトレースして計算すると膨大な時間がかかるので改善策を考える。
今回の問題ではブロック$ A_i $が何秒後に消えるかを事前計算できれば$ Q $個の質問に対して時間内に求めることができる。

ブロックが消える条件は一番下の行が全てブロックで埋まっている時のみで、下から2行目が一時的に全てブロックで埋まっても消えない。つまり、最初に消えるブロックは各列において一番下にあるブロックで、二番目に消えるブロックは各列の下から二番目にあるブロックとなる。
各列の下からi番目のブロックが全て一番下まできた時にようやく消えるので、同時に消えるブロックのうち一番高いところにあるブロックが一番下まで来るのにかかる時間¹が下からi番目のブロックが消える時間となる。

あとは各列ごとに列に配置されているブロックの高さのリストを作成してソートしてあげれば、下から何番目にいるかがわかるので各行ごとに最大値を求めてあげれば各ブロックが何秒後に消えるかが判明する。

自分の回答

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

warr = []
w.times { warr << [] } # 各列に配置されたブロックのリストの初期化
n.times do |i|
  x, y = gets.split.map(&:to_i)
  warr[x - 1] << [y, i] # 列に配置されたブロックの高さと、それが何番目のブロックなのかを格納
end

w.times do |i|
  warr[i] = warr[i].sort
end

line = 0
ar = []
arr = []
while !warr[0][line].nil?
  max = 0
  w.times do |j| # line行目のブロックが全て存在するか、存在するならその最大値を求める
    c, i = warr[j][line]
    if c.nil?
      max = nil
      break
    end
    max = [c, max].max
    arr[i] = line # ブロックiが消える行数
  end

  if max.nil? # ブロックの存在しない列がある場合は以降ブロックが消えることがないので終了する
    break
  end
  ar[line] = max # line行目が消える時刻
  line += 1
end

gets.to_i.times do
  t, a = gets.split.map(&:to_i)
  # ブロックが消えない or 消える時刻よりも前の時刻ならYesを返す
  #   arr[a - 1].nil? => 消えないブロック
  #   ar[arr[a - 1]].nil? => 処理中にブロックがない列があることが判明した行のブロック
  if arr[a - 1].nil? || (ar[arr[a - 1]] || t + 1) > t
    puts "Yes"
  else
    puts "No"
  end
end

E - Hierarchical Majority Vote

$ 3^N $bitの数値を$ 3 $bit毎の集約処理を$ N $回繰り返していき$ 1 $bitに集約する。
この時、与えられた数値を操作して集約結果のbitを反転させるために必要なbit操作の最小値を求める問題。

例として $ 001|011|111 $と$ 011|111|111 $を考える。これら数値に対して集約処理をかけると以下のようにどちらも$ 1 $になる。

\displaylines{
001|011|111 → 011 → 1 \\
011|111|111 → 111 → 1 
}

$ 001|011|111 $を$ 0 $とするには、一度集約した$ 011 $を$ 001 $,$ 010 $のいずれかにすればよい。($ 100, 000 $はともに後ろの$ 11 $を操作しているので必要以上の操作になる)
$ 001 $にする場合は元のbit列の$ 011 $が$ 0 $になるようにすればいいので、1のbitのどちらか片方のbitを反転すれば良い。$ 010 $にする場合は$ 111 $から2つのbitを反転させる必要がある。
よって$ 001 $にするケースであれば1bitの反転で済むので$ 1 $答えとなる。

同様に$ 011|111|111 $について考えてみると、一度集約すると$ 111 $となるため、どれか2つのbitを反転させる必要がある。元のbit列に対して反転させるのに必要なbit数は$ 1|2|2 $となるため、最小にするには$ 3 $bitになる。

同様に$ 1 $から$ 0 $にするにの必要な操作回数も求められるので、操作しない場合のbitと合わせて、1にする時の操作数と0にする時の操作数を管理し累積していくことで最終的な最小操作回数を求めることができる。

自分の回答

0にする操作回数と1にする操作回数を管理するのが面倒だったので0にする操作回数を負数にすることで一元管理できるようにしています。

n = gets.to_i
s = gets.chomp
arr = s.each_char.map {|c| c == "0" ? -1 : 1 }

while arr.length > 1
  ar = []
  arr.each_slice(3) do |slice|
    a, b, c = slice.sort
    if a > 0 # 111: 操作回数の小さい2つの和
      ar << a + b
    elsif c < 0 # 000: 操作回数の小さい2つの和(負数なので大きい2つ)
      ar << b + c
    else # 011 101, 110, 001, 010, 100: 0に近い方のbitを操作数
      ar << b 
    end
  end
  arr = ar
end
puts arr[0].abs

1. 消えるのは揃った時の次のタイミングより+1秒されることに注意。 ↩