メモ

yukicoderでゆるふわgolf

yukicoder No.514 宝探し３

問題はこちら
No.514 宝探し３ - yukicoder

N=100000とおく
(0,0)及び(N,0)の2点からの距離が分かれば特定できる。
なぜなら、それぞれの点からの距離をd1,d2、宝の位置を(x,y)とすれば
x+y=d1
(N-x)+y=d2
となるので、この連立方程式を解く事により
x=(d1-d2+N)/2
y=(d1+d2-N)/2
が得られるからである。
これをそのまま実装する

x,y,d1,d2,N=100000;
main(){
	printf("0 0\n");
	scanf("%d",&d1);
	if(d1==0)return 0;
	printf("100000 0\n");
	scanf("%d",&d2);
	if(d1==2)return 0;
	printf("%d %d\n",(d1-d2+N)/2,(d1+d2-N)/2);
}

よく考えると、2回目に質問する座標は(d1,0)でもよいことがわかる（宝の位置が質問する点より左にありさえすれば、(N,0)と同じ式が得られるので）
このことに注意しつつ、あとでループの形にできるように、同じような形になるよう書き換えたのがこれ

a,b;
main(){
	fflush(!printf("%d %d\n",a-b/2,b/2));scanf("%d",&a);
	if(a)fflush(!printf("%d %d\n",a-b/2,b/2)),scanf("%d",&b);
	if(b)fflush(!printf("%d %d\n",a-b/2,b/2));
}

ループ変数iはmainの引数に入れたいので、1から始まることを考えると
(i,a,b)が(1,0,0),(2,非0,0),(3,非0,非0)の時だけscanfをし、(2,0,0),(3,非0,0)のときはscanfを実行しないように分岐したい。
これはぐっと睨むとi%2^!a^!bと書けることがわかるので次のように書ける

a,b;main(i){for(;i%2^!a^!b&&fflush(!printf("%d %d\n",a-b/2,b/2))+scanf("%d",i++%2?&a:&b););}

ここでa,bのアドレスを調べると、b,aの順に並んでいることがわかるので、scanfの引数の分岐をまとめることができる

a,b;main(i){for(;i%2^!a^!b&&fflush(!printf("%d %d\n",a-b/2,b/2))+scanf("%d",&b+i++%2););}

89B

yukicoder No.516 赤と青の風船

問題はこちら
No.516 赤と青の風船 - yukicoder

入力を読み込んで、それがBLUEかREDか判別する

char s[10];
b,r;
main(){
	for(int i=0;i<3;i++){
		scanf("%s",s);
		if(strcmp(s,"BLUE")==0)b++;
		else r++;
	}
	if(b<r)puts("RED");
	else puts("BLUE");
}

各文字列の長さが短いのでint型に読み込んでも大丈夫そう。
文字数が違うので、BLUEとREDをint型として見た時の値の大きさは大きく異なり、例えばこういうのが考えられる

s;
main(i){
	for(;gets(&i);s+=i>>30);
	puts(s>1?"BLUE":"RED");
}

ただ、もっとよく考えると、BLUEがINT_MAX/2より僅かに大きいことを利用して次のようにできる

s;
main(i){
	for(;gets(&i);s+=i);
	puts(s<0?"BLUE":"RED");
}

54B

yukicoder No.512 魔法少女の追いかけっこ

問題はこちら
No.512 魔法少女の追いかけっこ - yukicoder

追いかける側がA[i]地点にあるi番目の交差点にたどり着いた時、追いかけられる側はA[i]/X*Y地点にいる。これがA[i+1]より真に大きければ見失う。
除算をすると誤差で落とされるケースが多数あるらしいので、A[i]/X*Y≦A[i+1]をA[i]*Y≦A[i+1]*Xと変形して整数の範囲でやる

a[100],x,y,n;
main(){
	scanf("%d%d%d",&x,&y,&n);
	for(int i=0;i<n;i++)scanf("%d",a+i);
	for(int i=0;i<n-1;i++)if(a[i]*y>a[i+1]*x){
		puts("NO");
		return 0;
	}
	puts("YES");
}

前から順番に読み込めば配列はいらない

p,q,f;
main(a,b){
	for(scanf("%d%d%*d",&a,&b);~scanf("%d",&q);p=q)f|=a*q<b*p;
	puts(f?"NO":"YES");
}

94B

