yukicoder : No.1635 Let’s Sort Integers!!

シンプルな問題。
https://yukicoder.me/problems/no/1635

問題

整数N,Kが与えられる。
1～NのPermutation Pに対し、f(P) = (隣接要素の差の絶対値)の総和 とする。
f(P)=KとなるPを構築せよ。

解法

f(P)の最小値は、Pとして1～Nを並べた場合の(N-1)である。
f(P)の最大値は、凡そN/2未満と以上の要素を交互に並べたものである。

Kがこの最小値と最大値の間の場合、実際に構築可能であることを示す。

• KがN(N-1)/2以下の場合
  • Pとして、1→N→2→N-1→…と順に末尾に追加することを考える。ただし、途中でf(P)がKを超えそうな場合、その値をスキップする。
  • 最終的にスキップされた値は、1→Nの間に昇順で挿入すれば、f(P)を変えることがない。
• KがN(N-1)/2を超える場合
  • Nが偶数でN=2mと置ける場合、f(P)が最大となるP=[(m+1),1,(m+2),2,....,2m,m]を考える。 末尾のmとm+iをswapすると、f(P)をiだけ小さくすることができる。
  • 奇数の場合も同じような感じ。

ll N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	ll mi=N-1;
	ll ma=0;
	if(N%2==0) {
		ma=(N/2+1+N)*(N/2)-(N/2+1);
		ma-=(1+N/2)*(N/2)-N/2;
	}
	else {
		ma=(N/2+2+N)*(N/2)-(N/2+2)+N/2+1;
		ma-=(1+N/2)*(N/2);
	}
	
	if(K>=mi&&K<=N*(N-1)/2) {
		vector<int> A,B,C,D;
		for(int L=1,R=N;L<=R;) {
			C.push_back(L++);
			if(L<=R) C.push_back(R--);
		}
		FORR(c,C) {
			if(A.empty()) {
				A.push_back(c);
			}
			else {
				if(abs(c-A.back())<=K) {
					K-=abs(c-A.back());
					A.push_back(c);
				}
				else {
					D.push_back(c);
				}
			}
		}
		cout<<A[0];
		sort(ALL(D));
		FORR(d,D) cout<<" "<<d;
		FORR(a,A) if(a!=1) cout<<" "<<a;
		cout<<endl;
		return;
	}
	else if(K>=mi&&K<=ma) {
		vector<int> R;
		if(N%2==0) {
			
			FOR(i,N/2) {
				R.push_back(N/2+1+i);
				R.push_back(1+i);
			}
		}
		else {
			FOR(i,N/2) {
				R.push_back(N/2+2+i);
				R.push_back(1+i);
			}
			R.push_back(N/2+1);
		}
		ll dif=ma-K;
		swap(R[dif*2],R[0]);
		FORR(r,R) cout<<r<<" ";
		cout<<endl;
		return;
	}
	
	cout<<-1<<endl;
}

まとめ

Editorialが一見長いせいか、AC数が少ないな。