TopCoder SRM 681 Div1 Medium LimitedMemorySeries2

安直に考えすぎた。
https://community.topcoder.com/stat?c=problem_statement&pm=14096

問題

n要素の数列Xがある。
この数列は明に与えられず、パラメータX[0]、a、bから以下の漸化式で生成できる。
X[i+1] = ((X[i] ^ a) + b) and ((2^50) - 1)
なお、本問題はメモリ制限が1MB程度となっており、Xを全部メモリ中に保持することはできない。

数列中i番目の要素の半径kは以下を満たす最大値であるとする。

• (i-k)及び(i+k)番目の要素はXの範囲内である。
• X[i-k]..X[i+k]の中でX[i]が単独で最大である。

数列の各要素に対する半径の和を求めよ。

解法

前回のLimitedMemoryシリーズが記憶にあると、つい平方分割したくなる。
自分もそうしたし、おそらくそれでも解けるが結構めんどくさい。

もっと簡単な方法がある。
Xの漸化式は1つ戻すことも容易である。
そこで、数列の各要素iに対し、題意通りX[i-k]...X[i+k]の範囲でX[i]が最大となるkを毎回愚直に求めればよい。

各iに対しkが大きくなるとTLEにならないか不安だが、実際はそうでもない。
X中X[i]が最大であるとする(同じ値が複数あっても良い)。
X[0..(i-1)]及びX[(i+1)..(n-1)]の半径計算において、X[i]を跨ぐような半径は取れない。
よってそれぞれの半径はせいぜいX[i]の半径の半分となるし、以後X[i]で分割された２つの区間それぞれの中のみを考えればよい。

同様の推論を重ねると、最悪ケースでも区間中真ん中の要素が最大値となる場合で、それでも計算量はO(n*logn)で済む。

class LimitedMemorySeries2 {
	public:
	ll A,B;
	ll nex(ll v) { return ((v^A)+B) & ((1LL<<50)-1); }
	ll pre(ll v) { return  ((v+(1LL<<50)-B)^A) & ((1LL<<50)-1); }
	
	int getSum(int n, long long x0, long long a, long long b) {
		int i,j;
		A=a;
		B=b;
		
		ll ret=0;
		ll y=x0;
		FOR(i,n) {
			ll x=pre(y);
			ll z=nex(y);
			for(j=1;i-j>=0 && i+j<n;j++) {
				if(x>=y || z>=y) break;
				x=pre(x);
				z=nex(z);
			}
			ret += j-1;
			y=nex(y);
		}
		
		return ret%1000000007;
	}
}

まとめ

本番思いついたものの計算量に自信が持てなくて振りきれなかった。