yukicoder No.566 だいたい完全二分木

○激ヤバ解法
シャッフルすれば高確率で通る

○まじめな解法
普通に完全二分木をつくると高さはK-1になる。そこで適当にいじって高さをKにする
・方針1
完全二分木を作る過程で、2と3を入れ替える。
そうすると
　2
／＼
1　3
の部分が
　3
／
1
＼
　2
または
　　3
　／
　2
／
1
となり高さが1増える。ほかの部分には影響がないのでこれにより全体の高さがKになる
・方針2
完全二分木を作る過程で、最大値2^K-1の代わりに0を入れる
そうすると
　2
／＼
1　3
の部分が
　　2
　／＼
　1　3
／
0
となり高さが1増える。
登場する数が0～2^K-2になっているので、全体に1を加えることで1～2^K-1にする

○実装について
・DFSっぽいの
自分が最初に思いついたのはこれだった。
方針1を再帰で実装する

f(n,c){
	printf("%d ",n!=2&&n!=3?n:5-n);
	if(c>=0){
		f(n-(1<<c),c-1);//左側
		f(n+(1<<c),c-1);//右側
	}
}

main(){
	int k;
	scanf("%d",&k);
	f(1<<(k-1),k-2);
}

・BFSっぽいの
完全二分木を、根に近いほうから順に配っていく
例えばK=4なら、頂点が8、その次が4,12、次が2,6,10,14、…となる
初項が2^i、公差が2^(i+1)の等差数列をなしている
方針2を実装する

main(){
	int k;
	scanf("%d",&k);
	for(int i=1<<(k-1);i;i/=2)for(int j=i;j<(1<<k);j+=i*2)printf("%d ",j);
}

・方針3
次の比較関数でソートする

c(int*a,int*b){
	int ta=*a,tb=*b;
	while(ta%2==0)ta/=2;
	while(tb%2==0)tb/=2;
	return ta-tb;
}

a[5000];
main(){
	int k;
	scanf("%d",&k);
	for(int i=0;i<(1<<k)-1;i++)a[i]=i+1;
	qsort(a,(1<<k)-1,4,c);
	for(int i=0;i<(1<<k)-1;i++)printf("%d ",a[i]);
}

この解法はtailsさんの提出をC言語に書きなおしたものである
（なおこの提出はシャッフル解でないもののなかで最短）
少しわかりにくいが、このソートにより高さ2K-1の木が得られることがKに関する帰納法で示せる。

このソートにより出力は、1,2,4,…、3,6,12,…、5,10,20,…、…となる。
初項2*i-1、公比2の等比数列からなる群数列なので、単なる二重ループで書ける。

main(){
	int k;
	scanf("%d",&k);
	for(int i=1;i<(1<<k);i+=2)for(int j=i;j<(1<<k);j*=2)printf("%d ",j);
}

これをちゃちゃっと縮める

j,k;main(i){for(k=1<<atoi(gets(&k));i<k;i+=2)for(j=i;j<k;j*=2)printf("%d ",j);}

79B
まだ縮む余地はありそう

メモ

yukicoderでゆるふわgolf

yukicoder No.566 だいたい完全二分木