きままにものづくり

日々の気付いたことなんかを書いてます。

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)
である。

コード

広告を非表示にする