HaskellでABC437を解く

はじめに

ABC437に参加しました。

A問題

問題の通りに実装する。

main = do
  [a,b] <- readInts
  print $ a * 12 + b

A問題提出

B問題

ちょっと強引なコードになってしまいあんまりきれいに書けなかった。

main = do
  [h,w,n] <- readInts
  abs <- replicateM h readInts
  bs <- replicateM n $ do
    b <- readLn :: IO Int
    return b
  ans <- forM [1..h] $ \i -> do
    return $ length [b | b <- bs, b `elem` (abs !! (i-1))]
  print $ maximum ans

B問題提出

C問題

最初はDPと思ったもののソリを引くか乗せるかでコロコロとWの上限が変わってしまうのと10^9なのでArrayで実装もできず詰んでしまいました。
解説を読んでw+pが小さいものをpの最大値から何個引けるかを考えれば良いということを理解て実装したのが以下です。

main = do
  t <- readLn :: IO Int
  replicateM_ t $ do
    n <- readLn :: IO Int
    wps <-  replicateM n $ do
      [w,p] <- readInts
      return (w,p)
    let [ws,ps] = transpose $ map (\(w,p) -> [w,p] ) $ sortBy (\(f1,s1) (f2,s2) -> compare (f1+s1) (f2+s2)) wps
    let p0 = sum ps
    print $ caseSolve p0 0 ws ps

caseSolve power cnt [] _ = cnt
caseSolve power cnt (w:ws) (p:ps)
  | power-(p+w)>= 0 = caseSolve (power-(p+w)) (cnt+1) ps ws
  | otherwise = cnt

C問題提出

おわりに

今回は惨敗でした。DはAiとBiを昇順に並べておいてどこまでがAi-Biが正か負かを考えれば良さそうだなという仮説を立てましたがC問題で躓いたため着手できずでした。