読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

数学は大切です。組み合わせ数を求めるプログラム問題

問題です。

0< a <= b <= c <= d
10 = a + b + c + d
が成立する(a,b,c,d)の組み合わせは9つです。

1000000 = a + b + c + d
が成立する(a,b,c,d)の組み合わせ数は?


以下自分の解答コード

#include <stdio.h>
#define N 1000000
/*
 10       --> 9
 100      --> 7153
 1000     --> 6965278
 10000    --> 6946527778
 100000   --> 6944652777778
 1000000  --> 6944465277777778
 10000000 --> 6944446527777777778
*/
int main()
{
   long long E,k;
   long long ans = 0;
   for( E=2; E<=N/2; E++){
      long long n=E/2;
      long long K = (3*E-N)/2;
      
      if( (double)n < (double)(3*E-N)/2.0)continue;
      if( K<1 )K=1;

      long long M = n-(K-1);

      ans += (N*M + (n*(n+1)-K*(K-1)) - 3*E*M)/2 + M - ((3*E-N)%2?M/2:0);
   }
   printf("ans: %lld\n",ans);
   return 0;
}



割り算って怖い><
思わぬバグというか、自身の考えが至らず、微妙な誤差から抜け出せませんでした。
問題掲載の元サイトのリンクを張るべきなのだけど、どこで見たのか忘れてしまった。
上記は強引な解法だけど、もっとスマートな方法があるかもしれない。
というかきっとある…