CodeIQ：連続する正の整数の和

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「連続する正の整数の和」（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で解答しています。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#!/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

解説

ある数を連続する数の和で表すことのできる条件がわかれば、総当たりでできます。

考え方

ある数nを連続する数の和で表せる場合、そのパターン数はnの奇数の約数の数に等しいという性質を使います。
例えばn=12の場合、奇数の約数は1と3です。
n=12を奇数の約数で割った数を中心に、奇数の約数個の連続する数を作ることができます。
約数が1の時は12だけです。
約数が3の時は4を中心に3個なので3+4+5となります。
n=18で約数が9の時は、
(2-4) + (2-3) + (2-2) + (2-1) + 2 + (2+1) + (2+2) + (2+3) + (2+4)
= -2-1+0+1+2+3+4+5+6
= 3+4+5+6
と、負数になった部分が正数の部分と相殺します。

なのでプログラムは次の様になります。
まず、nの奇数の約数（1を含む）を列挙します。
その全てに対して、連続する数を求めます。この時、連続することは保証されるので最初と最後の数だけわかっていれば十分です。
作ることのできる連続数の中で連続するものを探します。見つかれば題意を満たすのでカウントします。
これを3以上の数で繰り返し、入力値の数だけ見つけた時に答えになります。

main

入力値を数値にしてsolve()に渡し、結果を印字します。

solve(n)

3以上の数（v）で題意を満たす数を数えます。
iは題意を満たした数の数です。
seq?()はvが題意を満たす数列を作れるかをチェックする関数なので、これがtrueを返したらiをカウントアップします。
iがnと等しくなった時のvが答えなのでそれを返します。

seq?(n)

nが題意を満たす数を作れるかを調べます。
oddDivisors()はnの奇数の約数のリストを降順で返します。
28行目で偶数のチェックをしていますが無意味です（消し忘れ）。
getPart()でnをd（=奇数の約数）個の連続数にした時の最初の数と最後の数を得ます。
check()はそれまでに得た連続数seqsと今回得た連続数arrが連続するかを調べます。連続したら題意を満たすのでtrueを返して終わります。
そうでなければseqsにarrを追加します。
これを全ての奇数の約数に対して行った結果、連続するものがなければfalseを返します。

oddDivisors(n)

nの奇数の約数を降順で列挙します。
検索して見つけたコードをちょっと直したものなので説明は省略します。

getPart(n, d)

nをd個の連続する数の和にした時の最初と最後の数を求めます。
mは中心の数です。
mnは最小の数でm-d/2ですが、0未満になった場合その絶対値までを相殺するので（m-d/2）の絶対値+1が最小の数になります。
mxは最大数でm+d/2です。

check(seqs, arr)

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ですが、このコードを見たとき「ポインタ？ なはずはないだろう。何これ」と思って調べたら可変長変数だったというわけです。