メモ

yukicoderでゆるふわgolf

yukicoder No.481 1から10

問題はこちら
No.481 1から10 - yukicoder

和を求めて55から引くのが一番簡単なように思う

int main(){
	int i,t,s=0;
	for(i=0;i<9;i++){
		scanf("%d",&t);
		s+=t;
	}
	printf("%d",55-s);
	return 0;
}

入力が昇順で与えられるので、1個ずつ読み取って、食い違いが生じた時点で終わらせる方法もある

int main(){
	int i,t;
	for(i=1;i<=9;i++){
		scanf("%d",&t);
		if(t!=i){
			printf("%d",i);
			return 0;
		}
	}
	puts("10");
	return 0;
}

答えが10になるとき、10回目のscanfは失敗してtの値が9のままであることを利用すれば最後の場合分けが要らなくなる

int main(){
	int i,t;
	for(i=1;i<=10;i++){
		scanf("%d",&t);
		if(t!=i){
			printf("%d",i);
			return 0;
		}
	}
}

ということでこの方針で縮めてみた

n;main(c){for(;scanf("%d",&c),++n==c||!printf("%d",n););}

RE
じゃあ最後までループを回すことにしよう

n;main(c){for(;~scanf("%d",&c);)++n-c&&printf("%d",n=c);}

RE
仕方がないのでとりあえずmain再帰で書くことにした

n;main(c){scanf("%d",&n);n-c?n=!printf("%d",c):main(c+1);}

58B

さて、現時点での最短コードを見ると、どうやら文字列のまま処理しているようだ
例えば1が欠けているとき、入力の文字コードの合計は、空白が8つ、改行が1つ、'0'~'9'が各1つで791になる

欠けている数 入力の文字コードの合計
1 791
2 790
9 783
10 743

9までは792から合計を引けば求まるが、10では余分に39減っている。
39……ということは13で剰余を取ればうまくいくな!

欠けている数 入力の文字コードの合計 mod 13
1 11
2 10
9 3
10 2

ということでこれを実装してこう

x;main(c){for(;read(0,&c,1);)x+=c;x=!printf("%d",12-x%13);}

59Bとなり、main再帰に1B及ばず。


2017/07/29追記
変数の役割を入れ替えることで1B短縮
コンパイラのバージョンアップによる3Bと合わせて4B短縮

c;main(n){scanf("%d",&n);n-++c?printf("%d",c):main();}

54B

yukicoder No.480 合計

問題はこちら
No.480 合計 - yukicoder


和の公式を使う。Nが小さいので1~Nまでをそのまま足しても間に合う

int main(){
	int n;
	scanf("%d",&n);
	printf("%d",n*(n+1)/2);
	return 0;
}

ゴルフ的にも特に工夫の余地はなく

n;main(){n=scanf("%d",&n)>printf("%d",n*-~n/2);}

48B

yukicoder No.424 立体迷路

問題はこちら
No.424 立体迷路 - yukicoder

標準的な迷路を解く問題にちょっとだけ条件が加わったもの。
素直なDFS/BFSで解ける。以下はDFS

char s[99][99];
int a[99][99],h,w;
//(x,y)に到達可能かをa[x][y]に保存
void f(int p,int q){
	if(!a[p][q]){
		a[p][q]++;
		//はしごを縦に使う場合
		if(p>0  &&abs(s[p-1][q]-s[p][q])<2)f(p-1,q);
		if(p<h-1&&abs(s[p+1][q]-s[p][q])<2)f(p+1,q);
		if(q>0  &&abs(s[p][q-1]-s[p][q])<2)f(p,q-1);
		if(q<w-1&&abs(s[p][q+1]-s[p][q])<2)f(p,q+1);
		//はしごを横に使う場合
		if(p>1  &&s[p-2][q]==s[p][q]&&s[p][q]>s[p-1][q])f(p-2,q);
		if(p<h-2&&s[p+2][q]==s[p][q]&&s[p][q]>s[p+1][q])f(p+2,q);
		if(q>1  &&s[p][q-2]==s[p][q]&&s[p][q]>s[p][q-1])f(p,q-2);
		if(q<w-2&&s[p][q+2]==s[p][q]&&s[p][q]>s[p][q+1])f(p,q+2);
	}
}
int main(){
	int sx,sy,gx,gy,i;
	scanf("%d%d%d%d%d%d ",&h,&w,&sx,&sy,&gx,&gy);
	//配列のindexは0-basedで、入力は1-basedなのでそろえる
	sx--;sy--;gx--;gy--;
	for(i=0;i<h;i++)gets(s[i]);
	f(sx,sy);
	puts(a[gx][gy]?"YES":"NO");
	return 0;
}

とりあえず縮めてみる。入力の受け取りを2-basedにすることで、添え字の範囲外チェックを省略する
またaをsをまとめる

char s[199][99];a,b;
f(p,q){s[p+98][q]++||(/*何かいい感じに*/);}
main(i,x,y){
	for(scanf("%*d%*d%d%d%d%d ",&a,&b,&x,&y);gets(s[++i]+2););
	f(a+1,b+1);
	a=!puts(s[x+99][y+1]?"YES":"NO");
}

