4

つなぎ合わせたときの長さ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] を誤って数えているようです。

1
  • 2
    6 4 1 2 3 4 と入力すると 2 と出力されます。 [1,2,3], [2,3,1] の2つを数え上げているようです。 まずは, この入力で 1 と出力されるように直す必要があるかもしれません。
    – katoy
    Commented 2015年7月18日 12:54

2 件の回答 2

5

変更箇所だけ示します。

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
}

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

3
  • 1
    argus さんのように条件を追加しても、問題を制限時間(1秒)内で解けました。(ideone.com/Q5OW9T
    – TOM
    Commented 2015年7月18日 19:25
  • v[i] < v[a] < v2 に制限すると、[12, 13, 10], [13, 17, 5] が漏れてしまうのでは?
    – katoy
    Commented 2015年7月18日 22:30
  • 2
    代わりに [5,13,17] と [10,12,13] がカウントされます。
    – user9156
    Commented 2015年7月19日 0:33
2

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

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

実行例:

$ 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

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

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

9.rb (katoy のコード)

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

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

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

-

$ 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

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。