メモ

yukicoderでゆるふわgolf

yukicoder No.689 E869120 and Constructing Array 3

問題はこちら
No.689 E869120 and Constructing Array 3 - yukicoder

バラバラに考えれば良さそう
つまりa+b,c+d,e+f,……はそれぞれ素数だが、それ以外の組み合わせは素数にならないようなものを構成することを考える。
そのようなものが作れれば、それらをそれぞれA,B,C,……個使った時に全体でA*B+C*D+E*F+……個の対が素数になる。
長さを小さくしたいので、A==Bなどのケースのみ調べると、N≦250の制約をギリギリ満たすことが確かめられる(最大は9993のときの242)
(A==B+1などのケースも使うことにすれば9998のときのN=226が最大になる)

#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

int isp(ll n){
	for(ll i=2;i*i<=n;i++)if(n%i==0)return 0;
	return 1;
}

ll a[2][50];
maekeisann(){
	a[0][0]=3;
	a[1][0]=2;
	ll cnt=1;
	for(ll c=3;c<1000;c++)if(isp(c+c+1)){
		int f=1;
		rep(i,0,cnt)if(isp(c+  a[  c%2][i]))f=0;
		rep(i,0,cnt)if(isp(c+1+a[1-c%2][i]))f=0;
		if(f){
			a[0][cnt]=c%2?c:c+1;
			a[1][cnt]=c%2?c+1:c;
			cnt++;
		}
	}
}

ll ans[50],len,n;
f(ll k){
	if(k==0)return 0;
	ll temp=sqrt(k);
	k-=temp*temp;
	ans[len++]=temp;
	n+=temp;
	f(k);
}

main(){
	maekeisann();
	ll k;
	scanf("%lld",&k);
	f(k);
	printf("%d\n",n*2);
	rep(i,0,len)rep(j,0,ans[i])printf("%lld %lld ",a[0][i],a[1][i]);
}

この方針でゴルフをするのは無理なのでプロの方針をパクろう。
a=3,b=4,c=5,d=6とすると、求める答えはA*B+C*D。A+B+C+D≦250の下で10000以下の任意の数が作れるらしい。
まずはこれを素直に書く

t,a,b,c,d;
main(k){
	scanf("%d",&k);
	for(a=0;a<250;a++)for(b=0;b<250;b++)for(c=0;c<250;c++)for(d=0;d<250;d++)if(a+b+c+d<250&&a*b+c*d==k){
		for(t=0;t<=a+b+c+d;t++)printf("%d ",t?t>a?t>a+b?t>a+b+c?6:5:4:3:a+b+c+d);
		return 0;
	}
}

それから

	for(scanf("%d",&k);a<250;a++)for(b=0;b<250;b++)for(c=0;c<250;c++)for(d=0;d<250;t?exit(0):d++)for(;a+b+c+d<250&&a*b+c*d==k&&t<=a+b+c+d;t++)printf("%d ",t?t>a?t>a+b?t>a+b+c?6:5:4:3:a+b+c+d);
//こうして
	for(scanf("%d",&k);a+b+c+d>250|a*b+c*d!=k|t>a+b+c+d?t?exit(0),1:++d>250?d=0,++c>250?c=0,++b>250?b=0,++a<250:1:1:1:printf("%d ",t?t>a?t>a+b?t>a+b+c?6:5:4:3:a+b+c+d)+t++;);
//こうじゃ

ということで

t,a,b,c,d;main(k){for(scanf("%d",&k);a+b+c+d>250|a*b+c*d!=k|t>a+b+c+d?t?exit(0),1:++d>250?d=0,++c>250?c=0,++b>250?b=0,++a<250:1:1:1:printf("%d ",t?t>a?t>a+b?t>a+b+c?6:5:4:3:a+b+c+d)+t++;);}

189B

2018/07/01追記
ループの範囲は99未満で大丈夫らしい
対称性からb≦a、c<a、d≦cを仮定して良いのでループの向きを逆にすることでループ終了条件を短くするいつものテク

t,a,b,c,d;main(k){for(scanf("%d",&k);a+b+c+d>250|a*b+c*d-k|t>a+b+c+d?t?exit(0),1:d--||(d=c--)||(c=a,b--)||(b=a++)<99:printf("%d ",t?t>a?t>a+b?t>a+b+c?6:5:4:3:a+b+c+d)+t++;);}

174B

2018/07/03追記
d=1に固定してもよいらしいのでループが1つ減る
答えは必ず存在するのでaに関するループ終了条件は不要

