読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.401 数字の渦巻き

問題はこちら
No.401 数字の渦巻き - yukicoder
えっと、2次元配列を作って、その上を指定の順番に移動していって……
ええい面倒くさい。(x,y)の位置にある数を一発で求めればそんな面倒な事をしなくて済むぞ


例えばn=6のとき下図のようになる(x,yの座標は0-basedであり、(0,0)が1)
f:id:sugarknri:20160723100731p:plain
(k,k)の数は比較的簡単に求めることができるので、そこを起点に考える
・x+y<nのとき(上図の黄色い部分)
(0,0)に入る数は1
(1,1)に入る数は、外周1周分値が大きくなっているので(0,0)より4*(n-1)大きい
(2,2)に入る数は、さらに1周分で(1,1)より4*(n-3)大きい
ということで、(i,i)に入る数をf(i)とおくと、これは階差が等差数列となる事がわかる
具体的に計算することでf(i)=(n-i)*i*4+1を得る。
k=min(x,y)とおく。(k,k)を基準に考えると
x>=yなら、f(k)から右へx-y進むのでf(k)+(x-y)
x<yなら、f(k+1)からy-x戻るのでf(k+1)+(x-y)
・x+y>=nのとき
(n-1,n-1)に入る数は2*n-1
以下、先ほどと同様の考察で(n-1-i,n-1-i)に入る数g(i)=(n-i-1)*i*4+2*n-1をえる。
k=n-1-max(x,y)と置くと
x>=yなら、g(k)からx-y戻るのでg(k)-(x-y)
x<yなら、g(k)からy-x進むのでg(k)-(x-y)

ということで以上をまとめると以下のとおり

#define max(p,q)(p>q?p:q)
#define min(p,q)(p<q?p:q)
int main(){
	int x,y,k,n,m;
	scanf("%d",&n);
	for(y=0;y<n;y++){
		for(x=0;x<n;x++){
			if(x+y<n){
				k=min(x,y);
				if(x>=y)m=(n-k)*k*4+1+(x-y);
				else m=(n-(k+1))*(k+1)*4+1+(x-y);
			}else{
				k=n-max(x,y)-1;
				m=(n-k-1)*k*4+2*n-1-(x-y);
			}
			printf("%03d ",m);
		}
		puts("");
	}
	return 0;
}

本当はnの偶奇で場合分けしてもう少し丁寧に見ないといけない気がするのだけど、これで通ったのでOK。

あとはこれをぎゅっと短縮する
とりあえず短くなるかは別として、場合分けを次のようにまとめることが出来る

k=x+y<n?min(x,y):n-max(x,y)-1;
m=(x+y>=n||x<y?n-k-1:n-k)*(x+y<n&&x<y?k+1:k)*4+(x+y>=n?2*n:0)+(x+y<n?1+x-y:y-x-1);

x+y<nが何度も登場するのでそれを適当な変数に置くことで

f=x+y<n;
k=f?x<y?x:y:n+~(x>y?x:y);
//k=fmin(f?x:n+~x,f?y:n+~y);よりも1B短い
m=(n-k-(!f|x<y))*(k+(f&x<y))*4+2*n*!f-(f?:-1)*(y+~x);

fに保存するフラグを逆にしたら縮まないかな

f=x+y>=n;
k=f?n+~(x>y?x:y):x<y?x:y;
m=(n-k-(f|x<y))*(k+(!f&x<y))*4+2*n*f+(f?:-1)*(y+~x);

同じ長さだ…… と、ここでひらめいた

f=(x+y>=n)*2;
k=f?n+~(x>y?x:y):x<y?x:y;
m=(n-k-(f||x<y))*(k+(!f&x<y))*4+n*f+~-f*(y+~x);

これで1B短縮

実際には変数mは要らないので

x,y,n,k;
main(f){
	for(scanf("%d",&n);y<n;puts(""),y++)for(x=0;x<n;x++)
		f=(x+y>=n)*2,
		k=f?n+~(x>y?x:y):x<y?x:y,
		printf("%03d ",(n-k-(f||x<y))*(k+(!f&x<y))*4+f*n+~-f*(y+~x));
}

最後にfor文圧縮

for(;y<n;puts(""),y++)for(x=0;x<n;x++)f=...,k=...,printf("%03d ",...);
for(;x<n?f=...,k=...,printf("%03d ",...),++x:(x=!puts(""),++y<n););
for(;f=...,k=...,printf("%03d ",...),++x/n?x=!puts(""),++y<n:1;);

まとめると

x,y,n,k;main(f){for(scanf("%d",&n);f=(x+y>=n)*2,k=f?n+~(x>y?x:y):x<y?x:y,printf("%03d ",(n-k-(f||x<y))*(k+(!f&x<y))*4+f*n+~-f*(y+~x)),++x/n?x=!puts(""),++y<n:1;);}

163B