paiza オンラインハッカソン vol.1 をやってみた

前回のエントリでやったのがおもしろかったので、最初からやってみた。いつもながら Ruby です。
　
結果。

まあ悪くないのだけれど…。

いや、これは苦しみました。最初はソートしてバイナリサーチというアルゴリズムを考えていたのだけれど、バグに悩まされて挫折。もうこの方法は自分の力ではできないと諦めて、バケットソートの応用で解く攻め方に替えました。なんとかそれが上手くいったという次第。実行時間はまあまあというところらしい。コードは全然複雑でないですよね。でも、富豪プログラミング…。配列の大きさが 100万くらいなので、まあ許されるかなあ…。

コード。

n, d = gets.split.map(&:to_i)
price, target = [], []
n.times {price  << gets.to_i}
d.times {target << gets.to_i}

field = Array.new(100_0001, 0)
price.each_with_index do |x, i|
  if field[x].zero?
    field[x] = i
  elsif field[x] > 0
    field[x] = -1
  end
end

target.each do |t|
  min = Float::INFINITY
  price.size.times do |i|
    a = t - price[i]
    co = 0
    loop do
      break if co >= min
      if not field[a - co].zero? and i != field[a - co]
        min = co if min > co
        break
      else
        co += 1
        break if a - co < 0
      end
    end
    break if min.zero?    #高速化のためにあとで加えた（追記参照）
  end
  min = t if min == Float::INFINITY
  puts t - min
end

同じ値段の別商品があるというのが面倒ですよね。それなのに、同じ商品を二つ買ってはいけないという。

あ、これ、課題は通ったけれども、おかしいところがありますね。if文のところは

      if (field[a - co] > 0 and i != field[a - co]) or field[a - co] < 0

であるべきしょうね。たまたま誤った答えが出る条件ではなかったのだな。

※追記
ふと思いついて 1行付け加えたら、だいぶ高速化しました。こちらが以前で、こちらが 1行加えたあとの結果です。