TopCoder SRM 847 : Div1 Medium NoQuickGrowth

言い換えに気付くと楽。
https://community.topcoder.com/stat?c=problem_statement&pm=18057

問題

整数列Sは、S[j]-S[i]＞10*(j-i)であるi,jの対があると成長しすぎと判断される。

整数列Aが与えられる。
Aの要素をいくつか任意に書き換え、Aが成長しすぎとならないようにしたい。
最小何要素書き換えればよいか。

解法

B[i]=A[i]-i*10 とした数列Bを考える。Bの部分列のうち、最長の減少列を残し、それ以外を書き換えることを考えればよい。
以下では、Bをさらに符号反転し、LISを求めている。

template<class CC> int LIS_num(vector<CC>& v) {
	int i,N=v.size();
	vector<CC> dp(N,(numeric_limits<CC>::max)()),id(N);
	FOR(i,v.size()) dp[id[i]=lower_bound(dp.begin(),dp.end(),v[i]) - dp.begin()] = v[i]-1;
	return *max_element(id.begin(),id.end())+1;
}

class NoQuickGrowth {
	public:
	int solve(int N, int delta, int spread, int seed) {
		vector<ll> A;
		ll state = seed;
		int i;
		FOR(i,N) {
		    state = (state * 1103515245 + 12345) % (1LL<<31);
		    ll diff=state%(2*spread + 1);
		    A.push_back(i*delta + diff - spread);
		    A[i]=-(A[i]-10*i);
		}
		
		return N-LIS_num(A);
		
	}
}

まとめ

本番出てたら結構手間取ったかもな…。