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
Author And Source
この問題について(HaskellでAtCoderやるぜ2), 我々は、より多くの情報をここで見つけました https://zenn.dev/forest1040/articles/5c1ca5cd83e65915babb著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol