TopCoder SRM 743 Div1 Hard PermuteTheArray

方針は悪くなかったがツメが甘かった。
https://community.topcoder.com/stat?c=problem_statement&pm=14835

問題

N要素の整数列がある。
これらを並べ替えたい。

ただし、一部の要素対の間で、要素の和の偶奇が指定される。
条件を満たす並びのうち、辞書順最小のものを求めよ。

解法

N個の要素に対応するN個の頂点からなるグラフを考える。
偶奇が指定された頂点間に辺を張ると、連結成分内の１要素の偶奇が確定すると、連結成分にある全要素の偶奇が決まる。

そこで、まずこのグラフの連結成分と、それぞれにおいて、最小の順番の要素と、それと同じ・異なる偶奇要素の数を求めておこう。
あとは辞書順最小を求める問題のセオリー通り、手前の要素から値を決めていく。
もうその要素の偶奇が決まっているなら、未割当の値のうち最小値を割り当てる。

そうでない場合、余っている要素の最小要素がある側から、偶数・奇数をそれぞれ当てはめることができるか試していく。
まだ偶奇の決まってない連結成分において適切に偶奇を定めたら、ちょうど現在余っている偶奇要素数と一致するかどうかそのつどDPして判定していこう。

int from[251];
int dif[251];
int cat[503];
int P[255][2];
vector<pair<int,int>> E[255];
int NG;


class PermuteTheArray {
	public:
	
	int ok(int a,int s,vector<pair<int,int>> C) {
		int dp[555]={};
		dp[0]=1;
		
		if(a<0 || s<0) return 0;
		
		int i;
		FORR(c,C) {
			for(i=250;i>=0;i--) if(dp[i]) {
				dp[i+c.first]=1;
				dp[i+c.second]=1;
			}
		}
		return dp[s];
	}
	
	void dfs(int cur,int base,int val) {
		if(dif[cur]>=0) {
			if(val!=dif[cur]) NG=1;
			return;
		}
		
		dif[cur]=val;
		from[cur]=base;
		P[base][val]++;
		FORR(e,E[cur]) dfs(e.first,base,val^e.second);
	}
	
	vector <int> getPermutation(vector <int> A, vector <int> x, vector <int> y, vector <int> d) {
		int N=A.size();
		
		MINUS(from);
		MINUS(dif);
		MINUS(cat);
		ZERO(P);
		
		
		multiset<int> cand[2];
		vector<int> R;
		FORR(a,A) cand[a%2].insert(a);
		int i,j,k;
		
		FOR(i,N) E[i].clear();
		FOR(i,x.size()) {
			E[x[i]].push_back({y[i],d[i]});
			E[y[i]].push_back({x[i],d[i]});
		}
		
		NG=0;
		FOR(i,N) if(from[i]<0) dfs(i,i,0);
		if(NG) return R;
		
		int lef[2]={(int)cand[0].size(),(int)cand[1].size()};
		FOR(i,N) {
			if(cat[i]==-1) {
				vector<pair<int,int>> C;
				
				FOR(j,N) if(i!=j && cat[j]==-1 && P[j][0]>0) C.push_back({P[j][0],P[j][1]});
				
				if(lef[1]==0 || (lef[0] && *cand[0].begin()<*cand[1].begin())) {
					if(ok(lef[0]-P[i][0],lef[1]-P[i][1],C)) {
						cat[i]=0;
					}
					else if(ok(lef[0]-P[i][1],lef[1]-P[i][0],C)) {
						cat[i]=1;
					}
				}
				else {
					if(ok(lef[0]-P[i][1],lef[1]-P[i][0],C)) {
						cat[i]=1;
					}
					else if(ok(lef[0]-P[i][0],lef[1]-P[i][1],C)) {
						cat[i]=0;
					}
				}
				
				if(cat[i]==-1) return vector<int>();
				
				lef[cat[i]]-=P[i][0];
				lef[cat[i]^1]-=P[i][1];
				
				FOR(j,N) {
					if(cat[j]==-1 && from[j]==i) cat[j]=cat[i]^dif[j];
				}
			}
			
			R.push_back(*cand[cat[i]].begin());
			cand[cat[i]].erase(cand[cat[i]].begin());
		}
		
		return R;
		
	}
}

まとめ

まぁこれは800ptと言われても納得。
500～550ptぐらいでMediumで出ても違和感ない。