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

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.58 イカサマなサイコロ

問題はこちら
No.58 イカサマなサイコロ - yukicoder

DPすれば正確な値が求められるけど、誤差が緩いのでモンテカルロ

int main(){
	int n,k,i,j,t,s;
	scanf("%d%d",&n,&k);
	s=0;
	for(i=0;i<1e6;i++){
		t=0;
		for(j=0;j<k;j++)t+=rand()%3+4;
		for(;j<n;j++)t+=rand()%6+1;
		for(j=0;j<n;j++)t-=rand()%6+1;
		if(t>0)s++;
	}
	printf("%f",s/1e6);
	return 0;
}

サイコロを振る個数は同じなので、「rand()%6+1」の+1はいらないし、ループもまとめちゃって良さそう

i,j,k,s,t;
main(n){
	scanf("%d%d",&n,&k);
	for(;i<1e6;i++){
		for(t=j=0;j<n;j++)t-=rand()%6-(j<k?rand()%3+3:rand()%6);
		s+=t>0;
	}
	i=!printf("%f",s/1e6);
}

分岐を工夫して、処理系依存未定義動作にまとめる

i,j,k,s,t;
main(n){
	for(scanf("%d%d",&n,&k);i++<1e6;s+=t>0)for(t=j=0;j<n;t-=rand()%6-rand()%(j++<k?3:6)-(j<k)*3);
	i=!printf("%f",s/1e6);
}

134B

//ideoneだとjのincを後ろにして
t-=rand()%6-rand()%(j<k?3:6)-(j++<k)*3;
//だと通る
//ループ圧縮したら1B増えた
for(scanf("%d%d",&n,&k);j<n?t-=rand()%6-rand()%(j<k?3:6)-(j++<k)*3,1:(s+=t>0,t=j=0,i++<1e6););


16/07/29追記
j<kの結果を保存したほうがよくない?

x,i,j,k,s,t;
main(n){
	for(scanf("%d%d",&n,&k);i++<1e6;s+=t>0)for(t=j=0;j<n;t-=rand()%6-rand()%x+x-6)x=j++<k?3:6;
	i=!printf("%f",s/1e6);
}

1B短縮

ループ圧縮

for(scanf("%d%d",&n,&k);i++<1e6;s+=t>0)for(t=j=0;j<n;t-=rand()%6-rand()%x+x-6)x=j++<k?3:6;
for(scanf("%d%d",&n,&k);j<n?t-=rand(x=j++<k?3:6)%6-rand()%x+x-6,1:(s+=t>0,t=j=0,i++<1e6););
//そのままだと上述の通り+1Bだが
for(scanf("%d%d",&n,&k);n/j?t-=rand(x=k/j++?3:6)%6-rand()%x+x-6,1:(s+=t>1,t=j=i++<1e6););
//t,jの初期化に注意して1B短縮(jの初期値に注意)	

以上より

x,i,n,k,s,t;
main(j){
	for(scanf("%d%d",&n,&k);n/j?t-=rand()%6-rand(x=k/j++?3:6)%x+x-6,1:(s+=t>1,t=j=i++<1e6););
	i=!printf("%f",s/1e6);
}

132B