torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Beginner Contest #003, C : AtCoderプログラミング講座

概要

 値 C を持っているときに値 R を "使う" と、持っている値が ( C + R ) / 2 に変化する。N 個の整数があって、その内 K 個を選んで任意の順番で使う。初期状態で 0 を持っているとして、持っている値を最大でいくらにできるか求めよ。

解法

 更新後の値は二つの値の平均なので、できるだけ大きい値を使った方が得っぽいです。実際、あるタイミングで使った値より大きな値と交換できるなら、そうした方が平均は大きくなります。
 使う値の集合は決まったので、次は使う順序を決めます。ある時点で持っている値が a で、その後 b, c をこの順で使うとします。この時の結果は、b を使った時点での値が
 \frac{ a + b }{ 2 } = \frac{a}{2} + \frac{b}{2}
です。更に c を使うと
 \frac{ \frac{a}{2} + \frac{b}{2} + c }{2} = \frac{a}{4} + \frac{b}{4} + \frac{c}{2}
となります。ここで [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