メモ

yukicoderでゆるふわgolf

yukicoder No.646 逆ピラミッド

問題はこちら
No.646 逆ピラミッド - yukicoder

言われたとおりに二重ループを実装するだけ

main(){
	int n;
	scanf("%d",&n);
	for(int i=n;i>0;i--){
		for(int j=0;j<i;j++)printf("%d",n);
		puts("");
	}
}

縮める。まずはささっと

i,j;
main(n){
	scanf("%d",&n);
	for(i=n;i>0;i--,puts(""))for(j=0;j++<i;)printf("%d",n);
}

頑張って縮める

for(i=n;i>0;i--,puts(""))for(j=0;j++<i;)printf("%d",n);
//for文圧縮
for(i=n;j++<i?printf("%d",n):(j=0,puts(""),--i););
//三項演算子の順序を入れ替え
for(i=n;++j>i?j=0,puts(""),--i:printf("%d",n););
//jのループを逆に
for(j=i=n;!j--?puts(""),j=--i:printf("%d",n););
//putsの返り値を使う
for(j=i=n;!j--?j=i-=puts(""):printf("%d",n););

ということで完成品がこちら

i,j;
main(n){
	scanf("%d",&n);
	for(j=i=n;!j--?j=i-=puts(""):printf("%d",n););
}

74B

yukicoder No.648 お や す み

問題はこちら
No.648 お や す み - yukicoder

1からmまでの和はm(m+1)/2になるので「m(m+1)/2=nとなるmが存在するか?」と同じ問題になる。
とりあえず誤差の問題は置いておく。
もしそのようなmが存在したとする。
√(m(m+1))=√(2n)となる。ここでm<√(m(m+1))<m+1なので、floor(√(2n))=mとなることが分かる。
結局「m=floor(√(2n))としたとき、m(m+1)/2=nとなるか?」と同じ問題であることが分かる。
(答えがNOの時はどのようなmに対してもm(m+1)/2=nは成り立たないので、これでよい)
さて、誤差を考える。つまり、floor(√(2n))が正しく求まるかどうかを考える。
真の答えがNOである時に誤ってYESと答えることはない(どのようなmに対してもm(m+1)/2=nは成り立たないので)
真の答えがYESである時を考える。
このとき√(2n)はm+0.5くらいになるので、n<2*10^18つまりm<2*10^9だと相対誤差10^-10≒2^-34くらいまでは許される。
2nをdoubleにキャストするとき、平方根を計算するときに発生する誤差はそれぞれ高々2^-52程度なので、これは結果に影響を与えない。
よって誤差が影響を及ぼすことはない。

long n,m;
main(){
	scanf("%ld",&n);
	m=sqrt(2*n);
	if(m*(m+1)/2==n)printf("YES\n%d",m);
	else printf("NO");
}

ぎゅっとする

long n,m;
main(){
	scanf("%ld",&n);
	printf(n+m*~m/2?"NO":"YES\n%d",m=sqrt(2*n));
}

77B

yukicoder No.638 Sum of "not power of 2"

問題はこちら
No.638 Sum of "not power of 2" - yukicoder

考察により、答えは次のようになることがわかる
・Nが1,2,3,4,5,7のとき-1
・N-3が2ベキでないときa=3,b=N-3
・N-5が2ベキでないときa=5,b=N-5
正当性を示す。
2ベキでない最小の数は3、2番目に小さい数は5なので、1,2,3,4,5,7がダメなのは明らか。
よって「N≠1,2,3,4,5,7のとき、N-3とN-5がともに2ベキになることはない」を示せば良い。
差が2であるような2ベキの組は2,4しかなく、N≧8よりN-5>2、N-3>4であるから、これに該当することはない。

N-3が2ベキであるかどうかはpopcntが1であるかどうかを見れば良い

main(){
	long n;
	scanf("%ld",&n);
	if(n<=5||n==7)puts("-1");
	else if(__builtin_popcountl(n-3)!=1)printf("3 %ld",n-3);
	else printf("5 %ld",n-5);
}

ところで、popcntを自前で実装するときの有名テクとして次のようなものがある

int popcnt(int n){
	int count=0;
	while(n){
		count++;
		n&=n–1;
	}
	return count;
}

実はn&n-1により、nにおいて1になっている一番下のbitを消すことができる。
ということでpopcntを使わなくても、n-3&((n-3)-1)が0かどうかを見れば良いことが分かる。

long n;
main(m){
	scanf("%ld",&n);
	m=n-3&n-4?3:5;
	printf(n>5&&n-7?"%d %ld":"-1",m,n-m);
}

83B

yukicoder No.643 Two Operations No.2

問題はこちら
No.643 Two Operations No.2 - yukicoder

いろんな解説が出来て楽しいのでいろいろ紹介
偏角を見る
座標平面(X,Y)の点との対応を考える。偏角をθとする。
操作によりθ=45°とすることが目的である。
操作1は直線Y=Xでの対称移動であり、操作2は直線Y=(tan22.5°)Xでの対称移動となる。
よって操作1によりθは90°-θに移り、操作2によって45°-θに移る。
これらの操作ではmod 45°でθまたは-θにしか移らないことから、θ=0 mod 45°であることが必要。
そのような(X,Y)の組は(X,0),(X,X),(0,X),(X,-X)の4種しかないので、具体的に確かめることができる。

○線形変換のなす部分群を考える
A=\left(\begin{array}{cc}0&1\\1&0\end{array}\right),\ B=\left(\begin{array}{cc}1&1\\1&-1\end{array}\right)とおく。
操作1はAに、操作2はBに対応する線形変換である。
A,Bが生成するGL(2,\mathbb{R})の部分群を定数倍で割ったもの、< A,B >/\lambda Iを考える。
(以下、行列は定数倍で割った同値類で考えるものとする)
AA=I,\ BB=I,\ ABAB=BABAが成り立つことがわかるので、
< A,B >/\lambda I=\{I,A,B,AB,BA,ABA,BAB,ABAB\}となることがわかる。よってこれらを具体的に計算することで求めることができる。

○射影空間へうつす
X=Y=0なら明らか。そうでないとする。
操作1をf、操作2をgと書く。またα(X,Y)=X/Yとおく。
1/0=∞、1/∞=0など適当な演算を定める。ただし∞は正負を区別しない(要するにαはR^2\{0}からP^1への自然な写像
関数の合成について
αf=1/α、αgg=α、αgf=-αg
となることが計算により確かめられるので、f,gの操作を行って得られるものは
±α、±1/α、±αg、±1/αgのみであることがわかる。
よってこれらのいずれかが1となるためにはα(X,Y)=±1またはα(X+Y,X-Y)=±1が必要。
これらについては具体的に考えることができる。

main(){
	scanf("%d%d",&x,&y);
	if(x==y)puts("0");
	else if(y==0)puts("1");
	else if(x==0)puts("2");
	else if(x==-y)puts("3");
	else puts("-1");
}

はい

main(x,y){
	scanf("%d%d",&x,&y);
	printf("%d",x-y?y?x?x+y?-1:3:2:1:0);
}

67B

yukicoder No.642 Two Operations No.1

問題はこちら
No.642 Two Operations No.1 - yukicoder

逆にやる。即ち問題を次のように読み替える
「X=Nから始めて次の操作でX=1に出来るか? 出来るならば最小操作回数を答えよ
操作1:Xを1増やす
操作2:Xが偶数のとき2で割る」
まず、Xが偶数なら操作2によりX/2に、Xが奇数なら操作1+操作2により(X+1)/2に変換することができるので、X≧2に対しては、Xを小さくすることができる。
つまりどのようなXから始めても必ず1にすることができる。
次に最小回数を考える。
Xが奇数のときは操作1をするしかない。
Xが偶数のときは操作2をするのが最適である。
なぜならもし操作1をした場合、再び操作1をするしか無く、(値が小さくなるのは操作2を行った時のみなので)それ以降のある時点で操作2を行うことになる。
つまりあるK≧1が存在して「操作1を2K回行う→操作2を行う」という流れになるが、これは「操作2を行う→操作1をK回行う」と同じであり、こちらのほうが操作回数が少ないので、そのようなものは考慮しなくてよい。

editorialにある次の主張を証明する。
主張:N−1 を2進数にしたときの桁数と 0 の個数の和が答えとなる
K-1 を2進数にしたときの桁数と 0 の個数の和」をf(K)とし、先ほど同様、元とは逆の問題を考える。
f(1)=0なので、操作を1回行う毎にf(X)の値が1小さくなることを言えば良い。示すべきは次の2つ
その1:Kが奇数のときf(K+1)=f(K)-1
その2:f(K)=f(2K)-1
・その1について
K-1は偶数なので、K-1の最下位を0から1に変更するとKになる。
これにより桁数は変わらず、0の個数が1減るのでf(K+1)=f(K)-1となる。
・その2について
2K-1=2(K-1)+1なので、2K-1の最下位の1を削除することでK-1になる。
これにより桁数が1減り、0の個数は変わらないのでf(K)=f(2K)-1となる。
以上より示せた。

s;
main(n){
	scanf("%d",&n);
	while(n>1){
		s+;
		if(n%2)n++;
		else n/=2;
	}
	printf("%d",s);
}

やるだけ

s;
main(n){
	for(scanf("%d",&n);n>1;s++)n+=n%2?:-n/2;
	printf("%d",s);
}

66B