読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

プログラムコンテストの練習問題

Algorithms and Programming: Problems and Solutionsにあった次の問題を考えてみた。

ソートされた2つのn次配列xとm次配列yと整数qが与えられる。
i,jをうまく選んでx[i]+y[j]をqに近くせよ。計算量O(n+m)

わからなかったのでヒントを参考に・・・
新しい配列z[j]=q-y[m-j+1]を作り、xとzをマージしn+m次配列wを作ることを考える。
w[k+1]-w[k]が一番小さいのが求めるもの。ただし、それぞれxとzから取られているとする。

x,zの最後に影響がない番兵を追加して終了条件を簡単にしている

#return the closest value x[i]+y[j] to q
def solve(x,y,q)
	min=(x.first+y.first-q).abs
	ans=x.first+y.first
	z=y.reverse.map{|a|q-a}
	x_sentinel=z.last+min+1
	z_sentinel=x.last+min+1
	if (x_sentinel-z_sentinel).abs<=min
		if x_sentinel>z_sentinel
			x_sentinel+=min
		else
			z_sentinel+=min
		end
	end
	x<<x_sentinel
	z<<z_sentinel
	xsize=x.size
	zsize=z.size
	
	if x.first<z.first
		pre=x.first
		pre_x_flag=true
		xidx=1
		zidx=0
	else
		pre=z.first
		pre_x_flag=false
		xidx=0
		zidx=1
	end
	
	while (xidx<xsize)&&(zidx<zsize)
		if x[xidx]<z[zidx]
			unless pre_x_flag
				if x[xidx]-pre<min
					min=x[xidx]-pre
					ans=x[xidx]-pre+q
				end
				pre_x_flag=true
			end
			pre=x[xidx]
			xidx+=1
		else
			if pre_x_flag
				if z[zidx]-pre<min
					min=z[zidx]-pre
					ans=-z[zidx]+pre+q
				end
				pre_x_flag=false
			end
			pre=z[zidx]
			zidx+=1
		end
	end
	ans
end

if __FILE__==$0
	p solve([*1..10000],[*100..10000],0) #=>101
	p solve([*1..100000],[*100..100000],200001) #=>200000
	p solve([-5,-1,4,9,17,33],[*-22..-10,-3,0,3,4,5,10,*100..1000],0) #=>0
	p solve([1,7],[4,5],9) #=>11
	p solve([1],[4],2012) #=>5
end