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; } }