概要
値 C を持っているときに値 R を "使う" と、持っている値が ( C + R ) / 2 に変化する。N 個の整数があって、その内 K 個を選んで任意の順番で使う。初期状態で 0 を持っているとして、持っている値を最大でいくらにできるか求めよ。
解法
更新後の値は二つの値の平均なので、できるだけ大きい値を使った方が得っぽいです。実際、あるタイミングで使った値より大きな値と交換できるなら、そうした方が平均は大きくなります。
使う値の集合は決まったので、次は使う順序を決めます。ある時点で持っている値が a で、その後 b, c をこの順で使うとします。この時の結果は、b を使った時点での値が
です。更に c を使うと
となります。ここで [tex:b
コード
main = do [ n, k ] <- map read . words <$> getLine as <- drop ( n - k ) . sort . map ( read :: String -> Double ) . words <$> getLine printf "%.9f\n" $ foldl' ( \r c -> ( r + c ) / 2 ) 0 as