TopCoder SRM 833 : Div1 Medium FroggerAndNets

遠回りして無駄に考えてしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=17698

問題

N個の一列に並んだマスがあり、コマを置くことができる一部のマスが指定される。
初期状態では、コマを(置くことができる)任意のマスを選び置くことができる。

ここで、C個の条件が指定される。
各条件は、マスの区間が指定され、その区間内にコマを置かなければならないことを示す。
条件と条件の間に、コマを1回移動することができる。その際、移動したマス数分のスコアを得ることができるとする。

得られる最大スコアを求めよ。

解法

移動距離を最大化したいので、移動すべきマスは区間内で最も左と最も右の二択である。
そこで、条件毎に該当する2マスを求め、その間でスコアの最大値をDPで求めて行こう。

int pre[2020],nex[2020];


class FroggerAndNets {
	public:
	int jump(string stones, int C, int minW, int seed) {
		ll state=seed;
		int N=stones.size();
		int maxW=N-1;
		int i;
		
		int p=-1;
		FOR(i,N) {
			if(stones[i]=='O') p=i;
			pre[i]=p;
		}
		p=N;
		for(i=N-1;i>=0;i--) {
			if(stones[i]=='O') p=i;
			nex[i]=p;
		}
		
		ll LL,RR;
		ll from[2]={0,0};
		FOR(i,C) {
			state = (state * 1103515245 + 12345)%(1LL<<31);
		    int w = minW + (state % (maxW - minW + 1));
			state = (state * 1103515245 + 12345)%(1LL<<31);
		    int L = state % (N - w);
		    int R = L + w;
			
			
			if(nex[L]>R) return -1;
			ll to[2];
			ll NL=nex[L];
			ll NR=pre[R];
			if(i==0) {
				to[0]=to[1]=0;
			}
			else {
				to[0]=max(from[0]+abs(LL-NL),from[1]+abs(RR-NL));
				to[1]=max(from[0]+abs(LL-NR),from[1]+abs(RR-NR));
			}
			LL=NL;
			RR=NR;
			swap(from,to);
		}
		
		return max(from[0],from[1]);
	}
}

まとめ

最初区間は「コマを置いてはいけない区間」と勘違いしてタイムロスしてしまった…。