Herd Sums(0) - カメヲラボ

15
7+8
6+5+4
5+4+3+2+1

のように、連続する値を足して15にできるのは15も含めて4通りある。

9なら、

9
5+4
4+3+2

のように3通り。

この問題は、合計が与えられた自然数N(1 <= N <= 10,000,000)になるような連続する自然数が何通りあるかを求める問題である。

インプットの値が非常に大きいのと、http://d.hatena.ne.jp/Ozy/20060112#p1のように9回も通しているので、単に再帰の関数を書けばおしまいというわけにはいかない。もちろん、単純な探索でも多少の工夫でギリギリAcceptされるが。。。

ランキングhttp://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=2140&orderby=clen&language=-1を見る限り、上位陣は比較的短い探索時間でAcceptされている。これはきっと、シュゴー(ﾟДﾟ)なアルゴリズムがあるに違いない。

というわけで、次はこの問題について考えていこうと思う。