0,1,2,…,Nの中からk個選び足し合わせてできる整数は何通りか

最近AtCorderなるものを始めてみたのですが、そこで出題されていた以下の箇所がよく分かりませんでした。
D - Sum of Large Numbers

0,1,2,…,Nの中からk個選び足し合わせてできる整数は何通りか

ずっとコンビネーションnCrをうまく使えば解けると思っていたのですが、もっとエレガントに解けるみたいです。

備忘録もかねて解き方を書き残しておきたいと思います。

まずはシンプルにするためにN=3,k=2にして考えてみましょう。

0,1,2,3の中から2個選び足し合わせてできる整数は何通りか

これをさらに単純にしてみるために以下の問題を最初に考えてみます。

0,1,2,3の中から2個選びとる組み合わせ

f:id:hanaaaaaachiru:20200420200511p:plain

組み合わせは６通りがありますが、合計値は0 + 3 = 3, 1 + 2 = 3が被ってしまっていることが分かります。

ここから6 - xのように考えていくと結構難しくなってしまいます。(というか私には分かりませんでした・・・)

方針を変更してもう一度組み合わせの合計値を見直してみると、以下のような法則が導けます。

合計値は1,2,3,4,5のように連続した整数になる

実は選びとる数が2個じゃなくても成り立つんですよね。

よって問題は以下の問題に帰着することができます。

最大値xと最小値yを求めて、x - y + 1を求める

方針が決まったので、実際に最大値と最小値を求める式を探してみます。

0,1,2,…,Nの中からk個選び足し合わせてできる整数

等差数列の和の公式、初項がa，末項がl，項数がnのときは $\dfrac{1}{2}n(a+l)$ を用いると、
(ちなみに等比数列の和の公式は、初項がa，公比r，項数nのとき $\frac{a(1-r^n)}{1-r})$

と導けます。

よって、目的の組み合わせの数はこの式で求められます。

$\dfrac{k(2N-k+1)}{2} - \dfrac{k(k-1)}{2} + 1$

最後の式をみた時になるほどなーと思いました。ずっとnCrばかり考えていた私には全く思いつきもしませんでしたね。

AtCorderをやってみるとまた言語の違った側面をみることができて面白いです。ただこれをどんなにやったところでアプリは完成しないことは明白ですが。

とりあえず暇つぶし感覚で定期的に参加してみようかなと思っています。

ではまた。

はなちるのマイノート