Codeforces ECR #163 : E. Clique Partition

Fまでは割と易しめ。
https://codeforces.com/contest/1948/problem/E

問題

正整数N,Kが与えられる。
1～NのPermutation Aに対し、以下のグラフを考える。

• |i-j|+|A[i]-A[j]|≦Kである2点(i,j)の間に辺を張る

このグラフが、最小のクリークの集合となるようにしたい。
Aの具体例を求めよ。

解法

K点毎にクリークを構築するようにしよう。
A={K/2,K/2-1,...,1,K,K-1,..K/2+1,...} のように、1～Nを並べてK要素毎に、反転及び半分rotateさせればよい。

int T,N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		int nex=1;
		FOR(i,N) {
			if(i%K==0) {
				vector<int> V;
				for(j=i+1;j<=min(N,i+K);j++) V.push_back(j);
				reverse(ALL(V));
				rotate(V.begin(),V.begin()+(int)V.size()/2,V.end());
				FORR(v,V) cout<<v<<" ";
			}
		}
		cout<<endl;
		cout<<(N+K-1)/K<<endl;
		FOR(i,N) cout<<1+i/K<<" ";
		cout<<endl;
		
	}
}

まとめ

これは割とすんなり。