本履歴

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

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

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

(Moscow programming contest)
ソートされている自然数の配列aが与えられる。
aのある部分集合の元の和として表現されない最小の自然数は何か?

うーん、ありがちな問題だ。
部分集合a[0..l]の部分集合で集合{1..m}を表現出来たとすると、a[l+1]を追加して何が表現できるか?
まず、a[l+1]>m+1なら、m+1は表現できないね。
a[l+1]<=m+1なら、{1..m,1+a[l+1]...m+a[l+1]}={1..m+a[l+1]}は表現可能
これを繰り返していくと、最後にmはa[0]+a[1]+...+a[a.size-1]になるね。この場合もm+1が表現できない。

2進数表現1,2,4,8,16,32,64,..でチェックすればOKかな。

こんなコードになった。

#a=0.upto(15).map{|k|2**k}
a=[*1..100,*5051..10000,*37256277..37256279]
m=0
a.each{|k|
	break if k>m+1
	m+=k
}
p m+1
#p a.inject(:+)

似たようなのでメジリアクの問題の変形も考えられる:
分銅の重さの配列が与えられたときに天秤で量れない重さの最小数は?
1,3,9,27,81,...でチェックすればOK。