torus711 のアレ

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

Codeforces #243, Division 2, A : Sereja and Mugs

問題概要

 容積が s である空のカップと、n 個のマグカップを使ったゲームをする。n 個のマグカップには最初水が入っていて、i 番のマグカップの内容量は a_i である。各プレイヤーは一回ずつ、空でないマグカップを一つ選んで、その中身をカップに移す。カップから水が溢れた場合、そのプレイヤーの負けとなる。
 n - 1 人でこのゲームをプレイするとき、誰も負けないようなプレイが可能かどうか求めよ。

解法

 選択される n - 1 個のマグカップの内容量の合計を可能な限り小さくしたとき、s 以下にできれば "YES" です。そのようなマグカップの選択は、明らかに、最も内容量の多いマグカップ以外のマグカップを選択することです。

コード

readInt = ( readLn :: IO Int )
getInts = map ( read :: String -> Int ) . words <$> getLine

main = do
	[ n, s ] <- getInts
	sum <- sum . drop 1 . reverse . sort <$> getInts
	putStrLn $ if sum <= s then "YES" else "NO"