回答編集履歴

3

コメント受け修正

2020/08/23 05:44

投稿

swordone
swordone

スコア20649

test CHANGED
@@ -48,7 +48,7 @@
48
48
 
49
49
 
50
50
 
51
- logs=(double *)malloc(sizeof(double)*N);
51
+ logs=(double *)malloc(sizeof(double)*(N+1));
52
52
 
53
53
  logs[0]=logs[1]=0.0; //log10(0!)=log10(1!)=0
54
54
 
@@ -80,7 +80,7 @@
80
80
 
81
81
 
82
82
 
83
- LOG10 -= -N*log10(M);
83
+ LOG10 -= N*log10(M);
84
84
 
85
85
  int ans = (int)ceil(-LOG10);
86
86
 

2

修正

2020/08/23 05:44

投稿

swordone
swordone

スコア20649

test CHANGED
@@ -50,6 +50,8 @@
50
50
 
51
51
  logs=(double *)malloc(sizeof(double)*N);
52
52
 
53
+ logs[0]=logs[1]=0.0; //log10(0!)=log10(1!)=0
54
+
53
55
 
54
56
 
55
57
  double LOG10 = 0.0;
@@ -72,8 +74,6 @@
72
74
 
73
75
  scanf("%d",&r);
74
76
 
75
- if (r <= 1) continue; //rが0か1なら、log10(r!)=0なのでスキップ
76
-
77
77
  LOG10 -= logs[r];
78
78
 
79
79
  }
@@ -82,7 +82,7 @@
82
82
 
83
83
  LOG10 -= -N*log10(M);
84
84
 
85
- int ans = ceil(-LOG10);
85
+ int ans = (int)ceil(-LOG10);
86
86
 
87
87
 
88
88
 

1

対数計算の具体的戦略

2020/08/23 04:05

投稿

swordone
swordone

スコア20649

test CHANGED
@@ -1,3 +1,95 @@
1
1
  常用対数で計算するなら、全部常用対数で計算すればいいのでは?
2
2
 
3
3
  階乗が絡んでくると、掛け算ではちょっと数が大きくなればすぐオーバーフローしますよ。
4
+
5
+
6
+
7
+ 条件を満たす投票パターンは「同じものを含む順列」の公式から
8
+
9
+ N!/(r1!*r2!*...*rM!)通りとなるので、
10
+
11
+ これを全投票パターンのM^N通りで割れば確率pになります。
12
+
13
+ p≧10^(-x) ⇔ log10(p)≧-x ⇔ -log10(p)≦xなので、
14
+
15
+ pの常用対数を取って、-1倍して天井関数を取れば、条件を満たす最小の整数xが求められます。
16
+
17
+ pの常用対数の計算において、対数の性質から
18
+
19
+ log10(p)=log10(N!)-{log10(r1!)+log10(r2!)+...+log10(rM!)}-N*log10(M)
20
+
21
+ であり、階乗の定義と対数の性質から自然数nに対し、
22
+
23
+ log10(n!)=log10(1)+log10(2)+...+log10(n)
24
+
25
+ なので、掛け算を使うことなく計算が可能です。
26
+
27
+ log10(N!)はループで計算することになりますが、その過程でN以下のすべての自然数nに対するlog10(n!)の値が出てくることになるので、それを配列に保存しておけば、log10(ri!)に再利用できます。
28
+
29
+ なお、0!=1に注意してください。
30
+
31
+
32
+
33
+ Cのコードは書いたことがないのですが、たぶんこんな感じ?
34
+
35
+ ポインタなども理解が十分でないため、見様見真似で書いてます。
36
+
37
+ ```C
38
+
39
+ int main(void){
40
+
41
+ int N,M;
42
+
43
+ double *logs;
44
+
45
+
46
+
47
+ scanf("%d %d",&N,&M);
48
+
49
+
50
+
51
+ logs=(double *)malloc(sizeof(double)*N);
52
+
53
+
54
+
55
+ double LOG10 = 0.0;
56
+
57
+
58
+
59
+ for(int i=2;i<=N;i++){ //log10(1)=0なのでスキップして2から
60
+
61
+ LOG10+=log10(i);
62
+
63
+ logs[i] = LOG10;
64
+
65
+ }
66
+
67
+
68
+
69
+ int r;
70
+
71
+ for(int i=0;i<M;i++) {
72
+
73
+ scanf("%d",&r);
74
+
75
+ if (r <= 1) continue; //rが0か1なら、log10(r!)=0なのでスキップ
76
+
77
+ LOG10 -= logs[r];
78
+
79
+ }
80
+
81
+
82
+
83
+ LOG10 -= -N*log10(M);
84
+
85
+ int ans = ceil(-LOG10);
86
+
87
+
88
+
89
+ printf("%d\n",ans);
90
+
91
+ return 0;
92
+
93
+ }
94
+
95
+ ```