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

メモ

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

yukicoder No.211 素数サイコロと合成数サイコロ (1)

問題はこちら
No.211 素数サイコロと合成数サイコロ (1) - yukicoder

2重ループで全探索するだけ

int main(){
	int a[]={2,3,5,7,11,13},b[]={4,6,8,9,10,12},i,j,n=0,k;
	scanf("%d",&k);
	for(i=0;i<6;i++)for(j=0;j<6;j++)if(k==a[i]*b[j])n++;
	printf("%.12f",n/36.0);
	//出力形式を指定しないとデフォルトだと6桁くらいだから誤差でWAになる
	return 0;
}

ところで、例えば素数ダイスの出目を1つ決めた時、積がKになるような合成数ダイスの出目は高々1個なので次のような書き換えができそう

main(){
	int a[]={2,3,5,7,11,13},b[]={4,6,8,9,10,12},i,j,n=0,k;
	scanf("%d",&k);
	for(i=0;i<6;i++)if(k%a[i]==0&&/* k/a[i]がbに含まれるか? */)n++;
	printf("%.12f",n/36.0);
	return 0;
}

「k/a[i]がbに含まれるか」を調べるためにbはbitで保存する。1011101010000bを使えば

main(){
	int a[]={2,3,5,7,11,13},b=5968,i,n=0,k;
	scanf("%d",&k);
	for(i=0;i<6;i++)if(k%a[i]==0&&k/a[i]<15&&b&1<<k/a[i])n++;
	//32以上shiftした時の動作は未定義なのでそれを回避
	printf("%.12f",n/36.0);
	return 0;
}

と書ける。(ここではx<<33はx<<1と同じ挙動をするらしく、k/a[i]が32以上の時にはバグる)

というかだったらaの方もいらないんじゃ?

main(){
	int a=10412,b=5968,i,j,n=0,k;
	scanf("%d",&k);
	for(i=1;i<14;i++)if(a&1<<i&&k%i==0&&k/i<15&&b&1<<k/i)n++;
	printf("%.12f",n/36.0);
	return 0;
}

ということでこれをぎゅっとして

s,n;
main(i){
for(scanf("%d",&s);i<15;)n+=10412>>i&s%i<1&s/i<15&5968>>s/i++;
s=!printf("%.12f",n/36.);
}

100B