早朝PKU - TopCoderとJ言語と時々F#

早朝PKU

各数が最大値として選ばれる確率と最小値として選ばれる確率を計算して、最大値の期待値から最小値の期待値を引けばよい。

A[i]が最小値として選ばれる確率をP[i]とすれば、A[i]が最大値として選ばれる確率はP[n-i-1]になるので最(小|大)値として選ばれる確率のどちらかだけ計算すれば十分。

確率の計算は組み合わせ使って頑張るだけ。途中で数がでかくなるのでlogとって計算して後でexpした。計算量はO(n)。

選ぶ部分の最後尾を決めつけて二分探索するだけ。計算量はO(N log N)。

b > 0の時はb個をsqrt(a)にして、b <= 0のときは-a*b個を-1/sqrt(a)にする。

んで残りがr個だとするとそのうちint(r/(a+1))個をsqrt(a)にして、int(r-r/(a+1))個を-1/sqrt(a)にする。余った1個が出たら、残りr個の和が0になるような値にする。

という貪欲法。計算量はO(1)。

頂点abを「ここは点aで、これから点bへ行く」って感じで定義する。(どう言えばいいのかよくわからない)

んで頂点ab, bc間(a ≠ c)にだけ辺が存在して、長さが「点a, b間の距離 + 線分abとbcのなす角」とする。

あとはダイクストラ。計算量はO(n^3 log n)。

やるだけ。