【AtCoder:5回目】AtCoder Beginner Contest 129の振り返り（Ruby）

【目次】

【本題】

振り返り

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

今回も２問しか回答できませんでした・・・

やはり何も練習しない状態のままだと全く太刀打ち出来ないですね・・・

A - Airplane

問題文 空港 A, B, C があり、それぞれの空港の間では、双方向に飛行機が運航しています。

空港 A, B 間の飛行時間は片道 P 時間、空港 B, C 間の飛行時間は片道 Q 時間、空港 C, A 間の飛行時間は片道 R 時間です。

いずれかの空港からスタートして他の空港に飛行機で移動し、さらにそのどちらでもない空港に飛行機で移動するような経路を考えます。

飛行時間の和は最短で何時間になるでしょうか。

経路のパターンは６通り存在しますが、向きが逆なだけのパターンが半分なので、飛行距離のパターンは３通りです。

そして飛行距離については、全ての合計から選択していない経路の距離を引けば導き出せます。

つまり、選択しなかった経路が最長の場合、最短の経路となると考えて、下記の様に実装しました。

p,q,r = gets.split(" ").map &:to_i
puts (p+q+r) - [p,q,r].max

他にも面白い方法がありました。

P, Q, R = gets.split(" ").map(&:to_i)
 
a = [P, Q, R]
a.sort!
puts a[0] + a[1]

これは各経路の距離を昇順で並べ替えて、小さい順に２つ合計するという方法です。

B - Balance

問題文 1 から N の番号がついた N 個の重りがあり、番号 i の重りの重さは W i です。

ある整数 1 ≤ T < N に対してこれらの重りを、番号が T 以下の重り と 番号が T より大きい重りの 2 グループに分けることを考え、それぞれのグループの重さの和を S 1 , S 2 とします。

このような分け方全てを考えた時、 S 1 と S 2 の差の絶対値の最小値を求めてください。

差の絶対値の理論上の最小値は０です。

そして０になるのは、二つの重りが両方とも合計値の半分になった時です。

なので、合計値の半分を超えるまで重りを足していき、超えた時点と超える直前の重りの合計の差を比較して、より小さい方を選択する方法で実装しました。

n = gets.to_i

w = []
while w1 = $stdin.gets do
  w << w1.chomp.split(" ")
end

sum = 0
w[0].each{|i| sum += i.to_i }

half_over = 0
index = 0
while half_over < sum/2
  half_over += w[0][index].to_i
  index += 1
end

half_less = half_over - w[0][index-1].to_i

if half_over - (sum - half_over)  > (sum - half_less) - half_less
  puts (sum - half_less) - half_less
else
  puts half_over - (sum - half_over)
end

よりコード量が少なくなる実装方法もありました。

n = gets.to_i
ary = gets.split.map(&:to_i)
 
sum1 = 0
sum2 = ary.inject(:+)
ans = 10000000
 
n.times do |i|
  sum1 += ary[i]
  sum2 -= ary[i]
  ans = [ans, (sum1 - sum2).abs].min
end
 
puts ans

こちらは全パターンで差の絶対値を求めて、最小値だった場合に「ans」へ格納する方法です。