TopCoder SRM 578 Div1 Medium WolfInZooDivOne

問題

一列にN個のセルがある。それぞれのセルには高々1匹の狼が入る。
更に、M個の制約条件があり、
L[i]からR[i]番目（両端含む）のセルには合計で狼が2匹以下しかいないことがわかっている。

このとき、狼の入り方の場合の数をmod 10^9 + 7で求めよ。

制約条件

N≦300
M≦300

方針

動的計画法。
狼は最後の二匹だけを覚えていればよい。
dp[pos][prev1][prev2] := posまで見てprev1とprev2に狼がいたときの場合の数(prev1 > prev2)

posに狼を置く場合、posとprev2を含む区間がなければよい。
これは区間の情報を次のように前処理しておけばO(1)で判定できる。

anyInterval[l][r] := [l, r]を包含する区間があるか。
としてそれぞれの区間ごとにanyInterval[L[i]][R[i]]を1にして、
anyInterval[l][r]が1ならanyInterval[l+1][r], anyInterval[l][r-1]も1にするというDPを幅が大きいほうからやっていく。

たしか本番では上の方針でやったはず。
以下のコードはなんか変な判定方法をやっていて、
まずは区間から重複および、他に完全に包含されるものを削除して、左端の昇順に並べる。
で、ある点を含む区間のうち左端の座標が最小および最大のものを記録しておく。

prev1, prev2に狼がいたときposに狼をおきたいとき、
prev2を含む最大の区間Iと、posを含む最小の区間JがI≧Jなら区間に交差があるので、
I＜Jならよい。
これでも一応時間内に正しい答えが出る。

ソースコード

#define F first
#define S second

const int mod = (int)1e9 + 7;
int dp[2][310][310];
int leftmost[310], rightmost[310];

class WolfInZooDivOne {
	public:
	int count(int N, vector <string> L, vector <string> R) {
		
		memset(dp, 0, sizeof(dp));
		int cur = 0, next = 1;
		vi ls = parse(L), rs = parse(R);
		vector<pi> is;
		
		rep(i, ls.size()){
			bool ok = 1;
			rep(j, ls.size()){
				if(ls[j] == ls[i] && rs[i] == rs[j]) continue;
				if(ls[j] <= ls[i] && rs[i] <= rs[j]) ok = 0;
			}
			if(ok) is.pb(mp(ls[i], rs[i]));
		}
		sort(all(is));
		is.erase(unique(all(is)), is.end());
		
		rep(i, N + 2){
			leftmost[i]  = inf;
			rightmost[i] = -1;
			rep(j, is.size())                       if(is[j].F <= i && i <= is[j].S) rightmost[i] = j;
			for(int j = is.size() - 1; j >= 0; j--) if(is[j].F <= i && i <= is[j].S) leftmost[i]  = j;
		}
		
		dp[0][N + 1][N + 1] = 1;
		rep(i, N){
			memset(dp[next], 0, sizeof(dp[next]));
			
			rep(j, N + 2) rep(k, N + 2){
				
				int c = dp[cur][j][k];
				if(c == 0) continue;
				
				int pos[] = {i, j, k}, left = -1, right = inf;
				
				rep(l, 3){
					left  = max(left,  leftmost[pos[l]]);
					right = min(right, rightmost[pos[l]]);
				}
				
				if(left > right) (dp[next][i][j] += c) %= mod;
				(dp[next][j][k] += c) %= mod;
			}
			swap(cur, next);
		}
		
		ll ans = 0;
		rep(i, N + 2) rep(j, N + 2) ans += dp[cur][i][j];
		return ans % mod;
	}
	vi parse(vector<string> v){
		string s;
		vi res;
		int t;
		rep(i, v.size()) s += v[i];
		stringstream ss(s);
		
		while(ss >> t) res.pb(t);
		return res;
	}
};