Codeforces #275 Div1 A. Diverse Permutation

CF275に参加。ABをさっさと解いたうえで2Hackし、レート上昇。
Cは大量にTLEが発生して結構落ちたようだ。
自分も計算量的に通せないことがわかって出してしまった。
http://codeforces.com/contest/482/problem/A

問題

正の整数N,Kが与えられる。
1～NのpermutationであるP[i]から、隣接項の差分の絶対値を取った数列Q[i]=|P[i+1]-P[i]|を考える。
Qに登場する整数がちょうどK種類となるようなP[i]を答えよ。

解法

1→N→2→N-1→3→… と作っていくと、差がN-1、N-2、N-3…とそれぞれ異なる数値が作れる。
異なる数値を(K-1)個まで作ったら、残りの数値を昇順または降順に並べて差を1とするようにすればよい。

ll N,K;
int LB,UB;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	LB=1;UB=N;
	FOR(i,K) {
		if(i%2==0) _P("%d ",LB++);
		else _P("%d ",UB--);
	}
	if(K%2==0) {
		for(i=UB;i>=LB;i--) _P("%d ",i);
	}
	else {
		for(i=LB;i<=UB;i++) _P("%d ",i);
	}
	_P("\n");
}

まとめ

こういうconstructiveな問題、CFらしいよね。