Herd Sums(3)

一番良いアルゴリズム(下)

再び入力15を例にとってみる。

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

今度は小さい順にしてみたが、実は4つの式についてそれぞれ一番小さい数を簡単に求める方法がある。15から1,2,3...と順番に引いていくと、

15-1=14
14-2=12
12-3=9
9-4=5
5-5=0

0以下になったら終わりとする。

これだけ見るとわかり辛いが、こうしてみるとあることに気が付く。

14÷2=7
12÷3=4
9÷4=割り切れないので無効
5÷5=1

15は計算する必要がないし、他の3つの数も簡単に見つかる。しかも割る数を見ればいくつ足せばいいかが分かるのだ。

14÷2=7ということは、7から2つの連続する数、
12÷3=4ということは、4から3つの連続する数、
5÷5=1ということは、1から5つの連続する数を足せば良いとわかる。

コイツはすげぇ！！しかも計算量は程度ときたもんだ！というわけでこれが一番良いアルゴリズムでコードは67byteまで短縮することができる。holeさんもおそらくこの方法を発見したのだろう。

しかし、最短コードを出すにはこのアルゴリズムでは不可能なのだ。

つづく