TopCoder SRM 745 Div1 Hard Chains5

今回これだけは勉強になった。
https://community.topcoder.com/stat?c=problem_statement&pm=15263

問題

n個の1次元の区間[x[i],y[i])が与えられる。
これらをいくつかの区間列に分割したい。
各区間列では、手前の要素は後の要素に含まれており、かつ手前の方の長さが短くなければならない。

最小何個の区間列で全区間を含められるか。

解法

各区間をグラフの頂点とみなし、包含関係にある区間同士を有向辺で結ぶと、これは頂点を被覆する最小パス数を求める問題と言い換えられる。
最小パス数を求める手法として、Dilworthの定理がある。
これは最小パス数は、互いに遷移できない頂点数の最大値に一致するというものである。

これをこの問題に当てはめると、互いに包含関係を持たない最大の区間集合を求めればよいことになる。
以下、長さ0の区間は先に取り除く。これはこの問題において、長さ0の区間はその位置に関係なく、長さが正の区間に含まれると判定されるので先に除外しておくためである。
この分は最後に、max(得られたパス数, 長さ0の区間数)を返せばよくなる。

各区間をx[i]毎にグループ分けし、y[i]降順にソートする。
あとは互いに遷移できない頂点数と対応する区間の末尾の座標の配列を持ち、グループ毎にLIS風の処理を行えばよい。

ちょっとややこしいのが、x[i]が異なるならy[i]が等しいものは包含関係があるが、x[i]もy[i]も等しいものは包含関係とみなさないことである。

class Chains5 {
	public:

	int construct(vector <int> x, vector <int> y, int n, int seed, int a, int b, int c, int m) {
		while(x.size()<n) {
			int nx,ny;
			seed=(1LL*a*seed+b)%c;
			nx=seed%m;
			seed=(1LL*a*seed+b)%c;
			ny=seed%m;
			if(nx>ny) swap(nx,ny);
			x.push_back(nx);
			y.push_back(ny);
		}
		
		map<int,vector<int>> M;
		int i;
		int zero=0;
		FOR(i,n) {
			if(x[i]==y[i]) {
				zero++;
			}
			else {
				M[x[i]].push_back(y[i]);
			}
		}
		
		vector<int> V;
		FORR(m,M) {
			vector<int> B=m.second;
			sort(ALL(B));
			reverse(ALL(B));
			
			for(i=0;i<B.size();) {
				int num=1;
				while(i+num<B.size() && B[i+num]==B[i]) num++;
				int id=lower_bound(ALL(V),B[i])-V.begin();
				
				int j;
				FOR(j,num) {
					if(V.size()==id) V.push_back(B[i]);
					else V[id]=B[i];
					id++;
				}
				i+=num;
				
			}
		}
		return max(zero,(int)V.size());
		
		
	}
}

まとめ

Dilworthの定理、過去２・３回しか使った記憶ないし毎回忘れる…。