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

メモ

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

yukicoder No.294 SuperFizzBuzz

問題はこちら
No.294 SuperFizzBuzz - yukicoder

整数が3の倍数である必要十分条件は、各位の和が3の倍数であること。
5の倍数である必要十分条件は、一の位が0or5であること。
これより、問題は「各位の数字が'3'or'5'で、1の位が5であり、'5'の個数が3の倍数であるようなものの内~」と読める
各桁の数は3か5なのでbitで保存出来そうな気がするが、それだと何桁の数かわからなくなる
(3を0、5を1で表すとすると「3335」→「0001」と「335」→「001」の区別がつかない)
ということで、最上位に番兵をつけ次のように変換する
3335→10001
5335→11001
 335→ 1001

サンプルにある最大ケースが25桁なのでbitにすればそのまま保存できる

int main(){
	int i,j,n;
	scanf("%d",&n);
	i=1;
	while(n){
		i+=2;
		if(__builtin_popcount(i)%3==1)n--;
		//最上位に番兵がいるので、それをあわせて3の倍数+1になっていればよい
	}
	for(j=31;j>=0;j--){
		n=i>>j;
		if(n>1)putchar(n%2?'5':'3');
		//上位から0か1か調べる。出力は番兵以降
	}
	return 0;
}

これを縮めて

n,j=31;
main(i){
	for(scanf("%d",&n);n-=__builtin_popcount(i+=2)%3==1;);
	for(;j--;)(n=i>>j)>1&&putchar(51+n%2*2);
	exit(0);
}

118B
exit(0)をつけないとRE、悲しい

(2016/05/29追記)
for文に空きがあるんだからカッコを付けないほうが短い

n,j=31;
main(i){
	for(scanf("%d",&n);n-=__builtin_popcount(i+=2)%3==1;);
	for(;j--;n>1&&putchar(51+n%2*2))n=i>>j;
	exit(0);
}

117B