Rubyで解くAtCoder ABC 194 (B,C問題のみ)

9652 ワード
競技プログラミング Ruby AtCoder AtCoderBeginnerContest Ruby テキストリンク

B - Job Assignment

こう考えました

従業員に0から番号を割り振って，仕事A,B(変数名は1,2でつけてしまったけど・・・)の時間を従業員番号をキーとしたハッシュに入れる。
それぞれで早くできる順に2名を選抜。

もし，それぞれのトップが別々の従業員の場合
→２つの時間のうち，大きいものを出力。

それぞれトップが同じ従業員の場合
→どちらか片方を2番目の従業員にした場合の時間，トップが両方やる時間のうち，小さいものを出力。

提出コード

もっと簡単に出せる手法はありそうだけど・・・

ABC194_B.rb
N = gets.to_i
t_1 = {}
t_2 = {}

N.times do |i|
  w_1, w_2 = gets.split.map(&:to_i)
  t_1.store(i, w_1)
  t_2.store(i, w_2)
end

rank_1 = t_1.min(2){|x, y| x[1] <=> y[1]}
rank_2 = t_2.min(2){|x, y| x[1] <=> y[1]}

first_1, second_1 = rank_1[0], rank_1[1]
first_2, second_2 = rank_2[0], rank_2[1]

if first_1[0] != first_2[0]
  puts [first_1[1], first_2[1]].max
else
  puts [[first_1[1], second_2[1]].max , [second_1[1], first_2[1]].max , first_1[1] + first_2[1]].min
end

C - Squared Error

愚直にやったらTLE・・・

全部の組み合わせを配列にして，それぞれで計算した和を計算すれば・・・
（ちょうど教えてもらったsumにブロックを与える形が使える！）
→TLEでした。計算回数を減らさなきゃいけない・・・

ABC194_C.rb
gets
num = gets.split.map(&:to_i)
puts num.combination(2).to_a.sum {|i,j| (i-j)*(i-j) }

解説を少し見た

数列の長さはかなり大きいけど，与えられる数値は -200〜200 なので，数値ごとの個数を配列にすればいい！
（ちょうど教えてもらったtallyが使える！）

ハッシュにまとめてからkeyもvalueも別々に配列化し，あとは全部の組み合わせについて計算しました。
（係数としてそれぞれの数の個数をかければいいので，計算回数が大幅に減りました）

提出コード

ABC194_C.rb
gets
arr = gets.split.map(&:to_i)
hash = arr.tally

num = hash.keys
cnt = hash.values
n = num.size
sum = 0

(1..n-1).each do |i|
  (0..i).each do |j|
    sum += (num[i] - num[j]) * (num[i] - num[j]) * cnt[i] * cnt[j]
  end
end

puts sum
c++マトリクス乗算とブロックマトリクス乗算を実現
JAvaのIO入出力ストリームと異常処理