paiza POH ec-campaign (Python/Ruby) (not tuned well)

問題	https://paiza.jp/poh/ec-campaign
タイム一覧/C++	http://qiita.com/cielavenir/items/a61cfe8390eb16866ae5
Python/Ruby(1)	http://qiita.com/cielavenir/items/b10ff4d201150f525062
C#/Java/Python/Ruby	http://qiita.com/cielavenir/items/d89e85f069cf570e6786
Perl/PHP	http://qiita.com/cielavenir/items/1a650a4c41d7bdd31392
JavaScript	http://qiita.com/cielavenir/items/a85b985888fdc15c52b7
Go/CoffeeScript/Scala/R/Bash	http://qiita.com/cielavenir/items/79016a0afd30470f440d
VB/F#/D	http://qiita.com/cielavenir/items/cb6094bab56253de992c

C++の3番をPythonとRubyに移植してみました(PythonやRubyの配列はC(++)とは事情が違うのかバケットソートしたら逆に遅くなりました)。

Python (0.54s)
無駄に3.3でも動くようにしていたりする
http://paiza.jp/poh/ec-campaign/result/99a7b5e35cf1bd095e45504931c15635

paizapoh1.py

#!/usr/bin/python
import sys,bisect
if sys.version_info[0]>=3:
	raw_input=input
	xrange=range

n,d=[int(e,10) for e in raw_input().split()]
v=sorted([int(raw_input(),10) for i in xrange(n)])
for i in xrange(d):
	m=int(raw_input())
	r=j=0
	#k=n-1
	k=bisect.bisect_right(v,m-v[0])-1
	while j<k and v[j]+v[j+1]<=m:
		while v[j]+v[k]>m: k-=1
		if r<v[j]+v[k]:
			r=v[j]+v[k]
			if r==m: break
		j+=1
	print(r)

Ruby (0.34s)
paizaのRubyは1.9.3なのでbackports gemから引用。2.0.0ならbsearch部分はC言語になるのでより高速化されるであろう。
http://paiza.jp/poh/ec-campaign/result/885ab06217b9e35f56b2baaf8193ba2d

paizapoh1.rb

#!/usr/bin/ruby
#https://github.com/marcandre/backports/blob/master/lib/backports/2.0.0/range/bsearch.rb
unless Range.method_defined? :bsearch
  class Range
    def bsearch
      return to_enum(:bsearch) unless block_given?
      from = self.begin
      to   = self.end
      unless from.is_a?(Numeric) && to.is_a?(Numeric)
        raise TypeError, "can't do binary search for #{from.class}"
      end

      midpoint = nil
      if from.is_a?(Integer) && to.is_a?(Integer)
        convert = Proc.new{ midpoint }
      else
        map = Proc.new do |pk, unpk, nb|
          result, = [nb.abs].pack(pk).unpack(unpk)
          nb < 0 ? -result : result
        end
        from = map['D', 'q', to.to_f]
        to   = map['D', 'q', to.to_f]
        convert = Proc.new{ map['q', 'D', midpoint] }
      end
      to -= 1 if exclude_end?
      satisfied = nil
      while from <= to do
        midpoint = (from + to).div(2)
        result = yield(cur = convert.call)
        case result
        when Numeric
          return cur if result == 0
          result = result < 0
        when true
          satisfied = cur
        when nil, false
          # nothing to do
        else
          raise TypeError, "wrong argument type #{result.class} (must be numeric, true, false or nil)"
        end

        if result
          to = midpoint - 1
        else
          from = midpoint + 1
        end
      end
      satisfied
    end
  end
end

n,d=gets.split.map(&:to_i)
v=n.times.map{gets.to_i}.sort
d.times{
	m=gets.to_i
	r=j=0
	k=((0...v.size).bsearch{|i|m-v[0]<v[i]}||v.size)-1 # upper_bound-1
	while j<k&&v[j]+v[j+1]<=m
		k-=1 while v[j]+v[k]>m
		if r<v[j]+v[k]
			r=v[j]+v[k]
			break if r==m
		end
		j+=1
	end
	p r
}