t,a,b,c;main(k){for(scanf("%d",&k);a+b+c>249|a*b+c-k|t>a+b+c+1?t?exit(0),1:c--||(c=b--)||(b=++a):printf("%d ",t?t>a?t>a+b?t>a+b+c?6:5:4:3:a+b+c+1)+t++;);}

さらに

c--||(c=b--)||(b=++a)
//境界条件が微妙に変わるが次のように書き換えてもOK
c--||(c=b=b?b-1:++a)
c--||(c=b=--b?:++a)

ということで

k,t,a,c;main(b){for(scanf("%d",&k);a+b+c>249|a*b+c-k|t>a+b+c+1?t?exit(0),1:c--||(c=b=--b?:++a):printf("%d ",t?t>a?t>a+b?t>a+b+c?6:5:4:3:a+b+c+1)+t++;);}

152B
さらにジャッジコードを読むと、最後に余分な出力があっても構わないことが分かるので

k,t,a,c;main(b){for(scanf("%d",&k);a+b+c>249|a*b+c-k|t>260?t?exit(0),1:c--||(c=b=--b?:++a):printf("%d ",t?t>a?t>a+b?t>a+b+c?6:5:4:3:a+b+c+1)+t++;);}

として148B

2018/07/12追記
頭がついてない

k,t,a,c;main(b){for(scanf("%d",&k);a+b+c>249|a*b+c-k|t>260?c--||(c=b=--b?:++a,!t):printf("%d ",t?t>a?t>a+b?t>a+b+c?6:5:4:3:a+b+c+1)+t++;);}

139B

yukicoder No.688 E869120 and Constructing Array 2

問題はこちら
No.688 E869120 and Constructing Array 2 - yukicoder

明らかに並び順には依存せず、0と1の個数のみで決まることがわかる。
1がi個、0がj個あるとき、和が2になる部分集合はi*(i-1)/2*pow(2,j)個あるので、i,jを全探索する

main(){
	int k;
	scanf("%d",&k);
	for(int i=1;i<=30;i++)for(int j=0;i+j<=30;j++){
		if(i*(i-1)/2<<j==k){
			printf("%d\n",i+j);
			for(int t=0;t<i+j;t++)printf("%d ",t<i);
			exit(0);
		}
	}
}

これを縮める。

//printfをまとめる(スペシャルジャッジなので改行と空白を区別しなくて良い)
for(scanf("%d",&k);j>29?j=0,++i<31:1;j++)if(i*~-i/2<<j==k){for(;t<=i+j;t++)printf("%d ",t?t>j:i+j);exit(0);}
//ifを消す
for(scanf("%d",&k);j>29?j=0,++i<31:1;t?exit(0):j++)for(;i*~-i/2<<j==k&&t<=i+j;t++)printf("%d ",t?t>j:i+j);
//for文をまとめる
for(scanf("%d",&k);i*~-i/2<<j==k&&t<=i+j?printf("%d ",t?t>j:i+j)+t++:(t?exit(0):j++,j>29?j=0,++i<31:1););
//真偽入れ替え
for(scanf("%d",&k);i*~-i/2<<j!=k|t>i+j?t?exit(0):j++,j>29?j=0,++i<31:1:printf("%d ",t?t>j:i+j)+t++;);
//次のように書き換えると、exit(0)がvoidなのでCE
for(scanf("%d",&k);i*~-i/2<<j!=k|t>i+j?t?exit(0):++j>29?j=0,++i<31:1:printf("%d ",t?t>j:i+j)+t++;);
//これなら通るが長さは同じ
for(scanf("%d",&k);i*~-i/2<<j!=k|t>i+j?t?exit(0),1:++j>29?j=0,++i<31:1:printf("%d ",t?t>j:i+j)+t++;);

ということで完成品は以下

t,j,k;main(i){for(scanf("%d",&k);i*~-i/2<<j!=k|t>i+j?t?exit(0),1:++j>29?j=0,++i<31:1:printf("%d ",t?t>j:i+j)+t++;);}

116B

2018/07/12追記
自明に縮むし頭悪すぎか??

t,j,k;main(i){for(scanf("%d",&k);i*~-i/2<<j!=k|t>i+j?++j>29?j=0,!t&++i<31:1:printf("%d ",t?t>j:i+j)+t++;);}

107B

yukicoder No.668 6.0*10^23

問題はこちら
No.668 6.0*10^23 - yukicoder

桁上りなどに気をつけて、3桁目を四捨五入するコードを書く

