【Ruby】ABC202 こと エイシングプログラミングコンテスト2021の参加記(E問題まで)

AtCoderABC202 こと エイシングプログラミングコンテスト2021に参加しました。

本番はD問題まで解けて、本記事ではE問題まで書いています。

A - Three Dice

サイコロの問題。

a = gets.to_s.split.map{ |e| e.to_i }
puts 21 - a.sum

いつものように入力はCrystalにすぐ変換できるように、to_sをつけたり、map{ |e| e.to_i }と書いている。

3個じゃなくて任意の複数個に対応できるようにするには次のようにする。

a = gets.to_s.split.map{ |e| e.to_i }
puts 7 * a.size - a.sum

1分以内で解けたかなと思ったが、1分18秒だった。

B - 180°

問題文を誤読するも、サンプルをちゃんと確かめて、reverseの必要性に気がつく。

s = gets.to_s.chomp
puts s.tr('69', '96').reverse

競プロでは文字列を文字や数値の配列に変換した方が速いことが多いが、
この問題はシンプルで制約もキツくないので、あまり難しいことを考えずにすむ。
方針としては、6と9だけ、操作すると反転して入れ替わる。
1文字の置換(swap)は、trメソッドが便利なことが多い。
また、Rustは文字列の反転はないらしいが、Rubyは競プロ的に便利なことにある。

B問題の最短コードを見たが、yuruhiyaさんやkotatsugameさんのbashのコードが最短だった。

 tr 69 96|rev

自分のRubyコードに似ている。 bashzshのコマンドやスクリプトで、ちょっとしたことでいつか使えるかもしれない。

ここまでで、2m44s。悪くはない。

C - Made Up

少し悩んだ。AとBCが独立で、それぞれ同じ種類となるペアを求める。
制約的に二重ループを回せばTLEになる。 コンテストの時のことはちゃんと覚えてないが、それぞれの同じ数になるものの個数を求めておいて、かけ合わせれば良さそう。
数を数えるときはtallyメソッドが便利。

n = gets.to_s.to_i
a = gets.to_s.split.map{ |e| e.to_i }
b = gets.to_s.split.map{ |e| e.to_i }
c = gets.to_s.split.map{ |e| e.to_i - 1 }

t1 = a.tally
t2 = c.map{ |j| b[j] }.tally

ans = 0
(1..n).each do |k|
  ans += (t1[k] || 0) * (t2[k] || 0)
end

puts ans

なお、他の人の解答を見てると、片方のみをtallyメソッドで数えて、もう片方はeachで回して合計をしている方が多そうだった。

ここまでで、7m51s。特別悪いというわけではないが、速い方はもっと速いので、速くしたい。

D - aab aba baa

問題文を読んで、ABC161のD - Lunlun Numberを思い出して調べる。
しかし、Lunlun Numberは、K≦100,000のK番目を求める問題で、Kの制約が小さく順番に下から数え上げられるが、
この問題は制約が大きくて、下から順番に数え上げていくことはできない。

なんとなくこういう問題は、左から決めていく。

使える文字がaかbか片方のみだったら、1種類しか作れないので、それを答える。
なお、最初から使える文字が片方だったら、1種類しか作れないので、1番目を聞かれるはず。

最初に使える文字が、aもbも両方の可能性があるとする。二択である。aとすると、残りのパターンは、二項係数(a - 1 + b)C (a - 1)となる。もし、この場合の数がちょうどkだった場合は、 aを最初にもってきた上、次にbを全て優先させた並びが答えとなる。もし、この(a - 1 + b)C (a - 1)がk以上であれば、最初にaを持ってくるパターンの中に答えがあることになるので、aの可能性を1減らした上で、次の文字を考える。同様に、この(a - 1 + b)C (a - 1)がk未満であれば、aのパターンの中に答えはないので、bから始まるパターンが答えとなり、bを答えに保存した上で、bの残数を1減らす。

