メモ

yukicoderでゆるふわgolf

yukicoder No.693 square1001 and Permutation 2

問題はこちら
No.693 square1001 and Permutation 2 - yukicoder

数列の順序は関係ないのでソートしてから考えて良い。
1から順に作ることを考えると、小さい方から順に使うのが最適であることがわかるので、Σ|a[i]-i|が解

#define swap(p,q)(p^=q^=p^=q)
int a[99];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",a+i);
	for(int i=0;i<n;i++)for(int j=1;j<n;j++)if(a[j-1]>a[j])swap(a[j-1],a[j]);
	int s=0;
	for(int i=0;i<n;i++)s+=abs(a[i]-(i+1));
	printf("%d",s);
}

バケツソートを使うかバブルソートを使うかは悩みどころだが、バケツソートの方が短くなりそうな気がしたのでそれで実装
バブルソートの方は試してない

これを

a[99];
n,t,s,i,k;
int main(){
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&t);
		a[t]++;
	}
	for(int i=0;i<n;i++){
		while(a[k]==0)k++;
		s+=abs(k-(i+1));
		--a[k];
	}
	printf("%d",s);
}

こうじゃ

a[99],i,s;
main(k){
	for(;~scanf("%d",a)?++a[*a]:a[k]--?s+=abs(k-++i),1:++k<60;);
	printf("%d",s-1);
}

nもまとめて読み込んで、ループをn回ではなく十分大きな定数回実行している。このため答えが1ずれるので引いている。
入力の読み込みにa[0]を使うことで一時変数を削減している。(+1B-2Bで1B削減)
96B

yukicoder No.692 square1001 and Permutation 1

問題はこちら
No.692 square1001 and Permutation 1 - yukicoder

n=1かどうか判定するだけ

値を1つ見ればよいのでgets+atoiやるだけ

a;main(){puts(atoi(gets(&a)-1)?"Petr":"square1001");}

……と思ったら、scanfを使う方が短くなるらしい。
未定義動作だから何が起きてもいいとはいえ、値の評価順序はいったいどうなってるんだ……

main(n){puts(n-scanf("%d",&n)?"Petr":"square1001");}

52B

yukicoder No.683 Two Operations No.3

問題はこちら
No.683 Two Operations No.3 - yukicoder

逆向きに再帰で全探索すると解ける。

int f(long x,long y){
	if(x==0||y==0)return 1;
	int flag=0;
	if(x%2==0)flag|=f(x/2,y-1);
	if(y%2==0)flag|=f(x-1,y/2);
	return flag;
}

int main(){
	long x,y;
	scanf("%ld%ld",&x,&y);
	puts(f(x,y)?"Yes":"No");
}

現実的には探索回数は十分小さくなるらしいが、ここでは√N以下になることを示す。
（この証明はwriterに教えていただいた）
（証明）
mod 4で考える。
X,Yがともに4の倍数であるとき以外は、遷移先が一意に決まることが分かる。
また、X,Yがともに4の倍数のときは
(00,00)→(00,11)→(00,10)→(00,01)→(00,00)
(00,00)→(10,11)→(01,10)→(00,01)→(00,00)
のどちらかの遷移をたどったときその時に限り、ともに4の倍数である状態に戻ってくる。
よって、探索の枝は深さ4毎に高々2倍になる。ここで深さ1ごとにXYは1/2より小さくなるので、探索の深さは高々log2(XY)≦2log2(N)。
探索回数は高々2^(2log2(N)/4)=√Nである。
（証明終わり）
なお実際には√N=10^9どころか、せいぜい10^3程度にしかならないようである

フラグの持ち方を少し工夫して

F;
f(long x,long y){
	x&&y?x%2||f(x/2,y-1),y%2||f(x-1,y/2):F++;
}
main(){
	long x,y;
	scanf("%ld%ld",&x,&y);
	f(x,y);
	puts(F?"Yes":"No");
}

126B

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