TopCoder SRM 680 Div1 Easy BearFair

一応Easy,Medium,2Chalとなかなか良好な結果。
https://community.topcoder.com/stat?c=problem_statement&pm=14129

問題

1～bの整数のうちn個の異なる整数からなる集合Sがある。
また、q組の２整数(U[i],Q[i])からなるクエリがある。
以下の条件を満たすSが存在するか判定せよ。

• S中、奇数と偶数の回数は等しい(n/2個ずつ)
• 各クエリについて、S中でU[i]以下の要素はちょうどQ[i]個である。

解法

まずクエリ中U[i]が等しくQ[i]が異なるクエリが複数あったら、条件を満たす集合はありえない。

以下の値を考える。
f(x,o,e) := S中x以下の要素が奇数がo個、偶数はe個となるようなものの存在有無(0か1)
後は上記fをDPでxの小さい順に求めていけば良い。
途中、U[i]=xとなるU[i]があるなら、そこではo+e!=Q[i]の時f(x,o,e)=0で上書きする。

…とまぁO(b*n^2)かかるDPで十分間に合うのだが、O(nlogn)解もある。
番兵として、先にU[i]=0,Q[i]=0およびU[i]=b,Q[i]=nの２クエリをクエリ群に加えておこう。

まずクエリをU[i]昇順にソートする。
U[i]とU[i+1]の間には、(U[i]+1)～U[i+1]の(U[i+1]-U[i])個の整数がある。
ここから(Q[i+1]-Q[i])個の整数を選び、Sに加える。
(U[i]+1)～U[i+1]の間で、取りうる奇数要素及び偶数要素の最小数最大数が求められる。

各隣接クエリ間において、この取りうる奇数要素及び偶数要素の最小数最大数を求め、n/2がその範囲に含まれるか判定すればよい。

以下はDP解の方である。

int ok[1010][26][26];
int must[1010];

class BearFair {
	public:
	string isFair(int n, int b, vector <int> upTo, vector <int> quantity) {
		int i;
		MINUS(must);
		FOR(i,upTo.size()) {
			if(must[upTo[i]]!=-1 && n-quantity[i]!=must[upTo[i]]) return "unfair";
			must[upTo[i]] = n-quantity[i];
		}
		
		ZERO(ok);
		ok[0][n/2][n/2]=1;
		for(i=1;i<=b;i++) {
			int o,e;
			FOR(o,n/2+1) FOR(e,n/2+1) if(ok[i-1][o][e]) {
				// nottake
				ok[i][o][e] = 1;
				if(i%2==1 && o) ok[i][o-1][e] = 1;
				if(i%2==0 && e) ok[i][o][e-1] = 1;
			}
			if(must[i]!=-1) {
				FOR(o,n/2+1) FOR(e,n/2+1) if(o+e!=must[i]) ok[i][o][e]=0;
			}
		}
		if(ok[b][0][0]) return "fair";
		else return "unfair";
		
	}
}

まとめ

DP解は安直すぎるし、O(nlogn)解が想定解？
それならbをもっと大きくすればいいと思うけどなぁ。