Submission #5421300
Source Code Expand
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE BangPatterns #-} {-# LANGUAGE TupleSections #-} {-# LANGUAGE ExplicitForAll #-} {-# LANGUAGE LambdaCase #-} {-# LANGUAGE MultiWayIf #-} {-# LANGUAGE Unsafe #-} {-# LANGUAGE RecordWildCards #-} {-# LANGUAGE FlexibleContexts #-} import Debug.Trace (trace) import qualified Control.Monad as M import qualified Data.Map.Strict as Map data Turn = !Sunuke | !Sumeke deriving (Show, Eq, Ord) type Point = Int type Stack = ([Int], [Int]) type Game = (Turn, Stack) main = do _ <- getLine as <- map read . words <$> getLine bs <- map read . words <$> getLine print $ evalDP run $ (Sunuke, (as, bs)) run :: DP Game Point run = dp $ \(!trn, !stc) -> do let (!ss, !ps) = step stc if isEmpty stc then return 0 else do !p's <- sequence $ map run (zip (cycle [next trn]) ss) if trn == Sunuke then return $ maximum [p + p' | (!p, !p') <- zip ps p's] else return $ minimum [0 + p' | (!p, !p') <- zip ps p's] isEmpty :: Stack -> Bool isEmpty (as, bs) = null as && null bs step :: Stack -> ([Stack], [Point]) step ([] , [] ) = ([], []) step (a:as, [] ) = ([(as, [])], [a]) step ([] , b:bs) = ([([], bs)], [b]) step (a:as, b:bs) = ([(as, b:bs), (a:as, bs)], [a, b]) next :: Turn -> Turn next Sunuke = Sumeke next Sumeke = Sunuke -- DP type Memo a b = Map.Map a b type DP a b = a -> State (Memo a b) b dp :: (Ord a, Show a, Show b) => DP a b -> DP a b dp f x = do memo <- gets (Map.lookup x) memos <- get case memo of Just y -> return y Nothing -> do y <- f x modify (Map.insert x y) return y evalDP :: DP a b -> a -> b evalDP f x = evalState (f x) Map.empty evalDPAll :: DP a b -> [a] -> [b] evalDPAll f xs = evalState (sequence (map f xs)) Map.empty -- State.hs newtype State s x = State { runState :: s -> (x, s) } instance Functor (State s) where fmap = M.liftM instance Applicative (State s) where pure x = State $ \s -> (x, s) (<*>) = M.ap instance Monad (State s) where m >>= k = State $ \s -> let (x, s0) = runState m s in runState (k x) s0 get :: (State s) s get = State $ \s -> (s, s) put :: s -> (State s) () put s = State $ \_ -> ((), s) state :: (s -> (a, s)) -> (State s) a state f = do s <- get let (a, s') = f s put s' return a modify :: (s -> s) -> (State s) () modify f = get >>= put . f gets :: (s -> a) -> (State s) a gets f = get >>= return . f evalState :: State s x -> s -> x evalState = (fst .) . runState execState :: State s x -> s -> s execState = (snd .) . runState
Submission Info
Submission Time | |
---|---|
Task | B - ゲーム |
User | ykarako |
Language | Haskell (GHC 7.10.3) |
Score | 0 |
Code Size | 2802 Byte |
Status | CE |
Compile Error
Main.hs:16:13: Cannot parse data constructor in a data/newtype declaration: !Sunuke