TopCoder SRM 638 Div1 Medium NarrowPassage2、Div2 Medium NarrowPassage2Easy

600ptにしては簡単な問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13295
http://community.topcoder.com/stat?c=problem_statement&pm=13520

問題

N匹の狼が細い通路に１列に並んでおり、それぞれの大きさsize[i]が与えられている。
２匹の狼は、大きさの合計が道幅であるmaxSize以下であればすれ違うことができる。

任意回数狼同士がすれ違って得られる並び順の組み合わせ数を答えよ。

解法

Div2 EasyはN≦6と制限が小さいので、next_permutationで並び方を総当たりし、すれ違い不可な狼同士がすれ違っていないか判定すればよい。

Div1 MediumはN≦50なので総当たりはできない。

そこで狼を大きさ順にソートし、順に配置していく。
C番目の狼を配置する場合、すでに配置した狼群とサイズを比較し、すれ違い不可能な狼の左端Lと右端Rを求める。
するとC番目の配置は(L+1)～(R-1)番目の間にいる配置済みの狼数+1通り考えられるので、その分を掛算していく。
(位置順で)L＜A＜Cとなる配置済み狼Aがいて、狼Aは狼Lより左に行けてしまうことはないか？と疑問が残るかもしれないが、先に配置された狼Aはsize[A]≧size[C]なはずなので、C番の狼がL番とすれ違えないならA番もL番とすれ違えないのは明らか。

ll mo=1000000007;
int did[60];
pair<int,int> P[51];

class NarrowPassage2 {
	public:
	int count(vector <int> size, int maxSizeSum) {
		int i,x,y;
		int N=size.size();
		
		FOR(i,N) P[i]=make_pair(size[i],i);
		sort(P,P+N);
		reverse(P,P+N);
		
		vector<int> V;
		
		ZERO(did);
		ll ret=1;
		FOR(i,N) {
			int num=1;
			int c=P[i].second,l=P[i].second-1,r=P[i].second+1;
			while(l>=0) {
				if(did[l] && size[c]+size[l]>maxSizeSum) break;
				num+=did[l];
				l--;
			}
			while(r<N) {
				if(did[r] && size[c]+size[r]>maxSizeSum) break;
				num+=did[r];
				r++;
			}
			ret = ret*num%mo;
			did[c]=1;
		}
		return ret;
		
	}
}
||

*まとめ