AtCoder ARC #144 : C - K Derangement

良くもなく悪くもなく。
https://atcoder.jp/contests/arc144/tasks/arc144_c

問題

正整数Nと非負整数Kが与えられる。
1～NのPermutation Aのうち、|A[i]-i|≧Kを満たすもので辞書順最小のものを求めよ。

解法

Nが2K以上の場合、条件を満たすことが可能である。

そこでNが4K以上の場合を考える。
先頭のK要素に(K+1)～2K、次のK要素に1～Kを置けば、これは明らかに先頭2K要素は辞書順最小だし、残りN-2K要素は何かしら置ける。
よってこの場合先頭2K要素を確定させ、以後(N-2K)要素の問題を考えればよくなる。

残りは要素数が3K以下の場合と3K+1以上4K未満の場合で分けて考え、貪欲に詰め込んでいけばよい。

int N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	vector<int> V;
	/*
	FOR(i,N) V.push_back(i);
	do {
		FOR(i,N) if(abs(V[i]-i)<K) break;
		if(i==N) {
			FORR(v,V) cout<<v+1<<" ";
			cout<<endl;
			break;
		}
	} while(next_permutation(ALL(V)));
	*/
	V.clear();
	if(2*K>N) {
		cout<<-1<<endl;
		return;
	}
	int did=0;
	while(N-did>=4*K) {
		FOR(i,K) V.push_back(did+K+1+i);
		FOR(i,K) V.push_back(did+1+i);
		did+=2*K;
	}
	
	if(N-did<=3*K) {
		FOR(i,N-did) {
			if(i+K<N-did) V.push_back(did+1+i+K);
			else V.push_back(did+1+(i+K)%(N-did));
		}
	}
	else {
		set<int> S;
		FOR(i,N-did) {
			S.insert(did+1+i);
		}
		FOR(i,N-did-2*K) {
			if(i<K) {
				V.push_back(did+1+i+K);
			}
			else {
				V.push_back(did+1+i-K);
			}
			S.erase(V.back());
		}
		did=N-2*K;
		FOR(i,K) {
			V.push_back(did+1+i+K);
			S.erase(V.back());
		}
		FORR(s,S) V.push_back(s);
	}
	
	
	FORR(v,V) cout<<v<<" ";
	cout<<endl;
	
}

まとめ

本番よくまぁまぁな時間で解けたな。