SRM644Div1Easy - きままにものづくり

N種類のお好み焼きとそのサイズの配列osizeが与えられる。M個のお好み焼きを選び、その中の最大サイズと最小サイズの差がK以下となるにする。この時のM個のお好み焼きの組み合わせを求めよ。

与えられるサイズをソートする。
小さい方から、iを選択しosize[j] $\leq$ osize[i] + Kとなるjを選択する。iは必ず含むようにしてM-1個のお好み焼きをi+1~jの中で選ぶ。 ${}_{j-i+1} C_{M-1}$ をすべてのiに対して計算することで答えが求まる。

$O(N^2)$
階乗の計算を工夫していないので、下のコードでは階乗の計算が
$O(N)$
になっている。
よって、
全体の計算量は
$O(N^3)$
である。