A – Five Antennas
問題
解法
「直接 通信ができないアンテナの組が存在するかどうか」は距離が最も離れているアンテナの組の距離がk以下であれば存在しないと言えます。
よって、最も距離が離れるaとeの距離を比較すればよいです。
実装
a=[]
5.times do
a << gets.to_i
end
k=gets.to_i
puts a[4]-a[0]<=k ? "Yay!" : ":("
B – Five Dishes
問題
解法
各料理が10の倍数の時刻にしか注文できないということは、ある料理の調理時間がA分だとすると、次の料理を注文できるまでの時間は、「A以上の10の倍数」となります。
次に「最後の料理が届く最も早く」するには、最後の料理をどの料理にするかがポイントです。
調理時間が10で割り切れない料理が存在する場合、10で割った余りが最小の料理を最後に注文すれば、全体の時間が最短になります。
実装
ans=0 min=10 5.times do a=gets.to_i ans += (a+9)/10*10 min = a%10 if a%10!=0 && min > a%10 end if min==10 puts ans else puts ans - 10 + min end
C – Five Transportations
問題
解法
最も運べる人数が少ない交通機関がボトルネックになるので、全ての交通機関の運べる人数を最少のものにそろえても結果は同じになります。
実装
N=gets.to_i
a=[]
5.times{ a << gets.to_i}
a.sort!
puts (N-1)/a[0]+5
D – Cake 123
問題
解法
全てのケーキの組み合わせを求めてから上位K個を求めると、組み合わせが109となり間に合いません。
そこで次のような工夫をします。
- 上位K個に入るものは、各キャンドルのケーキのうち美味しさが上位K個以内に入っているものの組み合わせに必ずなる
- 「1のキャンドルの上位K個」と「2のキャンドルの上位K個」の組み合わせを全て求めてそのうち上位K個と「3のキャンドルの上位K個」の組み合わせを求めてから上位K個を求める
このようにすれば、組み合わせはK2のオーダーに抑えることが出来るので十分間に合います。
実装
X,Y,Z,K=gets.chomp.split.map(&:to_i)
a=gets.chomp.split.map(&:to_i)
b=gets.chomp.split.map(&:to_i)
c=gets.chomp.split.map(&:to_i)
ab = []
a.each_with_index do |m, i|
next if i >= K
b.each_with_index do |n, j|
next if j >= K
ab << m+n
end
end
ab.sort!.reverse!
abc = []
ab.each_with_index do |m, i|
next if i >= K
c.each_with_index do |n, j|
next if j >= K
abc << m+n
end
end
abc.sort!.reverse!
0.upto(K-1) do |i|
puts abc[i]
end
コメント