メモ

yukicoderでゆるふわgolf

yukicoder No.313 π

問題はこちら
No.313 π - yukicoder

円周率を20万桁目まで正しく計算するプログラムを書く問題……ではない
「0~9の各数字が何回登場するか」がわかれば、どこの値が間違っているかわかる
幸いsample1.txtに、整数部以外の20万桁は正しいものがおいてあるので、これを保存して数える

int main(){
	int i,p,q
	int a[10]={20104,20063,19892,20011,19874,20199,19898,20163,19956,19841};
	//a[i]はiが登場する回数
	char s[200010];
	gets(s);
	for(i=0;s[i];i++)if(i!=1)a[i-'0']--;
	for(i=0;;i++)if(a[i]==-1){p=i;break;}
	//a[i]==-1⇔iの登場が1回多い
	for(i=0;;i++)if(a[i]==1){q=i;break;}
	//a[i]==1⇔iの登場が1回少ない
	printf("%d %d",p,q);
	return 0;
}

うん長い…。とくにaの配列
「正しい」「1多い」「1少ない」さえ判別できればいいのだから、3での剰余を保存しとけば十分じゃね?

a[10]={1,2,2,1,2,0,2,0,0,2},j;
main(i){
	for(;read(0,&i,1);)i>47&&a[i-48]--;
	for(;i=a[j]%3+2;j++);
	for(;~a[i]%3;i++);
	j=!printf("%d %d",i,j);
}

他の剰余も試してみよう。5で割ると後ろ2つが1になるから、保存する値を1ずらせば省略できる

a[10]={3,2,1,0,3,3,2,2},j;
main(i){
	for(;read(0,&i,1);)i>47&&a[i-48]--;
	for(;i=a[j]%5;j++);
	for(;a[i]%5+2;i++);
	j=!printf("%d %d",i,j);
}

読み込み部分は '.' bitand 15 が14になることを使えばa[i&15]--と略せる
また読み込み終了時にi≧48であることを使うと

a[99]={3,2,1,0,3,3,2,2},j;
main(i){
	for(;read(0,&i,1);)a[i&15]--;
	for(;a[j]%5;j++);
	for(;a[--i]%5+2;);
	//a[14]は-1になっているので影響を与えない
	j=!printf("%d %d",i,j);
}

これにループ圧縮を施して

a[99]={3,2,1,0,3,3,2,2},j;
main(i){
	for(;read(0,&i,1)?a[i&15]--,1:a[j]%5?++j:a[--i]%5+2;);
	j=!printf("%d %d",i,j);
}

112B

2016/10/20追記
decじゃなくてincにすれば,1が省略できる
さらに最後の出力をfor文の中に放り込んでもREにはならないらしい

a[99]={2,3,4,0,2,2,3,3},j;
main(i){for(;read(0,&i,1)?++a[i&15]:a[j]%5?++j:a[--i]%5-2?:!printf("%d %d",i,j););}

109B