char s[1000010];
int main(){
	gets(s);
	int s0=s[0]-48;
	int s1=s[1]-48;
	int s2=s[2]-48;
	int n=strlen(s)-1;
	
	if(s2>=5)s1++;
	if(s1>9){
		s1=0;
		s0++;
	}
	
	if(s0>9)printf("1.0*10^%d",n+1);
	else printf("%d.%d*10^%d",s0,s1,n);
}

これを素直に縮めるとこう

char s[1<<17];
main(f){
	gets(s);
	s[2]>52?++s[1]>57?s[1]=48,++*s>57?*s=49,f=0:0:0:0;
	printf("%c.%c*10^%d",*s,s[1],strlen(s)-f);
}

123B
配列をとらずに入力を1Bずつ読むとむしろ長くなる

a,b,c,t;
main(f){
	for(;read(0,&t,1);)++c<3?a=b,b=t:c<4?t>52?++b>57?b=48,++a>57?a=49,f=0:0:0:0:0;
	printf("%c.%c*10^%d",a,b,c+~f);
}

125B

よく考えると、出力すべき「a.b*10^c」の「a.b」のところは%.1fでいけそうじゃない?

c;
float s,z=1;
main(t){
	for(;read(0,&t,1);z*=.1)c++<3?s+=(t-48)*z:0;
	printf("%.1f*10^%d",s,s>9.95?s/=10,c-1:c-2);
}

しかしこれは「3350」などで丸めに失敗し「3.3*10^3」と出力されてしまう。
じゃあ4桁読めばいいじゃん、とc++<3をc++<4に変えると、今度は「335」などで改行を読み込んでしまい困る。
「4桁目以降は全て1」と思うことにしてc++<3?s+=(t-48)*z:0;の最後の0をs+=c++<3?(t-48)*z:z;とzに取り替えるとうまくいく。

c;
float s,z=1;
main(t){
	for(;read(0,&t,1);z*=.1)s+=c++<3?(t-48)*z:z;
	printf("%.1f*10^%d",s,s>9.95?s/=10,c-1:c-2);
}

111B

2019/03/16追記
c-1,c-2なんて、いかにも「cをmainの引数にしてください」という感じがする

t;
float s,z=1;
main(c){
	for(;read(0,&t,1);z*=.1)s+=c-->-2?(t-48)*z:z;
	printf("%.1f*10^%d",s,s>9.95?s/=10,-c:~c);
}

yukicoder No.677 10^Nの約数

問題はこちら
No.677 10^Nの約数 - yukicoder

約数は2^i*5^jの形をしている。全て求めてソートすればよい。
ここでは約数を保存せず、毎回「今まで出力したものより大きい最小のもの」を探すようにしている。O(N^4)

main(){
	int n;
	scanf("%d",&n);
	long M=0;//直前に出力したもの
	for(int cnt=0;cnt<(n+1)*(n+1);cnt++){
		//約数は全部で(n+1)*(n+1)個
		long m=2e18;//Mより大きな最小の約数(=次に出力するもの)
		for(int i=0;i<=n;i++)for(int j=0;j<=n;j++){
			long t=pow(2,i)*pow(5,j);
			if(t>M&&t<m)m=t;
		}
		printf("%ld\n",m);
		M=m;
	}
}

まずざっと縮める

long M,m,t;i,j,x;
main(n){
	for(scanf("%d",&n);x++<~n*~n;printf("%ld\n",M=m))
		for(m=2e18,i=0;i<=n;i++)for(j=0;j<=n;j++)(t=(t=pow(5,j))<<i)>M&t<m?m=t:0;
}

for文をまとめる

for(m=2e18,i=0;i<=n;i++)for(j=0;j<=n;j++)(t=(t=pow(5,j))<<i)>M&t<m?m=t:0;
for(m=2e18,i=0;j<=n?(t=(t=pow(5,j++))<<i)>M&t<m?m=t:1:(j=0,i++<n););
for(m=2e18,i=0;j>n?j=0,i++<n:(t=(t=pow(5,j++))<<i)>M&t<m?m=t:1;);

もう1つのfor文をまとめても短くならなかった

long M,m,t;i,j,x;main(n){for(scanf("%d",&n);x++<~n*~n;printf("%ld\n",M=m))for(m=2e18,i=0;j>n?j=0,i++<n:(t=(t=pow(5,j++))<<i)>M&&t<m?m=t:1;);}
long M,m=1,t;i,j,x;main(n){for(scanf("%d",&n);j>n?j=0,i++>=n?i=!printf("%ld\n",M=m),m=2e18,++x<~n*~n:1:(t=(t=pow(5,j++))<<i)>M&&t<m?m=t:1;);}

何れにせよ140B