【AtCoder:15回目】AtCoder Beginner Contest 138の振り返り（Ruby）

【目次】

【本題】

振り返り

今回は 8/18(日)に開催されたAtCoder Beginner Contest 138の振り返りを行います。

AtCoder Beginner Contest 138 - AtCoder

今回は３問回答出来ました

レーティング微増

A - Red or Not

問題文 整数 a と、英小文字からなる文字列 s が入力されます。

a が 3200 以上なら s と出力し、 a が 3200 未満なら red と出力するプログラムを書いてください。

制約 2800 ≤ a < 5000 s は長さ 1 以上 10 以下の文字列である。 s の各文字は英小文字である。

条件が3200以上と未満の二つだけなので、三項演算子で簡単に出力を切り替えられますね。

作成したコードがこちらです。

a = gets.to_i
s = gets.chomp
puts a >= 3200 ? s : 'red'

以下の様にワンライナーで記述することも出来ますね。

puts (gets.to_i >= 3200 ? gets : 'red')

B - Resistors in Parallel

問題文 N 個の整数の列 A 1 , … , A N が与えられます。

これらの逆数の総和の逆数 1 1 A 1 + … + 1 A N を求めてください。

制約 1 ≤ N ≤ 100 1 ≤ A i ≤ 1000

この制約なら全探索で行けそうなので、以下の様にコードを作成しました。

n = gets.to_i
nums = gets.split(' ').map(&:to_i)

reverse_sum = 0
nums.each do |num|
  reverse_sum += 1.0 / num
end

puts (1 / reverse_sum)

以下の様にワンライナーで記述することも出来ますね。

gets
p 1/(gets.split.map(&:to_i).map{|i|1.0/i}.inject(&:+))

C - Alchemist

問題文 あなたは鍋と N 個の具材を持っています。各具材は 価値 と呼ばれる実数の値を持ち、 i 個目 ( 1 ≤ i ≤ N ) の具材の価値は v i です。

2 個の具材を鍋に入れると、それらは消滅して新たに 1 個の具材が生成されます。この新たな具材の価値は元の 2 個の具材の価値を x , y として ( x + y ) / 2 であり、この具材を再び鍋に入れることもできます。

この具材の合成を N − 1 回行うと、最後に 1 個の具材が残ります。この具材の価値として考えられる最大の値を求めてください。

制約 2 ≤ N ≤ 50 1 ≤ v i ≤ 1000 入力中の値はすべて整数である。

具材を足して２で割るという事は、

最大値のパターンを求める問題ですが、２で割る操作を多く行った値は、２で割る操作を行った回数が少ない値より、当然小さくなって行きます。

なので、小さな値から順に合成して行くのが、価値が最大になるパターンです。

これも全探索で行けそうなので、以下の様にコードを作成しました。

n = gets.to_i
vs = gets.split(' ').map(&:to_i)

vs.sort!
mixed_v = vs.shift

vs.each do |v|
  mixed_v = (mixed_v + v) / 2.0
end

puts mixed_v

これもワンライナーで行けますね。

gets
p gets.split.map(&:to_f).sort!.inject{|x,i| (x+i)/2}

D - Ki

問題文 1 から N までの番号がついた N 個の頂点を持つ根付き木が与えられます。 この木の根は頂点 1 で、 i 番目の辺 ( 1 ≤ i ≤ N − 1 ) は頂点 a i と頂点 b i を結びます。

各頂点にはカウンターが設置されており、はじめすべての頂点のカウンターの値は 0 です。

これから、以下のような Q 回の操作が行われます。

操作 j

( 1 ≤ j ≤ Q ) : 頂点 p j を根とする部分木に含まれるすべての頂点のカウンターの値に x j を足す。 すべての操作のあとの各頂点のカウンターの値を求めてください。

制約 2 ≤ N ≤ 2 × 10 5 1 ≤ Q ≤ 2 × 10 5 1 ≤ a i < b i ≤ N 1 ≤ p j ≤ N 1 ≤ x j ≤ 10 4 与えられるグラフは木である。 入力中の値はすべて整数である。

これも全探索でカウンターを回して行こうと考えましたが、途中で時間切れになってしまいました。

途中まで作成したコードはこちらです。

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

ab = []
(n-1).times { ab << gets.split.map(&:to_i) }

px= []
q.times { px << gets.split.map(&:to_i) }

result = []
n.times { result << 0 }

group =  ab.group_by { |i| i[0] }

px.each do |x, y|
  group[x]&.each do |g|
    result[g[1]-1] += y
  end
  result[x-1] += y
end

p result

但しこれだと、直接の結びつきがある頂点のカウンターしか値を足すことが出来ません。

そもそも制約的に全探索で出来る内容ではありませんでした・・・

こちらが模範解答です。

n, q = gets.split.map(&:to_i)
 
tree = Array.new
1.upto(n-1) do |i|
  ai, bi = gets.split.map(&:to_i)
  tree[bi] = ai
end
 
points = Array.new(n + 1, 0)
1.upto(q) do |i|
  pi, xi = gets.split.map(&:to_i)
  points[pi] += xi
end
 
2.upto(n) do |node_n|
  points[node_n] += points[tree[node_n]]
end
 
points.shift
puts "#{points.join(" ")}\n"