TopCoder SRM 608 Div1 Hard OneDimensionalRobot

問題

数直線上を走るロボットがいる。
最初ロボットは原点にいて、commandの文字列にしたがって動く。
i番目の文字がRのときロボットは+1, Lのときロボットは-1動く。

ロボットの座標が-A未満になるときまたはBより大きくなるときには命令は無視される。
(A, B)をminA≦A≦maxA, minB≦B≦maxBなるBについて全てロボットの動きを試す。
ロボットの最終位置の座標の値の総和を求めよ。

制約条件

commandの長さ≦5000
minA, maxA, minB, maxBは1以上5000以下

方針

A, Bをループで全通り試すのだが、シミュレーションがOn)かかるので、これを前の結果を利用して速く出来ればいい。

Aごとに、BをmaxBからminBまで減らす。
BがmaxBのときまず愚直にシミュレーションする。
で、最後に-AまたはBにぶつかった位置を覚えておく。

Bを減らしたとき、最後にぶつかったほうがBなら、そこから先の座標が全て-1される。
Aなら何もない。
最後にぶつかる以前の軌道への影響は、最後にぶつかった位置以降には全く影響がないので無視できる。
それで、新たに後ろのほうでA, Bにぶつかっていたら、ぶつかった位置を更新する。

最大値の取得は、座標の最大値が5000くらいしかない上に、最大値はどんどん減っていくだけなので、
値の出現回数を数えておけばならしO(1)でできる。
ぶつかる位置もどんどん前になっていくだけなので、ならしでO(1)でできる。

何もむずかしくないのだけど、75分でeasy, medを解いてから解くのはなかなかむりそう。

ソースコード

const int GETA = 5010;
int cnt[10020], pos[10020], d[5000];

class OneDimensionalRobot {
	public:
	long long theSum(vector <string> commands1, vector <string> commands2, int minA, int maxA, int minB, int maxB) {
		string s;
		rep(i, commands1.size()) s += commands1[i];
		rep(i, commands2.size()) s += commands2[i];
		
		int n = s.size();
		ll ans = 0;
		
		rep(i, n) d[i] = s[i] == 'R' ? 1 : -1;
		
		for(int A = -maxA; A <= -minA; A++){
			
			memset(cnt, 0, sizeof(cnt));
			int B = maxB, x = 0, last = -1;
			int mx = 10020 - 1, mn = 0;
			int geta = 0;
			
			rep(i, n){
				x += d[i];
				if(x <= A) x = A, last = i;
				if(x >= B) x = B, last = i;
				pos[i] = x;
				cnt[x + GETA]++;
			}
			
			rep(i, last) cnt[pos[i] + GETA]--;
			ans += x;
			
			while(--B >= minB){
				while(cnt[mx] == 0) mx--;
				while(cnt[mn] == 0) mn++;
				
				if(last < 0){
					if(mx - GETA != B) goto END;
					rep(i, n) if(pos[i] == B) last = i;
					rep(i, last) cnt[pos[i] + GETA]--;
				}
				else{
					if(pos[last] + geta == B + 1) geta--;
					while(cnt[A + GETA - geta] + cnt[B + GETA - geta] > 1) cnt[pos[last++] + GETA]--;
					while(pos[last] + geta != A && pos[last] + geta != B) cnt[pos[last++] + GETA]--;
				}
				END:
				ans += pos[n - 1] + geta;
			}
		}
		return ans;
	}
};