class Integer
  def nCk(k)
    n = self
    return 0 if k < 0 || n < k
  
    ret = 1/1r
    k = [k, n - k].min
    k.times do
      ret = ret * n / k
      n -= 1
      k -= 1
    end
    ret.to_i
  end
end

a, b, k = gets.to_s.split.map{ |e| e.to_i }

ans = ""
(a + b).times do |i|
  if a == 0 || b == 0
    puts ans + 'a' * a + 'b' * b
    exit
  end
  
  t = (a - 1 + b).nCk(a - 1)
  if t == k
    puts ans + 'a' + 'b' *  b + 'a' * (a - 1)
    exit
  elsif t > k
    ans << 'a'
    a -= 1
  else
    ans << 'b'
    b -= 1
    k -= t
  end
end

puts ans + 'a' * a + 'b' * b

この問題は、二項係数の選ぶ数が30以下にしかならないので、愚直に計算して答えを求める。
Ruby多倍長整数が使えるし、この程度であれば工夫は不要。

ここまでで29m12s。ちょっと時間がかかりすぎてしまった。

E - Count Descendants

考えても解けなかった。悔しい。この気持ちを大切にしたい。 木グラフ(Treeグラフ)で、DFSでオイラーツアーを使う問題。 他にも色々とやり方があるようだが。 行きがけ・帰りがけで記録したらできそうと思ったが、帰りの経路を覚えておく方法がわからなかった。
勉強不足でオイラーツアーという言葉もでてこなかった。

qib-sanのコードが、公式解説と同じやり方のようで、とても参考になった。
以下は、qib-sanのコードを自分風に書き換えたもの。

n = gets.to_s.to_i
parents = gets.chomp.split.map {|v| v.to_i - 1 }
g = Array.new(n) { [] }
parents.each.with_index(1){ |parent, child| g[parent] << child }
 
src = 0
st = [~ src, src]
depthes = Array.new(n) { [] }
dist = Array.new(n, -1)
dist[src] = 0
t_in = Array.new(n)
t_out = Array.new(n)
t = 0
while (cur = st.pop)
  if cur >= 0
    t_in[cur] = t
    depthes[dist[cur]] << t_in[cur]
    g[cur].each do |v|
      next if dist[v] >= 0
      dist[v] = dist[cur] + 1
      st << ~ v
      st << v
    end
  else
    t_out[~ cur] = t
  end
  t += 1
end
 
# p depthes  # [[0], [1, 3], [4, 6, 8], [9], [], [], []]
# p t_in     # [0, 3, 1, 8, 6, 9, 4]
# p t_out    # [13, 12, 2, 11, 7, 10, 5]
# depthes[2] # [4, 6, 8]
# p depthes[2].bsearch_index {|t| t >= t_in[0] }  # 0    -> m - 0 => 3
# p depthes[2].bsearch_index {|t| t >= t_out[0] } # nil  -> m - m => 0
 
q = gets.to_s.to_i
q.times do
  u, d = gets.to_s.chomp.split.map(&:to_i)
  u -= 1
  m = depthes[d].size
  ub = depthes[d].bsearch_index {|t| t >= t_in[u] } || m
  lb = depthes[d].bsearch_index {|t| t >= t_out[u] } || m
  puts lb - ub
end

帰りの経路を調べるためには、「帰りの頂点はここを調べるよ」とスタックに入れてあげる必要がある。
ここで、行きの経路として調べるために、行きは非負整数だったが、帰りは負数に対応させてあげる。
1対1対応で非負整数を負数に対応させるときは、~を使うと反転できていいらしい。
単に-でマイナスをすると、-0は0なので0と区別がつかない。

p [*0..3].map{ |e| -e } #=> [0, -1, -2, -3]
p [*0..3].map{ |e| ~e } #=> [-1, -2, -3, -4]

詳しい解法については公式解説を読むとよさそうです。