\(K=1\) のとき、答えは明らかに \(0\) です。以下では \(2\leq K\) を仮定します。

\(A\) を昇順にソートし、\(A_1<A_2<...<A_N\) であるとします。 \(K\) 個の要素を選び、最大値 \(X\) が \(A_{max}\)、最小値 \(Y\) が \(A_{min}\) になったとすると、\(1 \leq min < max \leq N\) であり、\(X-Y\) の値は次のように言い換えられます。

• \(\sum\limits_{i=min}^{max-1}(A_{i+1}-A_i)\)

ここで、各 \(i\,(1 \leq i <N)\) について、最終的な答えに対する \(A_{i+1}-A_{i}\) の寄与を求め、その総和をとることを考えます。

\(A_{i+1}-A_i\) が上記の式の値に寄与するための条件は、\(min \leq i \leq max-1\) 、すなわち、選んだ \(K\) 個の要素のうち、\(A_i\) 以下のものが存在し、かつ \(A_{i+1}\) 以上のものが存在することです。

この確率は、余事象を考えることで、以下の式で表すことができます。

• \(\dfrac{_{N}C_{K}-_{i}C_{K}-_{N-i}C_{K}}{_{N}C_{K}}\)

よって求める期待値は以下です。

• \(\sum\limits_{i=1}^{N-1}\dfrac{_{N}C_{K}-_{i}C_{K}-_{N-i}C_{K}}{_{N}C_{K}}(A_{i+1}-A_i)\)

この値は、適切に前処理を行うことで、\(O(N)\) で求めることが可能です。