問題概要
容積が s である空のカップと、n 個のマグカップを使ったゲームをする。n 個のマグカップには最初水が入っていて、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"