つなぎ合わせたときの長さLと、N個(1≦N≦5000)の棒の長さが標準入力から与えられるとき、N個の棒の中から3つをつなぎ合わせて長さがLになる組み合わせの総数を求める
という問題の解説記事(https://codeiq.jp/magazine/2015/07/26213/)があるのですが、
紹介されていた以下のRubyの解法は標準入力データを
35
10
13
12
17
10
4
18
3
11
5
7
とすると、出力が7となり(正しくは6)、どこかに間違いがある気がするのですが、
どこをどのように直せばよいか教えていただけないでしょうか?
s = STDIN.gets.to_i # Lsum
n = STDIN.gets.to_i # nSticks
v = Array.new # sticks
e = Array.new( s, false ) # exist
n.times{
a = STDIN.gets.to_i
v << a
e[a] = true if a < s
}
v.sort!
def search(l, r, f)
while r-l > 1
k = (l+r)/2
f.call(k) ? (l=k) : (r=k)
end
l
end
c = 0 # count
(0..n-3).each{|i|
r = s-v[i]
a = search(i+1, n-1, lambda{|k| v[k]+v[n-1] < r})
b = search(i+1, n-1, lambda{|k| v[k]+v[k+1] < r})
while a <= b
c+=1 if e[r-v[a]]
a+=1
end
}
p c
(追記)
以下の組み合わせを数えていることがわかりました。
[4, 13, 18]
[5, 12, 18]
[7, 10, 18]
[7, 11, 17]
[11, 12, 12]
[12, 13, 10]
[13, 17, 5]
よって、[11, 12, 12] を誤って数えているようです。