【AtCoder:5回目】AtCoder Beginner Contest 129の振り返り(Ruby)

f:id:ryoutaku_jo:20190610004222p:plain

【目次】

【本題】

振り返り

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

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

f:id:ryoutaku_jo:20190610110117p:plain

f:id:ryoutaku_jo:20190610110131p:plain

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

A - Airplane

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

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

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

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

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

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

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

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]

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

B - Balance

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

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

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

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

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

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

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」へ格納する方法です。

《今日の学習進捗(3年以内に10000時間に向けて)》

機械学習やりたい欲が高まって来たので、学習計画を検討中。

学習開始からの期間 :184日
今日までの合計時間:1775h
一日あたりの平均学習時間:9.7h
今日までに到達すべき目標時間:1680h
目標との解離:95h
「10,000時間」まで、

残り・・・「8225時間!」