ということでメインの処理の部分をなんかいい感じにする必要がある
次に見る方向を(n,m)とすると(つまり(n,m)は(-1,0),(1,0),(0,-1),(0,1)のいずれか)

//はしごを縦に使う場合
if(abs(s[p+n][q+m]-s[p][q])<2)f(p+n,q+m);
//はしごを横に使う場合
if(s[p+n+n][q+m+m]==s[p][q]&&s[p][q]>s[p+n][q+m])f(p+n+n,q+m+m);

と書くことができるので、この部分をdefineでまとめて

#define g(n,m)abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m),
char s[199][99];
f(p,q,t){s[p+98][q]++||(g(-1,0)g(1,0)g(0,-1)g(0,1)1);}
main(i,a,b,x,y){
	for(scanf("%*d%*d%d%d%d%d ",&a,&b,&x,&y);gets(s[++i]+2););
	f(a+1,b+1);
	n=!puts(s[x+99][y+1]?"YES":"NO");
}

そういえば、こういう風に回転して考えるのは以前にもやったことがあって、(n,m)→(m,-n)という風に値を更新していくことによってまとめることができる

//before
#define g(n,m)abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m),
f(p,q,t){s[p+98][q]++||(g(-1,0)g(1,0)g(0,-1)g(0,1)1);}
//after
#define G,abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m),t=n,n=m,m=-t
f(p,q,t){s[p+98][q]++||(1 G G G G);}

同じ処理をするのにdefineをするのはあほらしいので、for文にまとめてしまいたい

f(p,q,t,T,n,m){n=1;m=0;if(s[p+98][q]++)for(T=0;T++<4;t=n,n=m,m=-t)abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m));}
f(p,q,t,T,n,m){n=1;m=0;for(T=4*!s[p+99][q]++;T--;t=n,n=m,m=-t)abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m);}

dfsの途中で自身を呼び出すことがあるので、これを次のようには書けない

for(;s[p+98][q]++<4;)

さらによく考えると、一度fを呼んだとき、その関数内で(n,m)→(m,-n)の変換がおこなわれる回数は0回か4回なので、n,mはグローバル変数にしてしまって問題ない

また、indexを2-basedではなく1-basedにすると、s[-1][*]にアクセスしてしまうことになるが、実際に提出してみるとエラーは起こらないらしい
ということでここまでをいったんまとめるとこうなる

char s[199][99];
n=1,m;
f(p,q,t,T){
	for(T=4*!s[p+99][q]++;T--;t=n,n=m,m=-t)
		abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),
		s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m);
}
main(i,a,b,x,y){
	for(scanf("%*d%*d%d%d%d%d ",&a,&b,&x,&y);gets(s[i++]+1););
	f(a,b);
	n=!puts(s[x+99][y]?"YES":"NO");
}

さらにfが短く書けないかを考える。隣のマスと2マス先との高さによって、はしごを縦横に使えるかを表にまとめると次のようになる。

2マス先が同じ高さ 違う高さ
隣のマスが2以上高い - -
1高い
同じ高さ
1低い 縦横
2以上低い -

ここで縦横を両方考慮する必要があるのは「2マス先が同じ高さ、かつ、隣のマスが1低い」場合のみだが、よく考えればこれは縦移動2回により2マス先に移動できるので、横移動を考慮する必要はない。
ということで次のようにすればfの呼び出しは1回で済む
・隣のマスが2以上低く、2マス先が同じ高さなら横移動
・隣のマスとの高低差が1以下なら縦移動
・どちらにも該当しなければ移動できない

abs(t=s[p][q]-s[p+n][q+m])<2&&f(p+n,q+m),s[p+n+n][q+m+m]-s[p][q]|t<0||f(p+n+n,q+m+m);
t=(t=s[p][q]-s[p+n][q+m])>1&s[p][q]==s[p+n+n][q+m+m]?2:abs(t)<2,f(p+n*t,q+m*t);
t=s[p][q],t=t-s[p+n+n][q+m+m]|(t-=s[p+n][q+m])<2?abs(t)<2:2,f(p+n*t,q+m*t);

ということで以上をすべてまとめたものが以下

char s[199][99];
n=1,m;
f(p,q,t,T){
	for(T=4*!s[p+99][q]++;T--;t=n,n=m,m=-t)
		t=s[p][q],
		t=t-s[p+n+n][q+m+m]|(t-=s[p+n][q+m])<2?abs(t)<2:2,
		f(p+n*t,q+m*t);
}
main(i,a,b,x,y){
	for(scanf("%*d%*d%d%d%d%d ",&a,&b,&x,&y);gets(s[i++]+1););
	n=f(a,b)>puts(s[x+99][y]?"YES":"NO");
}

260B

yukicoder No.413 +5,000,000pts

問題はこちら
No.413 +5,000,000pts - yukicoder

余談
サンプル出力の数がどうみても日付なのだけど、何なのかわからず気になっているので、わかる方がいましたら教えてください

