TopCoder SRM 644 Div1 Easy OkonomiyakiParty

久しぶりに妙なひっかけやコーナーケースのない、落ち着いたEasyだった気がする。

問題

N個の店があり、それぞれで買えるお好み焼きのサイズはO[i]とする。
このうちM個の店でお好み焼きを買ったとき、最大サイズと最小サイズの差がK以下になる組み合わせはいくつあるか答えよ。

解法

まずO[i]をソートしてしまう。

最小値O[x]と最大値O[y]を総当たりすることを考える。
O[y]≦O[x]+Kであれば、そのようなお好み焼きの買い方が可能であり、その時の買い方はO[x+1]～O[y-1]の中から(M-2)個買うのでを答えに加算すればよい。

ll mo=1000000007;

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

class OkonomiyakiParty {
	public:
	int N;
	int count(vector <int> osize, int M, int K) {
		N=osize.size();
		sort(osize.begin(),osize.end());
		ll ret=0;
		int x,y;
		FOR(x,N) {
			y=x;
			while(y<N && osize[y]<=osize[x]+K) y++;
			ret+=comb(y-x-1,M-1);
		}
		return ret%mo;
	}
}

まとめ

落ち着いて解けた。