scanfを1つにするパターンも考えたが、Nの読み飛ばしが難しくて短くならなかった

p,q,f;main(a,b){for(scanf("%d%d%*d",&a,&b);~scanf("%d",&q);p=q)f|=a*q<b*p;puts(f?"NO":"YES");}
a,b,p,q,f;main(i){for(;~scanf("%d",&q);*(--i?~i?i+2?&p:&q:&b:&a)=q)f|=a*q<b*p;puts(f?"NO":"YES");}
a,b,p,q,f;main(i){for(;~scanf("%d",&q);~i--?i>-2?a=b,b=q:(p=q):0)f|=a*q<b*p;puts(f?"NO":"YES");}

2017/08/01追記
やっぱりscanfを1つにしたほうが短くなった

a,b,p,q,f;
main(i){
	for(;~scanf("%d",a?b?&q:&b:&a);--i+2?p=q:0)f|=a*q<b*p;
	puts(f?"NO":"YES");
}

92B

yukicoder No.509 塗りつぶしツール

問題はこちら
No.509 塗りつぶしツール - yukicoder

また、白でも黒でもない3つ目の色を赤と呼ぶことにする。
領域を「背景」「文字」「穴」の3つの領域に呼び分ける。
背景を塗りつぶすのは1回、文字をすべて塗りつぶすには文字数回、穴をすべて塗りつぶすには穴の個数回の操作が必要。

・背景を1回だけ塗りつぶす場合
背景の色は「白→黒」と変更されるので、そのとき文字の色は赤になっていなければならない。
すなわち各文字の色は2回以上変更されるので、全体では最低でも2*(文字数)+(穴数+1)回の操作が必要。
実際に「文字をすべて赤にする→背景と穴をすべて黒にする→文字をすべて白にする」という手順で最小回数を達成できる
・文字を1回だけ塗りつぶす場合
文字の色は「黒→白」と変更されるので、そのとき背景及び穴の色は赤になっていなければならない。
すなわち背景及び穴の色は2回以上変更されるので、全体では最低でも2*(穴数+1)+文字数回の操作が必要。
実際に「背景と穴をすべて赤にする→文字をすべて白にする→背景と穴をすべて黒にする」という手順で最小回数を達成できる
・背景,文字をどちらも2回以上塗りつぶす場合
最低でも2*(文字数)+(穴数)+2回の変更が必要なのでこれは1番目のパターンより必ず回数が多くなる

ということで、結局min{2*(文字数)+(穴数+1),2*(穴数+1)+文字数}が答えになることがわかる。

#define min(p,q)(p<q?p:q)
a[]={1,0,0,0,1,0,1,0,2,1};
s,h,x;
main(){
	while(1){
		x=getchar();
		if(x=='\n')break;
		s++;
		h+=a[x-'0'];
	}
	printf("%d",min(2*(h+1)+s,2*s+h+1));
}

縮める際の肝は上のコードで配列に保存していた部分をどうするか。
方針としては2通りあって、「いい感じの式をつくる」「bitでやる」
文字の入力の受取も、getchar()-10、~getchar()、read()、などいろいろ考えられるのでいい感じになるものを探す

s,x;main(h){for(;x=getchar()-10;s++)h+=3&397569>>x*2-12;printf("%d",s+h+(s<h?s:h));}
s,x;main(h){for(;x=getchar()-10;s++)h+=x/46-~x%2-!(x%8);printf("%d",s+h+(s<h?s:h));}
h,x;main(s){for(;x=~getchar();s--)h+=3&1446145>>~x*2;printf("%d",h-s+(-s<h?-s:h));}
h,x;main(s){for(;x=~getchar();s--)h-=x/57+x%2+!(x%17);printf("%d",h-s+(-s<h?-s:h));}
h,x;main(s){for(;read(0,&x,1);s--)h+=3&1446145>>x*2;printf("%d",h-s+(-s<h?-s:h));}
h,x;main(s){for(;read(0,&x,1);s--)h+=x/56-~x%2-!(x%25);printf("%d",h-s+(-s<h?-s:h));}
s,x;main(h){for(;read(0,&x,1);s++)h+=x/56-~x%2-!(x%10);printf("%d",h+--s+(s<h?s:h));}

int型に対するbitshiftはmod32で計算される仕様と'0'*2 mod 32が0であることがうまく噛み合って、bitの方が短くなった。
82B