HaskellでAtCoderやるぜ2

Haskellで蟻本やるぜ5（DP）で、ナップサック問題を解いたので、早速AtCoderに登録してみるぜ。

これだ。

ちなみに、AtCoderでHaskellを使う場合には、ByteString型を使う方がよいらしい。
詳しい説明は、HaskellでAtCoderの問題を解く（入力の高速化編）を参照だぜ。

ByteString型を使って標準入力からデータ取得

import qualified Data.ByteString.Char8 as BS
import qualified Data.List as DL
import qualified Data.Char as DC
import qualified Control.Monad as CM

getintlist = DL.unfoldr (BS.readInt .  BS.dropWhile DC.isSpace) <$> BS.getLine

main :: IO ()
main = do
    [n,maxW] <- getintlist
    items <- CM.replicateM n $ do
      [w,v] <- getintlist
      return (w,v)
    print $ q1' n maxW items

大量データとの戦い

前回のときには、テストデータが少ないせいか、DPよりも単にHaskellで書いた方が速度がでた。
果たして大量データの場合はどうなるのか！！！？？？

• 純粋Haskell版
  無念の時間切れ（TLE）
• DP版
  実行時間: 135 ms メモリ: 87540 KB
• DP+メモ版
  実行時間: 692 ms メモリ: 84856 KB

となり、DP版が勝った！
メモしなくてもよいんだ。。使用メモリ量も大差ないし。。

DP版のコード

一応、優勝したコードを記念コピペ。

-- https://lvs7k.github.io/posts/2018/11/pccb-easy-3/
{-# LANGUAGE BangPatterns, FlexibleContexts #-}

import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array

import qualified Data.ByteString.Char8 as BS
import qualified Data.List as DL
import qualified Data.Char as DC
import qualified Control.Monad as CM

q1' :: Int -> Int -> [(Int, Int)] -> Int
q1' n m wvs = runST $ do
    dp <- newArray ((0, 0), (n, m)) 0 :: ST s (STUArray s (Int, Int) Int)
    forM_ [1 .. n] $ \i -> do
        let (w, v) = wva ! i
        forM_ [0 .. m] $ \j -> do
            x1 <- readArray dp (i - 1, j)
            if j < w
              then writeArray dp (i, j) x1
            else do
              x2 <- readArray dp (i - 1, j - w)
              writeArray dp (i, j) (max x1 (x2 + v))
    readArray dp (n, m)
  where
    wva = listArray (1, n) wvs

getintlist = DL.unfoldr (BS.readInt .  BS.dropWhile DC.isSpace) <$> BS.getLine

main :: IO ()
main = do
    [n,maxW] <- getintlist
    items <- CM.replicateM n $ do
      [w,v] <- getintlist
      return (w,v)
    print $ q1' n maxW items