私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「連続する正の整数の和」（CodeIQ）を参照してください。
ある数を「連続する正の整数の和」で表現することを考えます。
例えば、15は「1+2+3+4+5」「4+5+6」「7+8」のように表現できます。
このように複数の表現が可能で、しかもその表現で使われる数が連続するものを探します。
例えば、15の場合は「4+5+6」「7+8」が「4, 5, 6, 7, 8」のように連続します。
このように連続する表現が可能な数を小さい方から順に調べると、
3, 15, 27, …となります。
3 … 1 + 2, 3
15 … 4 + 5 + 6, 7 + 8
27 … 2 + 3 + 4 + 5 + 6 + 7, 8 + 9 + 10
標準入力から整数 n が与えられたとき、小さい方から n 番目の数を標準出力に出力してください。
なお、n は80以下の整数とします。
【入出力サンプル】
標準入力
2
標準出力
15
Rubyで解答しています。
#!/usr/bin/ruby
require 'prime'
def oddDivisors(n)
return [1] if n == 1
first, *rest = Prime.prime_division(n).map{|q, k| (0..k).map{|i| q**i} }
return first.product(*rest).map{|a| a.reduce(:*) }.select{|v| v % 2 == 1}.sort{|a, b| b <=> a}
end
def getPart(n, d)
m = n / d
mn = m - d/2 <= 0 ? (m - d/2).abs+1 : m - d/2
mx = m + d/2
return [mn, mx]
end
def check(seqs, arr)
seqs.each{|s|
return true if s[1] == arr[0] - 1
return true if s[0] == arr[1] + 1
}
return false
end
def seq?(n)
seqs = []
oddDivisors(n).each{|d|
next if d % 2 == 0
arr = getPart(n, d)
return true if check(seqs, arr)
seqs << arr
}
return false
end
def solve(n)
v = 3
i = 0
loop{
i += 1 if seq?(v)
break if i == n
v += 1
}
return v
end
# main
while line = gets
line.strip!
next if line.empty?
p solve(line.to_i)
end
入力値を数値にしてsolve()に渡し、結果を印字します。
3以上の数（v）で題意を満たす数を数えます。
iは題意を満たした数の数です。
seq?()はvが題意を満たす数列を作れるかをチェックする関数なので、これがtrueを返したらiをカウントアップします。
iがnと等しくなった時のvが答えなのでそれを返します。
nが題意を満たす数を作れるかを調べます。
oddDivisors()はnの奇数の約数のリストを降順で返します。
28行目で偶数のチェックをしていますが無意味です（消し忘れ）。
getPart()でnをd（=奇数の約数）個の連続数にした時の最初の数と最後の数を得ます。
check()はそれまでに得た連続数seqsと今回得た連続数arrが連続するかを調べます。連続したら題意を満たすのでtrueを返して終わります。
そうでなければseqsにarrを追加します。
これを全ての奇数の約数に対して行った結果、連続するものがなければfalseを返します。
nの奇数の約数を降順で列挙します。
検索して見つけたコードをちょっと直したものなので説明は省略します。
nをd個の連続する数の和にした時の最初と最後の数を求めます。
mは中心の数です。
mnは最小の数でm-d/2ですが、0未満になった場合その絶対値までを相殺するので（m-d/2）の絶対値+1が最小の数になります。
mxは最大数でm+d/2です。
seqsは複数の連続する数のリストを持っています。
arrは1つの連続する数です。
seqsの中にarrと連続する数列があるかをチェックします。
seqsの1要素とarrはgetPart()で得た結果なので連続する数を[最初の数, 最後の数]で表現しています。
なので、seqsの1要素の最後とarr最初かseqsの1要素の最初とarr最後が連続していればこららが連続していることになります。
そういえば以前に別の問題である数を連続する数の和にするというのをやっていました。そんなことは忘れていたので今回も調べたら、以前に見たことのあるページが出てきたので前にもやったなぁと。
それはそうとRubyの可変長変数のことを今回初めて知りました。
「first, *rest = Prime.prime_division(n).map{|q, k| (0..k).map{|i| q**i} }」の*restですが、このコードを見たとき「ポインタ？ なはずはないだろう。何これ」と思って調べたら可変長変数だったというわけです。