天下一プログラマーコンテスト2015予選B C 擬二等辺三角形

2015/09/06 (Sun) 天下一 AtCoder OEIS 数学

問題

問題文

方針

実験してOEISにかけたら一般項がヒットしたので，多倍長で計算しました． A001971

想定解は難しい考察です． こういう数オリみたいなのは苦手だ…

実装

@mod = 1000000007

def f n
  (n**2-2*n+5)>>3
end

n = gets.chomp.to_i
if n >= 10
  puts f(n-6) % @mod
else
  s = {}
  for i in 1..n do
    for j in (i+1)..n do
      for k in (j+1)..n do
        v = [i,j,k].sort
        next if i+j+k > n
        next if v[0]+v[1] <= v[2]
        next if v[1]+v[2] <= v[0]
        next if v[2]+v[0] <= v[1]
        if v[0]+1==v[1] || v[1]+1==v[2]
          if s.include? v
            s[v] += 1
          else
            s[v] = 1
          end
        end
      end
    end
  end
  puts s.size
end