練習

今日は、
「プログラミングコンテストチャレンジブック」で取り扱っているPOJの問題をHaskellで解いてみました。

問題はこちら

import Data.List

main = do
  nls <- getLine
  print $ findAnswer (ls nls) []
    where
      ls = map read.tail.words
    
findAnswer :: Integral a => [a]-> [a] -> a
findAnswer [_] xs = sum xs
findAnswer ls  xs = findAnswer (g $ sort ls)  $ f (sort ls) : xs
  where
    f (a:b:_) = a+b
    g (a:b:c) = (a+b:c)

本来は、これらのデータは改行されて読み込まれているので
getContents使ってやらないといけないんですが、まあいいでしょう笑
問題の仕様通り、総分割数の入力も読み込んでいます。

問題読んだら、二分木探索かな、と想像はついたけれど、
逆から辿っていくだなんて..
こんなアルゴリズム思いつきませんでした

なるほど、言われてみれば確かにその通りです。