TopCoder SRM 578 Div1 Medium WolfInZooDivOne

さてDiv1 Medium。本番に解き切れなかったのが残念。
http://community.topcoder.com/stat?c=problem_statement&pm=12534

問題

Nマスに狼を配置するのは、先のDiv2 Hardとおなじ。
Div2 Hardでは、[L,R]内に狼が１匹以上いることが必要だったが、こちらでは[L,R]内に狼が２匹以内でなければならない点が異なる。

解法

Div2 HardではマスXに対し１匹以上狼がいないといけない右限A[X]を求めたが、今度は２匹以下しか狼を置けない右限B[X]を先に求めておく。

次に、Div2 Hardでは各マスPの最寄の狼QについてDPしたが、今度はPの最寄の２匹の狼Q1,Q2に対してDPをすればよい。
Div2 HardはO(N^2)だったが、こちらは最寄の２匹の狼の位置でループを回すのでO(N^3)。

ll mo=1000000007;

class WolfInZooDivOne {
	public:
	
	string concatvec(vector <string> expr) { return accumulate(expr.begin(),expr.end(),string("")); }
	vector<int> split_int(const string &str, char delim){
		vector<int> res;
		size_t current = 0, found;
		while((found = str.find_first_of(delim, current)) != string::npos){
			string s = string(str, current, found - current);
			res.push_back(atoi(s.c_str()));
			current = found + 1;
		}
		string s = string(str, current, str.size() - current);
		res.push_back(atoi(s.c_str()));
		return res;
	}
	
	int count(int N, vector <string> L, vector <string> R) {
		int i,x,y,z;
		int inval[301];
		vector<int> LI=split_int(concatvec(L),' ');
		vector<int> RI=split_int(concatvec(R),' ');
		
		int MR[301];
		FOR(x,N) MR[x]=-1;
		FOR(x,LI.size()) MR[LI[x]]=max(MR[LI[x]],RI[x]);
		FOR(x,N) FOR(y,x) if(MR[y]>=x) MR[x]=max(MR[x],MR[y]);
		
		ll DP[2][301][301];
		ZERO(DP);
		DP[0][N][N]=1;
		int cur=0;
		for(x=N-1;x>=0;x--) {
			int tar=1-cur;
			ZERO(DP[tar]);
			for(y=x+1;y<=N;y++) {
				for(z=y;z<=N;z++) {
					// not put
					DP[tar][y][z] = (DP[tar][y][z] + DP[cur][y][z]) % mo;
					if(MR[x]<z || z==N) {
						// put
						DP[tar][x][y] = (DP[tar][x][y] + DP[cur][y][z]) % mo;
					}
				}
			}
			cur=1^cur;
		}
		
		ll res=0;
		FOR(x,N+1) FOR(y,N+1) res=(res+DP[cur][x][y])%mo;
		return (int)res;
	}

};

まとめ

なんか似た問題見たな…と思ったらCF164 Div2 Dだな。
こういう数の条件が１とか２とか妙に小さい場合、その分の値を覚えてDPすることを考慮しよう。

下手にSRM576 Div1Mediumが頭に浮かんだおかげで、連結成分をどうこうするのかな？とか考えてしまってタイムロスしてしまった。