Submission #5419950


Source Code Expand

import qualified Control.Monad as M
import qualified Data.Map as Map
import qualified Data.List as L
import Data.Maybe (fromJust)

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 $ \g@(trn, stc) -> do
    memo <- get
    let (gs, ps) = step g
    if isEmpty stc
        then return 0
        else do
            p's <- sequence $ map run gs
            let p2s = zip ps p's
            if trn == Sunuke
                then return $ maximum [p + p' | (p, p') <- p2s]
                else return $ minimum [0 + p' | (p, p') <- p2s]

isEmpty :: Stack -> Bool
isEmpty (as, bs) = null as && null bs

step :: Game -> ([Game], [Point])
step (trn, ([]  , []  )) = ([], [])
step (trn, (a:as, []  )) = ([(t', (as, []))], [a])
    where t' = next trn
step (trn, ([]  , b:bs)) = ([(t', ([], bs))], [b])
    where t' = next trn
step (trn, (a:as, b:bs)) = ([(t', (as, b:bs)), (t', (a:as, bs))], [a, b])
    where t' = next trn

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 => DP a b -> DP a b
dp f x = do
  memo <- gets (Map.lookup x)
  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 2587 Byte
Status TLE
Exec Time 2106 ms
Memory 42620 KB

Judge Result

Set Name All
Score / Max Score 0 / 3
Status
AC × 3
TLE × 2
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 AC 2 ms 764 KB
01 TLE 2106 ms 42620 KB
02 TLE 2106 ms 42364 KB
90 AC 2 ms 508 KB
91 AC 2 ms 508 KB