TopCoder SRM 824 : Div1 Easy Div2 Hard ExactRate

しょうもないミスでEasy落としたのもったいない。
https://community.topcoder.com/stat?c=problem_statement&pm=17415

問題

整数列Hと閾値Tが与えられる。
Hの連続部分列のうち、Tより大きい要素とT以下の要素の頻度の比率がS:Fとなるような最長のものを答えよ。

解法

Tより大きい要素は+Fポイント、T以下の要素は-Sポイントとみなし、区間和が0ポイントとなるものを選べばよい。
これは典型問題でprefix sumが一致する2か所を求めればよい。

class ExactRate {
	public:
	vector <int> getLongest(int N, int seed, int threshold, int S, int F) {
		int i;
		map<ll,int> R;
		
		ll cur=0;
		R[0]=0;
		int mi=0,ma=0;
		FOR(i,N) {
			seed=(1LL*seed*1103515245+12345)%(1LL<<31);
			if(seed>threshold) cur+=F;
			else cur-=S;
			if(R.count(cur)==0) R[cur]=i+1;
			else {
				if(i+1-R[cur]>ma-mi) {
					mi=R[cur];
					ma=i+1;
				}
			}
		}
		
		return {mi,ma};
	}
}

まとめ

とてもしょうもないミスで落としてるなぁ…。