12472


つなぎ合わせたときの長さ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）、どこかに間違いがある気がするのですが、  
**どこをどのように直せばよいか** 教えていただけないでしょうか？

[code]

    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
    
[/code]

（追記）  
以下の組み合わせを数えていることがわかりました。

[4, 13, 18]  
[5, 12, 18]  
[7, 10, 18]  
[7, 11, 17]  
[11, 12, 12]  
[12, 13, 10]  
[13, 17, 5]

よって、[11, 12, 12] を誤って数えているようです。


CC BY-SA 3.0
2015-07-18T09:15:38.180
12466
2015-07-20T15:29:09.457
2015-07-18T20:03:31.487
5363
5363
question
ruby アルゴリズム lambda
N個の棒の中から3つをつなぎ合わせて長さがLになる組み合わせの総数を求めるプログラムについて


変更箇所だけ示します。

[code]

    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
        v2 = r - v[a]
        if v2 > v[a] && e[v2] then
          ## print v[i], " ", v[a], " ", v2, "\n"
          c+=1
        end
        a+=1
      end
    }
    
[/code]

元々の数値配列がソートされていて、かつユニークであることを利用してみました。`if v2 > v[a] && ...`
の部分がそれに当たるのですが、これによって、`v[i] < v[a] < v2` を満たす組み合わせだけがカウントされることになります。  
ただ、search 関数に渡す lambda 式(関数？)内で、元々が `< r` となっていたのはよく分かりませんが…。


CC BY-SA 3.0
2015-07-18T16:22:08.473
12472
2015-07-18T16:22:08.473
12466
answer


質問文にあったコードとはすこし違う方針で作ってみました。

[code]

    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!.uniq!
    
    c = 0 # count
    (0..n - 3).each do |i|
      break if s < v[i] + v[i + 1] + v[i + 2]
      r = s - v[i]
      (i + 1.. n - 2).each do |j|
        break if r < v[j] + v[j + 1]
        next unless e[r - v[j]]
    
        c += 1
        # puts "#{v[i]} #{v[j]} #{r - v[j]}"
    
      end
    end
    
    p c
    
[/code]

実行例：

[code]

    $ ruby 99.rb
    6
    5
    1
    2
    3
    4
    5
    1
    
    $ ruby 99.rb
    35
    10
    13
    12
    17
    10
    4
    18
    3
    11
    5
    7
    6
    
[/code]

データを与える部分を変更し、argus さんの変更を適用したコードと  
上のコードで速度を比較してみました。  
0.rb (argus さんの変更を適用したコード)

[code]

    s = 200
    n = 50000
    v = Array.new
    e = Array.new( s, false ) # exist
    (1..n).each do |x|
      x2 = x * 2
      v << x2
      e[x2] = true if x2 < s
    end
    v.sort!.uniq!
    
    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
        v2 = r - v[a]
        if v2 > v[a] && e[v2] then
          # print v[i], " ", v[a], " ", v2, "\n"
          c+=1
        end
        a+=1
      end
    }
    
    p c
    
[/code]

9.rb (katoy のコード)

[code]

    s = 200
    n = 50000
    v = Array.new
    e = Array.new( s, false ) # exist
    (1..n).each do |x|
      x2 = x * 2
      v << x2
      e[x2] = true if x2 < s
    end
    v.sort!.uniq!
    
    c = 0 # count
    (0..n - 3).each do |i|
      break if s < v[i] + v[i + 1] + v[i + 2]
      r = s - v[i]
      (i + 1.. n - 2).each do |j|
        break if r < v[j] + v[j + 1]
        next unless e[r - v[j]]
    
        c += 1
        # puts "#{v[i]} #{v[j]} #{r - v[j]}"
    
      end
    end
    
    p c
    
[/code]

それぞれ 3 回 time で実行時間をしらべました。  
$ time ruby 0.rb  
784

[code]

    real    0m1.375s
    user    0m0.858s
    sys     0m0.470s
    $ time ruby 0.rb
    784
    
    real    0m1.375s
    user    0m0.856s
    sys     0m0.476s
    $ time ruby 0.rb
    784
    
    real    0m1.435s
    user    0m0.874s
    sys     0m0.497s
    
[/code]

-
[code]

    $ time ruby 9.rb
    784
    
    real    0m1.046s
    user    0m0.526s
    sys     0m0.474s
    $ time ruby 9.rb
    784
    
    real    0m1.044s
    user    0m0.524s
    sys     0m0.474s
    $ time ruby 9.rb
    784
    
    real    0m1.060s
    user    0m0.530s
    sys     0m0.478s
    
[/code]


CC BY-SA 3.0
2015-07-20T15:29:09.457
12509
2015-07-20T15:29:09.457
2987
12466
answer