「ステップ・アップ・サム」問題解答（CodeIQ）

CodeIQ 数学 コードゴルフ

はじめに

CodeIQという所で公開していたプログラミング問題「ステップ・アップ・サム」( 出題者は @riverplus Kawazoeさん ) に解答しましたので、そのネタばれというか解説です。

問題

既に問題は公開終了していますから、概要を説明しますと、

  • 標準入力より自然数が1個与えられる ( nとする )
  • nを2個以上の連続する自然数の和で表す
  • それぞれの組 ( 連続する自然数 ) の最小値の合計を計算し、出力する

といったものです。 例えば、入力が 30 であれば、n=30=9+10+11=6+7+8+9=4+5+6+7+8 の3通りの表し方がありますから、最小値の合計 9+6+4=19 から、19を出力するようなコードを組みます。

解答

golf解をいつも心がけていますので、今回もそのようにしました。Ruby(53)です。

a=-n=gets.to_i;i=0;n%i>0||a+=n/i+1until 0>n-=i+=1;p a

※なお、@antimon2 あんちもんさんが、もう1文字短くして下さったのがこちら。

さて。そのままでは良く分からないかも知れないので、もうちょっと丁寧に書くとこういう事です。

n=gets.to_i
a=-n
i=0
while ( i+=1; n-=i; n>=0 )
  if n%i==0
    a+=n/i+1
  end
end
p a

aは出力すべき答え、i は「何個連続した自然数の和で表せるか」その個数を保持するループ変数です。
nは入力値を保存した後、1,2,3,…とiを増やすにつれ、都度 i の分だけ減らしていきます。そうすると次の通り、n が i で割り切れる時が丁度「連続した自然数の和で表せる」時に対応する、ということになりますので、その時の最小値 ( 図中の m ) を a に足していけば答えにありつけます。 f:id:ange1:20150919005817p:plain

なお、なぜ最初に a=-n をセットしているかと言うと、これは「1個連続の自然数」のケース分の補正です。

別解

実は最初は別のアプローチでコードを組んでいました。尤も、そちらはgolfには向かないので方針を転換したのですが…。
ただ、もしもっと大きな入力値に対応する必要がある場合、上の解よりも高速に処理することができる方法ですので、概要のみ挙げておきます。

実は、n が連続する幾つかの自然数の和で表せることと、n が(奇数)×(何か自然数)という積で表せることは1対1に対応しています。
その対応は次の図の通り。n=xy とした時の、x,yの大小関係によって2通りに分かれます。 f:id:ange1:20150919010644p:plain

なぜ分かれるかというと、連続する自然数という条件があるからですね。負の整数を許容するならばどちらのケースも取れるのですが、自然数という条件があると、図中 m の値が正になるのはどちらか1通りのみに決まるという事です。

で、実際の値で見てみると、例えば

  • 30=5×6 の場合
    • x＜2y のケースに該当し、30=4+5+6+7+8 という5個の連続する自然数の和に対応します。m=6-(5-1)/2=4 です。
  • 21=7×3 の場合
    • x＞2y のケースに該当し、21=1+2+3+4+5+6 という3組6個の連続する自然数の和に対応します。m=(7+1)/2-3=1 です。なお 7 は真ん中の2数 3,4 の和になっています。

なお、図中 y の偶奇は関係ありません。どちらでもO.K.です。
まあなので場合分けが必要にはなるのですが、n の奇数の約数を列挙して、それぞれに応じて最小値 ( 図中のmの値 ) を調べていくだけで済みますから、素因数分解をベースに組めば、最初に紹介した解 ( 計算量Ο(√n) ) よりも少ない計算量にできます。

最後に

他の方の解も、出題者のKawazoeさんがtogetterにまとめてますので、興味がある方は見てみては。