TopCoder SRM 644 Div1 Easy: OkonomiyakiParty (しゃくとり法・組み合わせ)

解法

osizeをソートする。

osize[i]が最小となる組み合わせを考える。この時osize[i+M-1]がosize[i]+Kより大きかったら、osize[i]が最小となる組み合わせは0通りである。osize[i]との差がK以内となる最大のosize[last]を考えると、osize[i]は必ず入れることにしているので、last-i個の中からM-1個を選ぶ組み合わせが、osize[i]が最小となる組み合わせとなる。これをi=0,1,...について足し合わせれば良い。

問題

import java.math.BigInteger;
import java.util.Arrays;

public class OkonomiyakiParty {

	private final int MOD = 1000000007;

	public int count(int[] osize, int M, int K) {
		Arrays.sort(osize);
		long ans = 0;
		for (int i = 0; i + M - 1 < osize.length; i++) {
			if (osize[i + M - 1] - osize[i] > K) {
				continue;
			}
			int last = i + M - 1;
			while (last + 1 < osize.length && osize[last + 1] - osize[i] <= K) {
				last++;
			}

			int options = last - i + 1;

			// (option-1)_C_(M-1)
			BigInteger modInteger = new BigInteger(String.valueOf(MOD));
			long comb = 1;
			int x = options - 1;
			int y = M - 1;
			if (x != y) {
				y = Math.min(y, x - y);
				for (int j = 0; j < y; j++) {
					comb *= x - j;
					comb %= MOD;
					comb *= (new BigInteger(String.valueOf(j + 1))).modInverse(modInteger).longValue();
					comb %= MOD;
				}
			}
			ans += comb;
			ans %= MOD;
		}
		return (int) ans;
	}
}