1≦n≦100のとき、 nCr >1,000,000となる nCrの数を求める問題です。
nの範囲が狭いので、nCrをすべて求めても1万通りしかありませんから、力づくで解くことが可能です。
しかし1≦n≦10000だったら1億通り計算して答えを導き出すのはなかなか大変です。
(やってみたら49971533個という答えが出てきました。)
まずは、rの範囲ですが、r<n/2で考えればよさそうです。
その1
n C r-1 < N < n C r
のとき、n-2r+1個がNを超える個数ですので、nに対してNを超えるrを探せばよいことになります。
その2
そしてnをn-1に置き換えます。この時、
n C r がNより大きければ、n C r-1はNより小さいので、この判定のみで個数が確定します。
n C r がNより小さければ、 n C r+1 がNを超えているはずです。(※)
ただし、r>n/2のときは、これ以上、Nを超える値は見つからないので、検索を打ち切ります。
つまり100から下に向かって探していけば、80回程度の検索で求まります。
O(n2)だった計算がO(n)になっているので、nを増やしても計算できるようになるはずです。
最初の1回だけは(※)の部分が成り立たないので、Loopを回してこれるまで求めるようにしておいたほうが簡単そうです。
n=100の場合、100×100×100=1000000なので、100×99×98/(3*2*1)は100万より小さく100×99×98×97/(4*3*2*1)は100万より大きいことが直感的にわかります。なので、n=100、r=4を初期値としてもよいのですが、nやNを変更した時のことを考えると、ちゃんとやった方がいいかなと思いました。