【Ruby】ABC202 こと エイシングプログラミングコンテスト2021の参加記(E問題まで)
AtCoderのABC202 こと エイシングプログラミングコンテスト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コードに似ている。 bashやzshのコマンドやスクリプトで、ちょっとしたことでいつか使えるかもしれない。
ここまでで、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]
詳しい解法については公式解説を読むとよさそうです。