【AtCoder:10回目】AtCoder Beginner Contest 133の振り返り（Ruby）

【目次】

【本題】

振り返り

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

AtCoder Beginner Contest 133 - AtCoder

今回は１問しか回答できませんでした・・・

数学要素の強い問題だと全く歯が立たないです・・・

A - T or T

問題文 私たちは N 人で旅行しようとしており、その交通手段として電車とタクシーがあります。

電車を使うと 1 人あたり A 円かかります。

タクシーを使うと N 人で B 円かかります。

全員の交通費の合計は最小でいくらになるでしょうか。

制約 入力は全て整数である。 1 ≤ N ≤ 20 1 ≤ A ≤ 50 1 ≤ B ≤ 50

私の回答はこちら。

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

if n*a < b
  puts n*a
else
  puts b
end

両方を配列に格納してminメソッドを利用した方が、よりシンプルです。

n,a,b=gets.split.map(&:to_i)
puts [n*a,b].min

B - Good Distance

問題文 D 次元空間上に N 個の点があります。

i 番目の点の座標は ( X i 1 , X i 2 , . . . , X i D ) です。

座標 ( y 1 , y 2 , . . . , y D ) の点と座標 ( z 1 , z 2 , . . . , z D ) の点の距離は √ ( y 1 − z 1 ) 2 + ( y 2 − z 2 ) 2 + . . . + ( y D − z D ) 2 です。

i 番目の点と j 番目の点の距離が整数となるような組 ( i , j )

( i < j ) はいくつあるでしょうか。

制約 入力は全て整数である。 2 ≤ N ≤ 10 1 ≤ D ≤ 10 − 20 ≤ X i j ≤ 20 同じ座標の点は与えられない。すなわち、 i ≠ j ならば X i k ≠ X j k なる k が存在する。

模擬回答がこちら。

N, D = gets.split.map(&:to_i)
XS = N.times.map { gets.split.map(&:to_i) }
 
ans = 0
XS.combination(2) do |xs1, xs2|
  sum = 0
  D.times do |i|
    sum += (xs1[i] - xs2[i])**2
  end
 
  sq = Math.sqrt(sum)
  ans += 1 if sq == sq.to_i
end
 
puts ans

combinationメソッドってのを初めて知った。これは便利そう・・・

https://ref.xaio.jp/ruby/classes/array/combination

C - Remainder Minimization 2019

問題文 非負整数 L , R が与えられます。 2 つの整数 i , j を L ≤ i < j ≤ R を満たすように選びます。 ( i × j ) mod 2019 の最小値を求めてください。

制約 入力は全て整数 0 ≤ L < R ≤ 2 × 10 9

色々もがいた結果、最後まで通らなかったコードがこちら。

l,r=gets.split.map(&:to_i)

if l/2019 != r/2019 || (l.lcm(r) >=l && l.lcm(r) <= r)
  puts 0
elsif 1+l/2019-l/2019.to_f < r/2019.to_f-r/2019
  puts r*(r-1)%2019
else
  puts l*(l+1)%2019
end

模擬回答がこちら。

L, R = gets.split.map(&:to_i)
 
ans = 2019
 
L.upto(R-1) do |i|
  (i+1).upto(R) do |j|
    mod = (i * j) % 2019
    if mod == 0
      puts 0
      exit
    end
 
    ans = mod if mod < ans
  end
end
 
puts ans

全探索で出来るんですね・・・