配列の距離の和の最小値を求める問題。
CHALLENGE DESCRIPTION:
Alice is looking for a sorority to join for her first year at Acme University. There is a street consisting entirely of sorority houses near the university, and some of her high school friends have already joined sorority houses on the street. (More than one of her friends may live at the same sorority house.)
Alice wants to visit her friends frequently, and needs a program that will help her pick an optimal house to visit them from. Each sorority house has a street number that indicates its location on the street. The optimal location will minimize the sum of differences between the number of Alice’s house and the number of her friends' houses.
For example: Alice’s friends live at houses 3, 3, 5, and 7. Alice moves in at house 4. Then the distances to her friends' houses are 1, 1, 1, and 3, totaling 6.
INPUT SAMPLE:
The input consists of several integers on a line, separated by spaces. The first integer F contains the number of friends (0 < F < 100). Then F street addresses A follow (0 < A < 10000).
4 3 3 5 7 3 20 30 40
OUTPUT SAMPLE:
6 20
CONSTRAINTS:
- Number of friends: 0 < F < 100
- Street addresses: 0 < A < 10000
- Number of test cases is 10.
My Code
#!/usr/bin/env ruby -w def minimum_distance(addresses) distances = [] addresses.each do |address| distances << addresses.inject(0) { |sum, a| sum += (a - address).abs } end distances.min end ARGF.each_line do |line| numbers = line.chomp.split.map(&:to_i) _firends_number = numbers.first addresses = numbers[1..-1] puts minimum_distance(addresses) end
別解
distances の数が大量だと遅くなる。
テストデータに5000個ぐらい突っ込んで、以下のように書いて比較して見たところ、
下記の方が早かった。データの個数が少ない場合は、ほぼ同じ。
def minimum_distance(addresses) min_distance = nil addresses.each do |address| distance = addresses.inject(0) { |sum, a| sum += (a - address).abs } min_distance ||= distance min_distance = [min_distance, distance].min end min_distance end
余談だけど、Benchmark#compare! ってすごい便利。何倍遅いかも表示してくれる。知らなかった。
Warming up -------------------------------------- minimum_distance 1.000 i/100ms minimum_distance2 246.156k i/100ms Calculating ------------------------------------- minimum_distance 999.161k (± 2.5%) i/s - 2.895M minimum_distance2 8.381M (± 9.0%) i/s - 41.600M in 5.006365s Comparison: minimum_distance2: 8381223.1 i/s minimum_distance: 999161.5 i/s - 8.39x slower
require "benchmark/ips" def minimum_distance(addresses) distances = [] addresses.each do |address| distances << addresses.inject(0) { |sum, a| sum += (a - address).abs } end distances.min end def minimum_distance2(addresses) min_distance = nil addresses.each do |address| distance = addresses.inject(0) { |sum, a| sum += (a - address).abs } min_distance ||= distance min_distance = [min_distance, distance].min end min_distance end Benchmark.ips do |x| x.report("minimum_distance") do ARGF.each_line do |line| numbers = line.chomp.split.map(&:to_i) _firends_number = numbers.first addresses = numbers[1..-1] minimum_distance(addresses) end end x.report("minimum_distance2") do ARGF.each_line do |line| numbers = line.chomp.split.map(&:to_i) _firends_number = numbers.first addresses = numbers[1..-1] minimum_distance2(addresses) end end x.compare! end