CSAcademy Round #19 : D. Smallest Array Permutation

D→Eの難易度差が大きい。
https://csacademy.com/contest/round-19/#task/smallest-array-permutation

問題

数列が与えられる。
この数列のPermutationのうち、同じ数字が連続しないもので辞書順最小のものを求めよ。

解法

辞書順最小値を求める問題なので、先頭から順にできるだけ小さいものを置くことを考える。
仮に、未配置の数値のうちある値xが最大でK個あったとする。

• 置く数字の残りが(2K-1)未満の場合、いずれxが連続してしまうので解なし。
• 置く数字の残りが(2K-1)個の場合、ここでxを置かないといずれxが連続してしまうのでここでxを置く。
  • ただし直前に置いたのもxの場合、解なし。
• 置く数字があと2K個以上あるなら、まだxを置かなくてもよい。
  • よって未配置の数字のうち最小値を置く。ただし直前の数字と一致してしまうなら次の数字を置く。

int N;
map<int,int> M;
map<int,set<int>> C;
vector<int> V;

void add(int y) {
	V.push_back(y);
	C[M[y]].erase(y);
	if(C[M[y]].size()==0) C.erase(M[y]);
	M[y]--;
	if(M[y]==0) {
		M.erase(y);
	}
	else {
		C[M[y]].insert(y);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		M[x]++;
	}
	FOR(i,100001) if(M.count(i)) C[M[i]].insert(i);
	
	V.push_back(0);
	FOR(i,N) {
		x = C.rbegin()->first;
		if(x+x-1>N-i) return _P("-1");
		if(x+x-1==N-i) {
			y = *C.rbegin()->second.begin();
			if(V.back()==y) return _P("-1");
			add(y);
		}
		else {
			int tar=-1;
			FORR(r,M) {
				if(V.back()==r.first) continue;
				tar=r.first;
				break;
			}
			add(tar);
		}
	}
	
	for(i=1;i<=N;i++) _P("%d%c",V[i],(i==N)?'\n':' ');
}

まとめ

シンプルでよい問題。