回答編集履歴
4
マークダウン恵助＠ぷ
answer
CHANGED
|
@@ -1,48 +1,48 @@
|
|
|
1
|
-
常用対数で計算するなら、全部常用対数で計算すればいいのでは？
|
|
1
|
+
常用対数で計算するなら、全部常用対数で計算すればいいのでは？
|
|
2
|
-
階乗が絡んでくると、掛け算ではちょっと数が大きくなればすぐオーバーフローしますよ。
|
|
2
|
+
階乗が絡んでくると、掛け算ではちょっと数が大きくなればすぐオーバーフローしますよ。
|
|
3
|
-
|
|
3
|
+
|
|
4
|
-
条件を満たす投票パターンは「同じものを含む順列」の公式から
|
|
4
|
+
条件を満たす投票パターンは「同じものを含む順列」の公式から
|
|
5
|
-
N!/(r1!*r2!*...*rM!)通りとなるので、
|
|
5
|
+
N!/(r1!\*r2!\*...\*rM!)通りとなるので、
|
|
6
|
-
これを全投票パターンのM^N通りで割れば確率pになります。
|
|
6
|
+
これを全投票パターンのM^N通りで割れば確率pになります。
|
|
7
|
-
p≧10^(-x) ⇔ log10(p)≧-x ⇔ -log10(p)≦xなので、
|
|
7
|
+
p≧10^(-x) ⇔ log10(p)≧-x ⇔ -log10(p)≦xなので、
|
|
8
|
-
pの常用対数を取って、-1倍して天井関数を取れば、条件を満たす最小の整数xが求められます。
|
|
8
|
+
pの常用対数を取って、-1倍して天井関数を取れば、条件を満たす最小の整数xが求められます。
|
|
9
|
-
pの常用対数の計算において、対数の性質から
|
|
9
|
+
pの常用対数の計算において、対数の性質から
|
|
10
|
-
log10(p)=log10(N!)-{log10(r1!)+log10(r2!)+...+log10(rM!)}-N*log10(M)
|
|
10
|
+
log10(p)=log10(N!)-{log10(r1!)+log10(r2!)+...+log10(rM!)}-N\*log10(M)
|
|
11
|
-
であり、階乗の定義と対数の性質から自然数nに対し、
|
|
11
|
+
であり、階乗の定義と対数の性質から自然数nに対し、
|
|
12
|
-
log10(n!)=log10(1)+log10(2)+...+log10(n)
|
|
12
|
+
log10(n!)=log10(1)+log10(2)+...+log10(n)
|
|
13
|
-
なので、掛け算を使うことなく計算が可能です。
|
|
13
|
+
なので、掛け算を使うことなく計算が可能です。
|
|
14
|
-
log10(N!)はループで計算することになりますが、その過程でN以下のすべての自然数nに対するlog10(n!)の値が出てくることになるので、それを配列に保存しておけば、log10(ri!)に再利用できます。
|
|
14
|
+
log10(N!)はループで計算することになりますが、その過程でN以下のすべての自然数nに対するlog10(n!)の値が出てくることになるので、それを配列に保存しておけば、log10(ri!)に再利用できます。
|
|
15
|
-
なお、0!=1に注意してください。
|
|
15
|
+
なお、0!=1に注意してください。
|
|
16
|
-
|
|
16
|
+
|
|
17
|
-
Cのコードは書いたことがないのですが、たぶんこんな感じ？
|
|
17
|
+
Cのコードは書いたことがないのですが、たぶんこんな感じ？
|
|
18
|
-
ポインタなども理解が十分でないため、見様見真似で書いてます。
|
|
18
|
+
ポインタなども理解が十分でないため、見様見真似で書いてます。
|
|
19
|
-
```C
|
|
19
|
+
```C
|
|
20
|
-
int main(void){
|
|
20
|
+
int main(void){
|
|
21
|
-
int N,M;
|
|
21
|
+
int N,M;
|
|
22
|
-
double *logs;
|
|
22
|
+
double *logs;
|
|
23
|
-
|
|
23
|
+
|
|
24
|
-
scanf("%d %d",&N,&M);
|
|
24
|
+
scanf("%d %d",&N,&M);
|
|
25
|
-
|
|
25
|
+
|
|
26
|
-
logs=(double *)malloc(sizeof(double)*(N+1));
|
|
26
|
+
logs=(double *)malloc(sizeof(double)*(N+1));
|
|
27
|
-
logs[0]=logs[1]=0.0; //log10(0!)=log10(1!)=0
|
|
27
|
+
logs[0]=logs[1]=0.0; //log10(0!)=log10(1!)=0
|
|
28
|
-
|
|
28
|
+
|
|
29
|
-
double LOG10 = 0.0;
|
|
29
|
+
double LOG10 = 0.0;
|
|
30
|
-
|
|
30
|
+
|
|
31
|
-
for(int i=2;i<=N;i++){ //log10(1)=0なのでスキップして2から
|
|
31
|
+
for(int i=2;i<=N;i++){ //log10(1)=0なのでスキップして2から
|
|
32
|
-
LOG10+=log10(i);
|
|
32
|
+
LOG10+=log10(i);
|
|
33
|
-
logs[i] = LOG10;
|
|
33
|
+
logs[i] = LOG10;
|
|
34
|
-
}
|
|
34
|
+
}
|
|
35
|
-
|
|
35
|
+
|
|
36
|
-
int r;
|
|
36
|
+
int r;
|
|
37
|
-
for(int i=0;i<M;i++) {
|
|
37
|
+
for(int i=0;i<M;i++) {
|
|
38
|
-
scanf("%d",&r);
|
|
38
|
+
scanf("%d",&r);
|
|
39
|
-
LOG10 -= logs[r];
|
|
39
|
+
LOG10 -= logs[r];
|
|
40
|
-
}
|
|
40
|
+
}
|
|
41
|
-
|
|
41
|
+
|
|
42
|
-
LOG10 -= N*log10(M);
|
|
42
|
+
LOG10 -= N*log10(M);
|
|
43
|
-
int ans = (int)ceil(-LOG10);
|
|
43
|
+
int ans = (int)ceil(-LOG10);
|
|
44
|
-
|
|
44
|
+
|
|
45
|
-
printf("%d\n",ans);
|
|
45
|
+
printf("%d\n",ans);
|
|
46
|
-
return 0;
|
|
46
|
+
return 0;
|
|
47
|
-
}
|
|
47
|
+
}
|
|
48
48
|
```
|
3
コメント受け修正
answer
CHANGED
|
@@ -23,7 +23,7 @@
|
|
|
23
23
|
|
|
24
24
|
scanf("%d %d",&N,&M);
|
|
25
25
|
|
|
26
|
-
logs=(double *)malloc(sizeof(double)*N);
|
|
26
|
+
logs=(double *)malloc(sizeof(double)*(N+1));
|
|
27
27
|
logs[0]=logs[1]=0.0; //log10(0!)=log10(1!)=0
|
|
28
28
|
|
|
29
29
|
double LOG10 = 0.0;
|
|
@@ -39,7 +39,7 @@
|
|
|
39
39
|
LOG10 -= logs[r];
|
|
40
40
|
}
|
|
41
41
|
|
|
42
|
-
LOG10 -=
|
|
42
|
+
LOG10 -= N*log10(M);
|
|
43
43
|
int ans = (int)ceil(-LOG10);
|
|
44
44
|
|
|
45
45
|
printf("%d\n",ans);
|
2
修正
answer
CHANGED
|
@@ -24,6 +24,7 @@
|
|
|
24
24
|
scanf("%d %d",&N,&M);
|
|
25
25
|
|
|
26
26
|
logs=(double *)malloc(sizeof(double)*N);
|
|
27
|
+
logs[0]=logs[1]=0.0; //log10(0!)=log10(1!)=0
|
|
27
28
|
|
|
28
29
|
double LOG10 = 0.0;
|
|
29
30
|
|
|
@@ -35,12 +36,11 @@
|
|
|
35
36
|
int r;
|
|
36
37
|
for(int i=0;i<M;i++) {
|
|
37
38
|
scanf("%d",&r);
|
|
38
|
-
if (r <= 1) continue; //rが0か1なら、log10(r!)=0なのでスキップ
|
|
39
39
|
LOG10 -= logs[r];
|
|
40
40
|
}
|
|
41
41
|
|
|
42
42
|
LOG10 -= -N*log10(M);
|
|
43
|
-
int ans = ceil(-LOG10);
|
|
43
|
+
int ans = (int)ceil(-LOG10);
|
|
44
44
|
|
|
45
45
|
printf("%d\n",ans);
|
|
46
46
|
return 0;
|
1
対数計算の具体的戦略
answer
CHANGED
|
@@ -1,2 +1,48 @@
|
|
|
1
1
|
常用対数で計算するなら、全部常用対数で計算すればいいのでは？
|
|
2
|
-
階乗が絡んでくると、掛け算ではちょっと数が大きくなればすぐオーバーフローしますよ。
|
|
2
|
+
階乗が絡んでくると、掛け算ではちょっと数が大きくなればすぐオーバーフローしますよ。
|
|
3
|
+
|
|
4
|
+
条件を満たす投票パターンは「同じものを含む順列」の公式から
|
|
5
|
+
N!/(r1!*r2!*...*rM!)通りとなるので、
|
|
6
|
+
これを全投票パターンのM^N通りで割れば確率pになります。
|
|
7
|
+
p≧10^(-x) ⇔ log10(p)≧-x ⇔ -log10(p)≦xなので、
|
|
8
|
+
pの常用対数を取って、-1倍して天井関数を取れば、条件を満たす最小の整数xが求められます。
|
|
9
|
+
pの常用対数の計算において、対数の性質から
|
|
10
|
+
log10(p)=log10(N!)-{log10(r1!)+log10(r2!)+...+log10(rM!)}-N*log10(M)
|
|
11
|
+
であり、階乗の定義と対数の性質から自然数nに対し、
|
|
12
|
+
log10(n!)=log10(1)+log10(2)+...+log10(n)
|
|
13
|
+
なので、掛け算を使うことなく計算が可能です。
|
|
14
|
+
log10(N!)はループで計算することになりますが、その過程でN以下のすべての自然数nに対するlog10(n!)の値が出てくることになるので、それを配列に保存しておけば、log10(ri!)に再利用できます。
|
|
15
|
+
なお、0!=1に注意してください。
|
|
16
|
+
|
|
17
|
+
Cのコードは書いたことがないのですが、たぶんこんな感じ？
|
|
18
|
+
ポインタなども理解が十分でないため、見様見真似で書いてます。
|
|
19
|
+
```C
|
|
20
|
+
int main(void){
|
|
21
|
+
int N,M;
|
|
22
|
+
double *logs;
|
|
23
|
+
|
|
24
|
+
scanf("%d %d",&N,&M);
|
|
25
|
+
|
|
26
|
+
logs=(double *)malloc(sizeof(double)*N);
|
|
27
|
+
|
|
28
|
+
double LOG10 = 0.0;
|
|
29
|
+
|
|
30
|
+
for(int i=2;i<=N;i++){ //log10(1)=0なのでスキップして2から
|
|
31
|
+
LOG10+=log10(i);
|
|
32
|
+
logs[i] = LOG10;
|
|
33
|
+
}
|
|
34
|
+
|
|
35
|
+
int r;
|
|
36
|
+
for(int i=0;i<M;i++) {
|
|
37
|
+
scanf("%d",&r);
|
|
38
|
+
if (r <= 1) continue; //rが0か1なら、log10(r!)=0なのでスキップ
|
|
39
|
+
LOG10 -= logs[r];
|
|
40
|
+
}
|
|
41
|
+
|
|
42
|
+
LOG10 -= -N*log10(M);
|
|
43
|
+
int ans = ceil(-LOG10);
|
|
44
|
+
|
|
45
|
+
printf("%d\n",ans);
|
|
46
|
+
return 0;
|
|
47
|
+
}
|
|
48
|
+
```
|