Expected Difference(1)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3015
まず基本的な考え方から。n個の整数の中からm個を無作為に選び、その最大値と最小値の差を求めて、さらにその期待値を求めなければならず、しかもnとmの値が非常に大きい。まずはTLEにならない計算の方針を立てなければなりません。
以下のような例で考えてみます。n個の整数の集合をAとして、その中からm個を無作為に選び出して作る集合をBとしておきます。
①n=4,m=2,A={1,2,3,4}の場合
考えられるBは、{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}の6通り。それぞれの集合について最大値と最小値の差は、1,2,3,1,2,1ですから、1が3通り、2が2通り、3が1通りでその期待値は1*3/6+2*2/6+3*1/6=10/6=1.666...と計算することができます。これはごくごく一般的な計算方法ですが、少し工夫します。最大値と最小値の差を計算せずに、最大値と最小値のみに注目してその分布を調べてみます。

	1	2	3	4
最小値	3個	2個	1個	0個
最大値	0個	1個	2個	3個

最大値の合計から最小値の合計を引けば、(4*3+3*2+2*1)-(1*3+2*2+3*1)=20-10=10になり、Bの組み合わせ数6で割れば期待値を求めることが可能です。個数が同じものの差を先に計算すれば、(4-1)*3+(3-2)*2+(2-3)*1=9+2-1=10と、当然これでも同様の結果になります。

①n=5,m=3,A={1,2,3,4,5}の場合
考えられるBは、{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}の10通りです。これらの中から最大値、最小値になる値の分布を調べてみますと、

	1	2	3	4	5
最小値	6個	3個	1個	0個	0個
最大値	0個	0個	1個	3個	6個

このように、何やら規則性がありそうな雰囲気です。最大値・最小値となり得る値の分布は簡単に計算できそうですね。