ド文系が競プロのために数学をちょっとだけ勉強したときのメモです。
本記事はRubyで書いていますが、どちらかというと大人が数学を勉強した話です。
結論は「公式を使ってみよう」まで、スキップどうぞ。
やりたいこと
連続する数の総和を求めたいです。
たとえば、最初がaと最後がb として、その間の整数も全部足したいんです。
a = 100
b = 10000
数学の素養がない私がまず思いついた方法は、１回配列にしてsumすればできるね？ というものでした。
[*a..b].sum
でも、速度的に満足できないケースがあり、調べてみると0.0004秒くらいかかっているらしいことがわかりました。
Benchmark.realtime {[*a..b].sum}
=> 0.00042100000064237975
※irb上でも、require 'Benchmark'すると使える。
一度配列にする、というところで時間がかかっていそうです。
Benchmark.realtime {[*a..b]}
=> 0.0005849999979545828
※この例の場合、足し合わせている↑よりも配列にしているだけのこちらのほうが時間がかかっている。
公式を使ってみよう
最初と最後の数字がわかってるんだから数学的になんとかできそうじゃん？ と考えました。調べてみたところ、1から変数aまでのすべての整数の和を求めたい時、a と a + 1 をかけて2で割った数になるそうなんですね。
a * (a + 1) / 2
Rubyを電卓代わりに調べてみました。本当だ。すみません、知りませんでした。
[*1..10].sum
=> 55
10 * 11 / 2
=> 55
スタートが1ではないとき
上を応用すれば良いですね！ 大きい方(ここではb)の累積和から、小さい方の一つ前（ここではa - 1！）の累積和を引いてあげれば、a ~ b の区間の和だけが残ります。
丁寧に書くと、こんな感じでしょうか。
(b * (b + 1) / 2) - ((a - 1) * a / 2)
こちらもRubyを電卓代わりに調べてみました。
[*a..b].sum
=> 50000050
(b * (b + 1) / 2) - ((a - 1) * a / 2)
=> 50000050
ちゃんと計算できていますね！
肝心の速度はいかに
比較したところ、かなり速くなっていることがわかりました。
Benchmark.realtime {[*a..b].sum}
=> 0.0005270000001473818
Benchmark.realtime {(b * (b + 1) / 2) - ((a - 1) * a / 2)}
=> 1.0000003385357559e-06
※e-06 とは、10のマイナス6乗をかけた数を表します。
今回は、この方法で処理速度の壁を超えることができました。
さいごに
ぴったりの記事をなかなか見つけることができなかったので、ちょっとでも需要があればと思いまとめました。一方で、実用性がない説もあるので、もっとこうしたらいいよ、というのがありましたら、ぜひ教えていただけるとうれしいです。