(※以下は試行錯誤により解く過程を記したものです。ちゃんとした解説が読みたい方はeditionalを読んでください)
calc関数は、二次不等式t*t+t≦dを解の公式を用いて解いているので、誤差が発生しなければ正しい値を返すはず。
ということは、バグるのは誤差が発生するとき。
doubleからlong longへの変換のときの丸めが怪しそうだなと思ったので、実数の範囲での最大値がほぼ整数となるようなものであって、誤差が発生しような大きめのdについて調べてみる

#define ll long long
ll calc(ll d) {
  return (ll)((-1 + sqrt(1 + 4*d)) / 2.0);
}
int main(){
	for(ll M=1e8;M>1e8-100;M--)for(int i=-100;i<100;i++){
		//t*t+t<=dの実数の範囲での解の最大値が整数になるのは
		//dがある整数Mを用いてM*M+Mとあらわされるとき(不等式から明らか)
		ll d=M*M+M+i;
		ll ans=calc(d);
		if(ans*ans+ans>d||(ans+1)*(ans+1)+(ans+1)<=d)printf("%lld %d %d\n",M,i);
	}
	return 0;
}

これを実行してみると

100000000 -1 100000000
99999999 -1 99999999
99999998 -1 99999998
中略
99999903 -1 99999903
99999902 -1 99999902
99999901 -1 99999901

という出力が得られた。どうやらdがM*M+M-1という形で書けるときのようだ。
このときt*t+t≦dの実数の範囲での解の最大値はMよりもわずかに小さくなるので、正しい答えはM-1となるはずだが、calc関数はMを返してしまっている。

ということでM*M+M-1のような形で書ける大きな数を10万個生成する

int main(){
	long M;
	for(M=100000000;M>99900000;M--)printf("%ld\n",M*M+M-1);
	return 0;
}

これでめでたくACを得たが、解説を読むと、どうやら問題はdoubleからlong longへの変換ではなく、sqrt関数へ渡すためのlong longからdoubleの変換の方だったらしい。
doubleの精度は53bitなので、64bit整数の値を保持できるとは限らないことが問題の本質だったそうだ。

それはさておき短縮。
とくに工夫する要素はない

i=999e5;main(){for(;i++<1e8;)printf("%ld\n",~-i+1L*i*i);}

57B

yukicoder No.467 隠されていたゲーム

問題はこちら
No.467 隠されていたゲーム - yukicoder

対称性からx,yは0以上としてよい
・0手で移動可能⇔原点
・1手で移動可能⇔チェビシェフ距離がdiのいずれかと等しい
であることは明らか
それ以外の場合を考える。d=max{di}とする
(★)チェビシェフ距離がXの点に移動するにはceil(X/d)手以上かかる
(☆)2手で移動可能⇔チェビシェフ距離が2d以下
∵⇐:dによる移動のみで(0,0)→(d,y-d)→(x,y)とできる
 ⇒:★より
チェビシェフ距離が2dより大きいときは、(0,d),(d,d),(d,0)のいずれかに移動することで目的地までのチェビシェフ距離をd小さくできるので、(☆)より帰納的にceil(X/d)手で移動できることが分かる。(★)よりこれが最小。

#define max(p,q)(p>q?p:q)
int c(int*a,int*b){return*a-*b;}
int main(){
	int n,x,y,i,ans,d[99];
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",d+i);
	qsort(d,n,4,c);
	scanf("%d%d",&x,&y);
	x=max(abs(x),abs(y));

	if(x==0)ans=0;
	else if(x<=2*d[n-1]){
		ans=2;
		for(i=0;i<n;i++)if(x==d[i])ans=1;
	}
	else ans=(x+d[n-1]-1)/d[n-1];
	//ceil(x/d[n-1])=(x+d[n-1]-1)/d[n-1]
	printf("%d",ans);
	return 0;
}

場合分けをぐっと睨むと、ceil(x/d)と一致しないのは、x<dかつx≠0かつdiの中にxと一致するものがないとき、その時に限る。
なので、diの中にxと一致するものがあるかどうかをフラグfに保存すれば、全ての場合をまとめて

(x+d-1)/d+(x<d&&x&&!f)

とあらわすことができる。
いずれにせよ、diの中にmax(|x|,|y|)と一致するものがあるかどうか確認しないといけないので、入力と合わせて2回for文が必要そう……?

a[99],x,d,i;
main(f){
	for(;~scanf("%d",a+i);)x=fmax(abs(a[i++]),abs(a[i-1]));
	for(i-=2;--i;f&=x!=a[i])d=fmax(d,a[i]);
	x=!printf("%d",(x+d-1)/d+(x<d&f&&x));
}

152B

よく考えると、これも後ろから見れば簡単になるやつだから、再帰で書くと短くできそう

x,F,d,i;
f(t){~scanf("%d",&t)?f(),++i>2?d<t?d=t:0,F*=x!=t:x<(t=abs(t))?x=t:0:0;}
main(){x=!printf("%d",(f(gets(&F))&&x<d&&x)+(x+d-1)/d);}
//fの返り値がFになっていることを利用

135B