TopCoder SRM 804 : Div1 Easy YetAnotherGraphColoring

せっかくのイベント回だったのにunratedだったようで。
https://community.topcoder.com/stat?c=problem_statement&pm=16407&rd=18642

問題

N要素の整数列Aが与えられる。
ここで各要素に対応した頂点を持つ、N頂点のグラフを考える。
x＜yかつA[x]＞A[y]である場合、xとyに対応する頂点に無向辺が張られるとする。

このグラフの頂点を彩色するとき、辺の両端が同じ色にならないようにするには最小何色必要か。

解法

LISならぬLDS(Longest Decreasing Sequence)の長さを求めればよい。

vector<int> LIS(vector<int>& v) {
	int i,N=v.size();
	vector<int> dp(N,1<<30),id(N);
	FOR(i,v.size()) {
		id[i] = lower_bound(dp.begin(),dp.end(),v[i]) - dp.begin();
		// id[i] = lower_bound(dp.begin(),dp.end(),v[i]+1) - dp.begin(); //こうすると同じ値も許容する
		dp[id[i]] = v[i];
	}
	int nl = *max_element(id.begin(),id.end());
	vector<int> ret(nl+1);
	FOR(i,N) if(id[N-1-i] == nl) ret[nl--] = v[N-1-i];
	return ret;
}

class YetAnotherGraphColoring {
	public:
	int minColors(int n, int a1, int a2, int x, int y, int z, int m) {
		vector<int> A;
		A.push_back(a1);
		A.push_back(a2);
		while(A.size()<n) {
			A.push_back((1LL*x*A[A.size()-1]+1LL*y*A[A.size()-2]+z)%m);
		}
		FORR(v,A) v=m-v;
		auto V=LIS(A);
		return V.size();
		
	}
}

まとめ

最初の数列Aを作るところでミスしてたので、参加してratedだったら大ダメージだった。