SRM644Div1Easy
問題
N種類のお好み焼きとそのサイズの配列osizeが与えられる。M個のお好み焼きを選び、その中の最大サイズと最小サイズの差がK以下となるにする。この時のM個のお好み焼きの組み合わせを求めよ。
解法
与えられるサイズをソートする。
小さい方から、iを選択しosize[j] osize[i] + Kとなるjを選択する。iは必ず含むようにしてM-1個のお好み焼きをi+1~jの中で選ぶ。 をすべてのiに対して計算することで答えが求まる。
計算量
階乗の計算を工夫していないので、下のコードでは階乗の計算が
になっている。
よって、
全体の計算量は
である。