質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.59%

組み合わせの計算の高速化

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 702

grape_ll

score 45

下記のリンクの問題を解いていたのですが,sampleケースが両方通って他のケースは一つがWA,残りはTLEとなってしまいました.while文も終了条件はきちんとできていますし,for文もそこまで計算量があるようには思えません.あるとしたら組み合わせを求めているところかなと思うのですが,ここはどのようにしたら高速化できますでしょうか.
問題

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

double nPm(int n,int m){
    if(m<=1)  return (double)n;
    return (n-m+1)*(nPm(n,m-1));
}

double nCm(int n,int m){
    return nPm(n,m)/nPm(m,m);
}


int main(void){
    int N,M;
    int *r;

    scanf("%d %d",&N,&M);

    r=(int *)malloc(sizeof(int)*M);

    for(int i=0;i<M;i++) scanf("%d",&r[i]);

    double p=1/(double)M;

    double P=1;

    double LOG10=N*log10(p);

    //printf("p=%f\n",p);

    int A=N;
    for(int i=0;i<M;i++){
        P=nCm(A,r[i]);
        LOG10+=log10(P);
        A-=r[i];
    }

    //printf("P=%f\n",P);

    int ans=0;
    double divide=1.0;
    while(1){
        if(LOG10>=log10(divide)) break;
        divide/=10;
        ans++;
    }

    printf("%d\n",ans);
    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • swordone

    2020/08/22 21:35 編集

    間違った指摘でした。削除します。

    キャンセル

回答 3

checkベストアンサー

+1

常用対数で計算するなら、全部常用対数で計算すればいいのでは?
階乗が絡んでくると、掛け算ではちょっと数が大きくなればすぐオーバーフローしますよ。

条件を満たす投票パターンは「同じものを含む順列」の公式から
N!/(r1!*r2!*...*rM!)通りとなるので、
これを全投票パターンのM^N通りで割れば確率pになります。
p≧10^(-x) ⇔ log10(p)≧-x ⇔ -log10(p)≦xなので、
pの常用対数を取って、-1倍して天井関数を取れば、条件を満たす最小の整数xが求められます。
pの常用対数の計算において、対数の性質から
log10(p)=log10(N!)-{log10(r1!)+log10(r2!)+...+log10(rM!)}-N*log10(M)
であり、階乗の定義と対数の性質から自然数nに対し、
log10(n!)=log10(1)+log10(2)+...+log10(n)
なので、掛け算を使うことなく計算が可能です。
log10(N!)はループで計算することになりますが、その過程でN以下のすべての自然数nに対するlog10(n!)の値が出てくることになるので、それを配列に保存しておけば、log10(ri!)に再利用できます。
なお、0!=1に注意してください。

Cのコードは書いたことがないのですが、たぶんこんな感じ?
ポインタなども理解が十分でないため、見様見真似で書いてます。

int main(void){
    int N,M;
    double *logs;

    scanf("%d %d",&N,&M);

    logs=(double *)malloc(sizeof(double)*(N+1));
    logs[0]=logs[1]=0.0; //log10(0!)=log10(1!)=0

    double LOG10 = 0.0;

    for(int i=2;i<=N;i++){ //log10(1)=0なのでスキップして2から
        LOG10+=log10(i);
        logs[i] = LOG10;
    }

    int r;
    for(int i=0;i<M;i++) {
        scanf("%d",&r);
        LOG10 -= logs[r];
    }

    LOG10 -= N*log10(M);
    int ans = (int)ceil(-LOG10);

    printf("%d\n",ans);
    return 0;
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/08/23 20:18

    確かにこの考え方なら常用対数の加法減法で表すことができるうえ,計算量も削減できるように思えます.
    また,慣れない言語であるのに参考コードを書いてくださりありがとうございます.きれいに問題が解決しました.

    キャンセル

+1

nCmの値を愚直に計算すると倍精度でも表せません
C言語でこういう値がどう扱われるのかわかりませんが、おそらくそのせいでLOG10がNaNか何かになってbreakされず無限ループになってるんでしょう。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/08/23 20:07

    組み合わせを使用すると精度が足りないということは知りませんでした.
    ですが,私の考えでは計算の過程にどうしても組み合わせを用いる必要が出てきてしまいます.なにか他のうまい方法はありますでしょうか.

    キャンセル

  • 2020/08/23 21:45

    たぶんn,mが大きくなるとnPm(n,m)もnPm(m,m)もINFINITYになると思います。
    INFINITY同士の割り算だから、NaNになるのでしょう。

    キャンセル

+1

swordoneさんの回答は、次のように修正すればいいということですよね。

 double nPm(int n,int m){
-    if(m<=1)  return (double)n;
-    return (n-m+1)*(nPm(n,m-1));
+    if(m<=1)  return log10(n);
+    return log10(n-m+1) + nPm(n,m-1);
 }

 double nCm(int n,int m){
-    return nPm(n,m)/nPm(m,m);
+    return nPm(n,m) - nPm(m,m);
 }
     for(int i=0;i<M;i++){
         P=nCm(A,r[i]);
-        LOG10+=log10(P);
+        LOG10 += P;
         A-=r[i];
     }


追記
選ばれなかった色がある場合、すなわち r[i] = 0 の場合、
double nPm(int n,int m) の m が 0 になりますよ。
次のような修正が必要なのではありませんか?

double nPm(int n,int m){
    if(m==0)  return 0;
    if(m<=1)  return log10(n);
    return log10(n-m+1) + nPm(n,m-1);
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/08/23 14:36

    お見事です。 次の 2個所を修正すればよいでしょう。

    - logs=(double *)malloc(sizeof(double)*N);
    + logs = (double *)malloc(sizeof(double)*(N + 1));

    - LOG10 -= -N*log10(M);
    + LOG10 -= N*log10(M);

    キャンセル

  • 2020/08/23 14:45

    これは私の回答へのコメントでしょうか?
    ご指摘ありがとうございます。修正しました。

    キャンセル

  • 2020/08/23 14:50

    すみません。コメントを書くところを間違えました。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.59%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る