yukicoder : No.2038 Strange Arrange

この構成法は典型かもなぁ。
https://yukicoder.me/problems/no/2038

問題

正整数Nが与えられる。
以下を満たす数列Xを構築せよ。

• XはN要素の数列で、各要素は1～9の整数値を取る。
• 隣接要素は異なる値を取る。X[i]=X[j]ならX[i]＜X[i+j]

解法

X[i] := iの2進数表記において、Trailing Zeroの数+1
とすると上記条件を満たす。

int N;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		x=i+1;
		y=0;
		while((x&(1<<y))==0) y++;
		cout<<y+1;
	}
	cout<<endl;
}

まとめ

この構築法時々出てくるよね。