メモ

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